为什么Python中的串联似乎变得越来越慢？

Question

为什么在某些情况下，Python 3中的连接似乎比Python 2中的连接慢？影响最大的串联方法似乎是bytes对象的连续串联，从O（n）到O（n²）操作。我的分析代码大部分在这里：#!/usr/bin/env pythonfrom operator import concatfrom sys import version, version_infofrom timeit import timeit  # Compatibility: ver >= 2.6# ver = version.partition('\n')[0].rstrip()ver = '.'.join(str(v) for v in version_info[:3])print(ver)if version_info[0] == 2:    from StringIO import StringIOelse:    from io import StringIO    from functools import reduce    xrange = rangedef build_plus():    output = ''    for _ in xrange(input_len):        output += 'a'    return outputdef build_join():    return ''.join('a' for _ in xrange(input_len))def build_bytes_plus():    output = b''    for _ in xrange(input_len):        output += b'a'    return outputdef build_stringio():    output = StringIO()    for _ in xrange(input_len):        output.write('a')    return output.getvalue()def build_reduce():    return reduce(concat, ('a' for _ in xrange(input_len)))builds = {'str+': build_plus,          'join': build_join,          'reduce': build_reduce,          'bytes+': build_bytes_plus,          'StringIO': build_stringio}if version_info[0] == 2:    import cStringIO    def build_cstringio():        output = cStringIO.StringIO()        for _ in xrange(input_len):            output.write('a')        return output.getvalue()    builds['cStringIO'] = build_cstringioelse:    from io import BytesIO    def build_bytesio():        output = BytesIO()        for _ in xrange(input_len):            output.write(b'a')        return output.getvalue()    builds['BytesIO'] = build_bytesioresfile = open('times.csv', 'a')size_range = 50  # Number of points over the size axismin_order = 1.0  # 10^x byte input minmax_order = 5.0  # 10^x byte input max我的R脚本中的一些图形如下所示：

Answer 1

将字符串串联+或+=循环连接从来都不是一个好主意。这样做似乎很有效，因为在字节码解释器循环中存在一个奇怪的，有争议的特殊情况，如果无法证明没有其他人引用正在处理的字符串，它将试图以可变方式连接字符串。没有有效的调整大小政策；它只是调用realloc并希望达到最佳效果，因此，如果realloc需要复制，它仍然可能以O（n ^ 2）结尾。

在Python 3中，这种奇怪的特殊情况现在可以处理unicode字符串，而不是字节字符串。字节串连接每次都返回建立新的字符串对象，因此循环返回到O（n ^ 2）。