layout: post author: zoomq title: Python 列表开销优化 description: ~ via CPyUG categories: Think tags: CPyUG Python Pythonic
a里面的测试表明了一个问题,定态分配的list快过列表推导式快过append重复调用. 这说明有的时候用列表推导式而不是append可以加速代码.
然后是静态生成. 理论上说,在任何情况下,这个都比列表推导式和append快,而且实际上就是快. 这很好理解,静态生成不需要扩张大小,尤其是list的大小重分配是一个很频繁的问题.
列表推导式和append之间关系
def join3(n): b = [] for i in xrange(n): b.append(a[i]) # return ''.join(b) def join4(n): b = [a[i] for i in xrange(n)] # return ''.join(b) for n in xrange(1, 40, 2):
0.723090629108 0.74334951208 0.610983964173 0.627904584411 0.594889465838 0.576456981387 0.587058850443 0.574822100807 0.571444616501 0.558473461852 0.553502716806 0.54686361629 0.542239744063 0.550127440675 0.558543129789 0.55148314297 0.544658859149 0.537840854175 0.550946275219 0.546243330849
从数据可以看出,两者性能比大约在1:0.6左右,随着元素的数量小幅变化.
列表推导式和append的反编译分析
append的:
19 0 BUILD_LIST 0
3 STORE_FAST 1 (b)
20 6 SETUP_LOOP 37 (to 46)
9 LOAD_GLOBAL 0 (xrange)
12 LOAD_FAST 0 (n)
15 CALL_FUNCTION 1
18 GET_ITER
>> 19 FOR_ITER 23 (to 45)
22 STORE_FAST 2 (i)
25 LOAD_FAST 1 (b)
28 LOAD_ATTR 1 (append)
31 LOAD_GLOBAL 2 (a)
34 LOAD_FAST 2 (i)
37 BINARY_SUBSCR
38 CALL_FUNCTION 1
41 POP_TOP
42 JUMP_ABSOLUTE 19
>> 45 POP_BLOCK
>> 46 LOAD_CONST 0 (None)
49 RETURN_VALUE
列表推导式:
24 0 BUILD_LIST 0
3 LOAD_GLOBAL 0 (xrange)
6 LOAD_FAST 0 (n)
9 CALL_FUNCTION 1
12 GET_ITER
>> 13 FOR_ITER 16 (to 32)
16 STORE_FAST 1 (i)
19 LOAD_GLOBAL 1 (a)
22 LOAD_FAST 1 (i)
25 BINARY_SUBSCR
26 LIST_APPEND 2
29 JUMP_ABSOLUTE 13
>> 32 STORE_FAST 2 (b)
35 LOAD_CONST 0 (None)
38 RETURN_VALUE
OK,现在理解了?
列表生成成本分析
其次是列表推导式成本.
def join4(n):
b = [a[i] for i in xrange(n)]
for n in xrange(1, 1000, 50):
:
1 0.0476880073547 0.0476880073547 51 0.420774936676 0.00825048895443 101 0.769494771957 0.00761876011839 151 1.0588850975 0.00701248408943 201 1.32135987282 0.00657392971551 251 1.59451413155 0.00635264594241 301 1.87293815613 0.00622238590076 351 2.16326808929 0.00616315694956 401 2.44224190712 0.00609037882075 451 2.71852707863 0.00602777622756 501 3.00196099281 0.00599193810941 551 3.29650497437 0.00598276764858 601 3.61599302292 0.00601662732599 651 3.91590690613 0.00601521798176 701 4.13701701164 0.00590159345455 751 4.40393304825 0.00586409194174 801 4.7007830143 0.00586864296417 851 4.96966505051 0.00583979441893 901 5.25287795067 0.00583005321939 951 5.54418587685 0.00582984845094
注意,以上数据的timeit为100000,不是文章里常用的1000000
list的重分配逻辑和dict类似. 我这里有一篇python中dict的插入复杂度估算和排重复杂度估算,说明list的插入成本大约应该是O(1)级别. 单纯来看似乎并不吻合.
使用matplotlib对曲线做拟合,发现应当是一条不过原点的方程,拟合后方程应为O=0.0054n+0.0423. 拟合曲线还是略有点奇怪,怀疑是因为list在低段数据下复制不均匀所致. 不过原点的原因很简单,还有list生成开销呢.
1 0.0464599132538 0.0477 0.974002374293 51 0.420957803726 0.3177 1.32501669413 101 0.722836017609 0.5877 1.22994047577 151 1.0100440979 0.8577 1.17761932832 201 1.27215504646 1.1277 1.12809705282 251 1.55443191528 1.3977 1.11213559082 301 1.84508705139 1.6677 1.10636628374 351 2.12424898148 1.9377 1.09627340738 401 2.40401697159 2.2077 1.08892375395 451 2.68004202843 2.4777 1.08166526554 501 2.94087600708 2.7477 1.07030462098 551 3.21941900253 3.0177 1.06684528036 601 3.52912306786 3.2877 1.07343220727 651 3.79638195038 3.5577 1.06708883559 701 4.0689470768 3.8277 1.06302664179 751 4.35646104813 4.0977 1.06314787518 801 4.62156105042 4.3677 1.05812236427 851 4.87002706528 4.6377 1.05009531994 901 5.17770791054 4.9077 1.05501719961 951 5.42190599442 5.1777 1.04716495633
还原到原始的timeit,O=0.054*n+0.423.
无列表成本对比
使用直接join和concat对比,在任何一个n下,两者的比值基本都接近于3.
shell@shell-deb:/tmp$ python a.py 0.582046985626 1.78690886497
10对象
shell@shell-deb:/tmp$ python a.py 4.21616888046 14.2262041569
100对象
shell@shell-deb:/tmp$ python a.py 4.01020812988 12.4731109142
1000对象,降低timeit次数
>>> 1.78690886497/0.582046985626 3.0700422974412516 >>> 14.2262041569/4.21616888046 3.3742016888440833 >>> 12.4731109142/4.01020812988 3.1103400397757515
而反过来,做字节大小变化.
shell@shell-deb:/tmp$ python a.py 0.582046985626 1.78690886497
10字节
shell@shell-deb:/tmp$ python a.py 0.707537174225 1.83530902863
100字节
shell@shell-deb:/tmp$ python a.py 1.57860517502 2.82620382309
1000字节
>>> 1.78690886497/0.582046985626 3.0700422974412516 >>> 1.83530902863/0.707537174225 2.5939400719690857 >>> 2.82620382309/1.57860517502 1.790317089929845
随着字节数的增加,join和concat的效率比明显发生变化. 具体来说,字节数越大,concat的相对效率越高(但是始终比join低). 对此我特意验证了一下10k字节的,结论是两者效率相差无几. 很明显,如果是重复分配模型,根本不会出现这样的结果. 这足以说明python在对随机字符的concat上使用的不是重复分配模型.
有趣的是,阅读python源码,可以在stringobject.c:1015(Python-2.7.1源码)看到,concat并没有做什么特殊优化. 就是干做memcpy. 而memcpy的总体O应当为O(n^2). 对此我只能认为,如上面朋友所说,在主循环里面有特殊优化.
http://wiki.python.org/moin/PythonSpeed/PerformanceTips#String_Concatenation
concat和对象个数间的关系
采用以下代码.
def concat(n):
b = ''
for i in xrange(n):
b += a[i]
return b
for n in xrange(1, 40, 2):
1 0.0361330509186 0.0361330509186
3 0.0786919593811 0.026230653127
5 0.0982298851013 0.0196459770203
7 0.126276016235 0.0180394308908
9 0.157994031906 0.017554892434
11 0.189352989197 0.0172139081088
13 0.217918872833 0.0167629902179
15 0.249435186386 0.0166290124257
17 0.285101890564 0.0167706994449
19 0.313716888428 0.0165114151804
21 0.343729019165 0.0163680485317
23 0.38047504425 0.0165423932283
25 0.433068990707 0.0173227596283
27 0.471400976181 0.0174592954141
29 0.531830787659 0.0183389926779
31 0.578590869904 0.0186642216098
33 0.606976985931 0.0183932419979
35 0.633711099625 0.0181060314178
37 0.65832901001 0.0177926759462
39 0.681631088257 0.0174777202117
注意这个数据是timeit在100000下的值.
可以看到,随着n的上涨,字符串拼接的平均成本是下降的. concat的时间复杂度不是O(n). 拟合后表明,这个是一个略有偏差的一次方程,可以用O=0.015n+0.015近似. 这表明字符串相加确实是线性的.
还原原始方程,O=0.15n+0.15
join成本分析
for n in xrange(1, 100, 5): del a[:] for i in xrange(n): a.append(''.join([random.choice(string.letters) for j in xrange(10)])) t = timeit.Timer('join()', 'from __main__ import join') t = t.timeit(1000000) print n, t, t/n 1 0.173592090607 0.173592090607 6 0.434324979782 0.0723874966304 11 0.630973815918 0.0573612559925 16 0.830116987228 0.0518823117018 21 1.0301399231 0.0490542820522 26 1.33784198761 0.0514554610619 31 1.55134892464 0.050043513698 36 1.74370908737 0.0484363635381 41 1.93989706039 0.0473145624486 46 2.13955497742 0.0465120647265 51 2.34015417099 0.0458853759018 56 2.54159998894 0.0453857140882 61 2.7404961586 0.0449261665344 66 2.96345996857 0.0449009086146 71 3.16043996811 0.0445132389875 76 3.35920596123 0.0442000784372 81 3.55862188339 0.0439336034987 86 3.76083993912 0.0437306969665 91 3.96302700043 0.0435497472574 96 4.16351914406 0.0433699910839
一样,一次函数不过原点. 拟合分析大概结论是0.04n+0.134. 注意,这个结论只分析了字符串长度为10的情况.
求解平衡点
令0.15n + 0.15 = 0.054n + 0.423 + 0.04n + 0.134,简化得0.056n=0.407. 在10个元素的级别concat和列表推导式join效率相仿. 这个和实验结果有差异,实验结果实际上要到n=100的量级才能近似.
根据无列表成本对比一节的分析,大数据下两者效率差应当近似于3:1. 这和0.15, 0.054, 0.04三个系数对不上号. 如果维持3:1的比例,平衡量级就到了n=100的级别. 怀疑其中一个系数测错了.
以上...
码不停提马上无虫 ;-)
|_|0|_| |_|_|0| |0|0|0|
加入 珠海GDG
- 注册 G+
- 关注 GDG Zhuhai
- 成为 GDG Zhuha开发者
通过 珠海GDG 可以:
第一时间获知谷歌最新的技术,
可以学到如何去谷歌平台上赚钱的思路和方法,
可以认识很多有可能将来一起走上自己创业道路的人,
可以学会把你的创新带向国际市场,
参加那里的活动有经常和国际上的开发者们进行交流的机会...
PS:
若无意外,题图都是从原文提取或是通过 Google 图片搜索出来的, 版权属左, 不负责任 ;-)
PPS:
珠海GDG wechat/Blog 都是欢迎投稿的,只要追认内容吻合以下条件:
0. 有趣 ~ 至少是自个儿有兴趣的领域吧... 1. 有料 ~ 至少有点儿原创的东西吧.. 2. 有种 ~ 至少不能是成功学吧!
有好物的,及时向大妈们吼: [email protected]
微信栏目
当前应该是:
G术图书 (gb:推荐好书,书无中外)
D码点评 (dd:麻辣评点,善意满盈)
G说公论 (gt:时评杂文,新旧不拘)
珠的自白(dm:大妈自述,每周一篇)
海选文章(hd:得要相信,大妈法眼)
总之! 珠海的组委大妈们,决定开始坚持发文,方方面面细细同大家分享/交流
总之! 请大家告诉大家, 珠海生活中的技术社区 已经认真回归 微信,都来订阅吧!
订阅方法
- 搜索微信号
GDG-ZhuHai - 或查找公众号:
GDG珠海 - 或扫描:
GDG珠海 社区资源:
- 邮件列表: [email protected] (可发空邮件到 [email protected] 即完成订阅)
- 微博: @GDG珠海
- 微信: GDG珠海
- G+ 主页: GDG ZhuHai
- G+ 社群: ZhuHai GDG
Author:
/mail
/
gittip
/
github
