如何加速Python中的字符串连接？

Question

在下面的代码中，连接字符串的过程非常慢。你可以看到我尝试了一些复杂的方法来加快这个速度，但无论如何还是很慢。我想知道有没有什么办法可以让它更快。

顺便说一下，plain和secret都是从二进制文件中读取的数据，而且它们的大小都挺大的（大约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

Answer 1

Python中的列表在添加元素时，平均来说是O(1)的速度。也就是说，添加一个元素的时间是固定的，不会随着列表的大小而变化。你可以选择不在最里面的列表中进行连接，而是先把所有的元素放到一个大列表中，最后再一次性连接起来。这样可以把你的算法从O(N^2)的复杂度降低到O(N)。不过，要给你提供具体的代码，我需要知道你的setBit()和getBit()这两个函数具体是做什么的，但可以参考以下这种写法：

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

Answer 2

我觉得你根本不应该使用字符串拼接。更好的方法是创建一个可变的 bytearray，大小和最终数据一样，然后逐个设置每个字节。这样做的效率是 O(N)，而且在你要做的事情上，使用 bytearray 比处理字符串要自然得多：

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