CODEWITHSUNDEEP
python
sowa
sowa

Reputation: 56

How to speed up string concatenation in Python?

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

Upvotes: 3

Views: 1117

Answers (2)

xscott
xscott

Reputation: 2420

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)

Upvotes: 7

Scott Griffiths
Scott Griffiths

Reputation: 21925

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

Upvotes: 5

Related Questions