python - 为什么 Python 中的连接似乎变慢了?
问题描述
为什么在某些情况下 Python 3 中的连接似乎比 Python 2 慢?
受影响最大的连接方法似乎是bytes
对象的连续连接,它从 O(n) 变为 O(n²) 操作。
我的大部分分析代码在这里:
#!/usr/bin/env python
from operator import concat
from sys import version, version_info
from 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 StringIO
else:
from io import StringIO
from functools import reduce
xrange = range
def build_plus():
output = ''
for _ in xrange(input_len):
output += 'a'
return output
def 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 output
def 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_cstringio
else:
from io import BytesIO
def build_bytesio():
output = BytesIO()
for _ in xrange(input_len):
output.write(b'a')
return output.getvalue()
builds['BytesIO'] = build_bytesio
resfile = open('times.csv', 'a')
size_range = 50 # Number of points over the size axis
min_order = 1.0 # 10^x byte input min
max_order = 5.0 # 10^x byte input max
for allow_gc in (False, True):
setup = 'gc.enable()' if allow_gc else 'pass'
for build_name, build_fun in builds.items():
# For a roughly constant confidence interval, aim for uniform sample density across the
# (logarithmic) input size axis.
for size_index in range(size_range+1):
input_len = int(10**((max_order-min_order)*size_index/size_range + min_order))
# Rather than repeating many measurements at one input size, perform one measurement
# per input size for a continuous range of input sizes and apply smoothing later.
dur = timeit(build_fun, setup, number=1)
resfile.write('"%s",%s,"%s",%d,%.6g\n' % (ver, str(allow_gc).upper(), build_name,
input_len, dur))
我的 R 脚本中的一些图表如下所示:
解决方案
将字符串与+
或+=
在循环中连接从来都不是一个好主意。它看起来很有效,因为在字节码解释器循环中有一个奇怪的、有争议的特殊情况,如果它可以证明没有其他人引用它正在处理的字符串,它会尝试可变地连接字符串。没有有效的调整大小政策;它只是打电话realloc
realloc
并希望最好,所以如果需要复制,它仍然可能以 O(n^2) 结束。
在 Python 3 中,这种奇怪的特殊情况现在处理 unicode 字符串而不是字节字符串。字节串连接每次都回到构建一个新的字符串对象,所以你的循环回到 O(n^2)。
推荐阅读
- c++ - 为什么当我尝试通过地址访问 Lambda 本地变量时出现访问冲突
- node.js - 在 CRA React 应用程序中构建构建脚本的正确方法是什么?
- java - 无法在 Eclipse 中创建新的 EJB 项目
- node.js - 错误 gyp ERR!堆栈错误:`C:\Program Files (x86)\MSBuild\14.0\bin\MSBuild.exe` failed with exit code: 1 while istalling Node on my project
- sas - 计算每个变量子集的唯一 ID 数
- delphi - Delphi - 更改菜单栏颜色
- java - 使用 gradle jar 文件查找主类时出现问题
- swift - ObservedObject 更改不会重绘 SwiftUI 视图
- jquery - 如何使此功能适用于所有实例
- php - 如何解析 Facebook 提要并在网站上显示