Python 列表开销优化

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):

723090629108
74334951208
610983964173
627904584411
594889465838
576456981387
587058850443
574822100807
571444616501
558473461852
553502716806
54686361629
542239744063
550127440675
558543129789
55148314297
544658859149
537840854175
550946275219
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):

:

0.0476880073547 0.0476880073547
0.420774936676 0.00825048895443
0.769494771957 0.00761876011839
1.0588850975 0.00701248408943
1.32135987282 0.00657392971551
1.59451413155 0.00635264594241
1.87293815613 0.00622238590076
2.16326808929 0.00616315694956
2.44224190712 0.00609037882075
2.71852707863 0.00602777622756
3.00196099281 0.00599193810941
3.29650497437 0.00598276764858
3.61599302292 0.00601662732599
3.91590690613 0.00601521798176
4.13701701164 0.00590159345455
4.40393304825 0.00586409194174
4.7007830143 0.00586864296417
4.96966505051 0.00583979441893
5.25287795067 0.00583005321939
5.54418587685 0.00582984845094

注意,以上数据的timeit为100000,不是文章里常用的1000000

list的重分配逻辑和dict类似. 我这里有一篇python中dict的插入复杂度估算和排重复杂度估算,说明list的插入成本大约应该是O(1)级别. 单纯来看似乎并不吻合.

使用matplotlib对曲线做拟合,发现应当是一条不过原点的方程,拟合后方程应为O=0.0054n+0.0423. 拟合曲线还是略有点奇怪,怀疑是因为list在低段数据下复制不均匀所致. 不过原点的原因很简单,还有list生成开销呢.

0.0464599132538 0.0477 0.974002374293
0.420957803726 0.3177 1.32501669413
0.722836017609 0.5877 1.22994047577
1.0100440979 0.8577 1.17761932832
1.27215504646 1.1277 1.12809705282
1.55443191528 1.3977 1.11213559082
1.84508705139 1.6677 1.10636628374
2.12424898148 1.9377 1.09627340738
2.40401697159 2.2077 1.08892375395
2.68004202843 2.4777 1.08166526554
2.94087600708 2.7477 1.07030462098
3.21941900253 3.0177 1.06684528036
3.52912306786 3.2877 1.07343220727
3.79638195038 3.5577 1.06708883559
4.0689470768 3.8277 1.06302664179
4.35646104813 4.0977 1.06314787518
4.62156105042 4.3677 1.05812236427
4.87002706528 4.6377 1.05009531994
5.17770791054 4.9077 1.05501719961
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):

0.0361330509186 0.0361330509186
0.0786919593811 0.026230653127
0.0982298851013 0.0196459770203
0.126276016235 0.0180394308908
0.157994031906 0.017554892434
0.189352989197 0.0172139081088
0.217918872833 0.0167629902179
0.249435186386 0.0166290124257
0.285101890564 0.0167706994449
0.313716888428 0.0165114151804
0.343729019165 0.0163680485317
0.38047504425 0.0165423932283
0.433068990707 0.0173227596283
0.471400976181 0.0174592954141
0.531830787659 0.0183389926779
0.578590869904 0.0186642216098
0.606976985931 0.0183932419979
0.633711099625 0.0181060314178
0.65832901001 0.0177926759462
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

0.173592090607 0.173592090607
0.434324979782 0.0723874966304
0.630973815918 0.0573612559925
0.830116987228 0.0518823117018
1.0301399231 0.0490542820522
1.33784198761 0.0514554610619
1.55134892464 0.050043513698
1.74370908737 0.0484363635381
1.93989706039 0.0473145624486
2.13955497742 0.0465120647265
2.34015417099 0.0458853759018
2.54159998894 0.0453857140882
2.7404961586 0.0449261665344
2.96345996857 0.0449009086146
3.16043996811 0.0445132389875
3.35920596123 0.0442000784372
3.55862188339 0.0439336034987
3.76083993912 0.0437306969665
3.96302700043 0.0435497472574
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的级别. 怀疑其中一个系数测错了.

巡阅

150113 Zoom.Quiet checked

2013-05-28

声明: 本文采用 BY-NC-SA 授权。转载请注明转自: #ZHGDG#

以上...

加入珠海GDG

注册 Meetup
关注 Zhuhai GDG
或扫描:

通过珠海GDG 可以:

    第一时间获知谷歌最新技术,
    可以学到如何去谷歌平台上赚钱的思路和方法,
    可以认识很多有可能将来一起走上自己创业道路的人,
    可以学会把你的创新带向国际市场,
    参加那里的活动有经常和国际上的开发者们进行交流的机会...

PS:

若无意外,题图都是从原文提取或是通过 Google 图片搜索出来的, 版权属左, 不负责任 ;-)

PPS:

珠海GDG 微信/Blog 欢迎投稿,只要追自认内容吻合以下条件:

0. 有趣 ~ 至少是自个儿有兴趣的领域吧...
1. 有料 ~ 至少有点儿原创的东西吧..
2. 有种 ~ 至少不能是成功学吧!

有好物请及时通过邮件列表投稿成也: [email protected]
(发空邮件到 [email protected] 即完成订阅)

微信公号

栏目设定:

    G术图书 (gb:推荐好书,书无中外)
    D码点评 (dd:麻辣评点,善意满盈)
    G说公论 (gt:时评杂文,新旧不拘)
    珠的自白(dm:大妈自述,每周一篇)
    海选文章(hd:得要相信,大妈法眼)

总之, 请大家告诉大家, 珠海生活中的技术社区 都来订阅呗 ;-)

订阅方法

搜索微信号 GDG-ZhuHai
或查找公众号: GDG珠海
或扫描:

GDG珠海社区资源:

邮件列表: [email protected] (可发空邮件到 [email protected] 即完成订阅)
微信: GDG珠海
博客: 珠海GDG | GDG Livin ZhuHai Life;-)

大妈的多重宇宙 - YouTube

全新自媒体系列...科学幻想,读书,说故事...

点击注册~> 获得 100$ 体验券:

订阅 substack 体验古早写作:
Zoom.Quiet’s Chaos42 | Substack

关注公众号, 持续获得相关各种嗯哼:
zoomquiet

蟒营®编程思维提高班Python版

**2021.01.11** 因大妈再次创业暂停定期开设, 转换为预约触发:

+ 任何问题, 随时邮件提问可也:
```
[email protected]
```