如何在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

- sowa

---

你能否添加一个类似于"C"语言的伪代码，以便我更好地理解你的意图？我对Python中的setBit不熟悉。 - K. Brafford

有关字符串连接方法和速度，请参见以下链接：https://dev59.com/83M_5IYBdhLWcg3wlELO - mshsayem

Python中的字符串连接操作，使用join()函数比直接使用"+"号更快，但这是为什么呢？ - mshsayem

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)

- xscott

---

自从Python 2.3以来，这已经不再是真实的了。使用连接和连接方式（concatenation and joins）来测试一些代码所需的时间。 - nate c

@nate c，Python的字符串是一系列连续的字节和相关长度。他的代码中的x.join(...)在分配给它之前每次都会创建一个新的、稍微更长一点的字符串，并在释放旧字符串时。这是O(N^2)的行为。你错了，而且你不应该把我降级。 - xscott

据我所知，将字符串构建为列表并仅在必要时连接它们（最好在整个列表构建完成后）的建议仍然有效。这是很长一段时间以来推荐的Python实践。 - Jim Dennis

@Jim：我不是说它不正确。我是说字符串的大O分析是错误的。 - nate c

@xscott：这是有关补丁的讨论 -- 我们不是在谈论2倍甚至10倍的速度提升，而是大约Nx倍的提升，其中N是输入数据集的大小。 http://mail.python.org/pipermail/python-dev/2004-August/046686.html - nate c

@nate c，这至少有以下几个有趣的原因：它没有得到很好的宣传（Python网站仍然建议使用str.join(list)），它没有在stringobject.c中实现，而是作为ceval.c中的一个hack实现，你发送的链接显示Guido在添加它时感到恼火。我对于字符串和+=的理解是错误的，但@sowa代码中的x.join(...)仍然是O(N^2)。 - xscott

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

- Scott Griffiths

---

非常感谢，这正是我所需要的（它的速度快了100倍）。 xscott的解决方案可能和这个一样快，但这个更适合我的问题。 - sowa