How to speed up string concatenation in Python?

Question

In the code below concatenation is the bottleneck. As you can see i've tried some sophisticated methods to speed this up, but its bloody slow anyway. I would like to know if there is anything i can do to make it faste.

BTW both plain and secret are data read from binary file and they are quite big (around 1mb)

x = b''
if len(plain) < len(secret*8):
    return False
i = 0

for secByte in secret:
    for j in range(8):
        z = setBit(plain[i],0,getBit(secByte,j))
        #x += bytes([z])
        x = x.join([b"", bytes([z])])
        #x = array.array("B",(int(z) for z in x.join([b"", bytes([z])]))).tostring()
        i = i+1

can you add a simple "C" like pseudocode of what you are trying? I am unfamiliar with setBit in Python... — K. Brafford
– K. Brafford, Commented Nov 27, 2010 at 3:17
For string concatenation methods and speed see these:stackoverflow.com/questions/1316887/… — mshsayem
– mshsayem, Commented Nov 27, 2010 at 4:35

xscott · Accepted Answer · 2010-11-28 21:41:45Z

7

Python's lists have O(1) append, at least in the amortized sense. Instead of doing the join in the innermost list, you could build one big list and then join them at the end. This will turn your algorithm from O(N^2) to O(N). It's tough to give you working code without knowing exactly what your setBit() and getBit() functions are doing, but something like:

L = []
for secByte in secret:
    for j in range(8):
         z = ...
         L.append(z)
x = b"".join(L)

edited Nov 28, 2010 at 21:41

answered Nov 27, 2010 at 2:35

xscott

2,43018 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

nate c Over a year ago

That has not been true since Python 2.3. Time some code with concatenation and with joins.

xscott Over a year ago

@nate c, Python strings are an array of contiguous bytes and associated length. His code with x.join(...) creates a new, slightly longer string every time before it deallocates the old string when he assigns to it. This is O(N^2) behavior. You're wrong, and you shouldn't have modded me down.

Jim Dennis Over a year ago

The suggestion that one build strings as lists and only join them as necessary (preferably after the entire list is built) is still valid so far as I know. It's been a recommended Python practice for a very long time.

nate c Over a year ago

@Jim: I'm not saying its not. I'm saying Big O analysis of Strings is incorrect.

nate c Over a year ago

@xscott: Heres the discussion on the patch -- we are not talking about 2x or even 10x faster but roughly Nx faster where N is the size of the input data set. mail.python.org/pipermail/python-dev/2004-August/046686.html

|

Scott Griffiths · Accepted Answer · 2010-11-27 10:42:07Z

5

I don't think you should be using string concatenation at all for this. It would be better to create a mutable bytearray of the full size of the final data and then set each byte. This is very much O(N) and for what you are doing using a bytearray is much more natural than string manipulation:

x = bytearray(len(secret)*8)   # creates an array of zero bytes
i = 0
for secByte in secret:
    for j in range(8):
        x[i] = setBit(plain[i], 0, getBit(secByte, j))
        i += 1

answered Nov 27, 2010 at 10:42

Scott Griffiths

22k8 gold badges58 silver badges86 bronze badges

1 Comment

sowa Over a year ago

tyvm, it's exactly what i needed (it works like 100x faster) xscott solution is propably as fast as this, but this one is a litle better suiting to my problem

Collectives™ on Stack Overflow

How to speed up string concatenation in Python?

2 Answers 2

6 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related