為什么在某些情況下,Python 3中的連接似乎比Python 2中的連接慢?影響最大的串聯(lián)方法似乎是bytes對(duì)象的連續(xù)串聯(lián),從O(n)到O(n2)操作。我的分析代碼大部分在這里:#!/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腳本中的一些圖形如下所示:
1 回答

慕勒3428872
TA貢獻(xiàn)1848條經(jīng)驗(yàn) 獲得超6個(gè)贊
將字符串串聯(lián)+
或+=
循環(huán)連接從來(lái)都不是一個(gè)好主意。這樣做似乎很有效,因?yàn)樵谧止?jié)碼解釋器循環(huán)中存在一個(gè)奇怪的,有爭(zhēng)議的特殊情況,如果無(wú)法證明沒(méi)有其他人引用正在處理的字符串,它將試圖以可變方式連接字符串。沒(méi)有有效的調(diào)整大小政策;它只是調(diào)用realloc
并希望達(dá)到最佳效果,因此,如果realloc
需要復(fù)制,它仍然可能以O(shè)(n ^ 2)結(jié)尾。
在Python 3中,這種奇怪的特殊情況現(xiàn)在可以處理unicode字符串,而不是字節(jié)字符串。字節(jié)串連接每次都返回建立新的字符串對(duì)象,因此循環(huán)返回到O(n ^ 2)。
添加回答
舉報(bào)
0/150
提交
取消