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

  1. 注册 G+
  2. 关注 GDG Zhuhai
  3. 成为 GDG Zhuha开发者

通过 珠海GDG 可以:

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

PS:

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

PPS:

珠海GDG wechat/Blog 都是欢迎投稿的,只要追认内容吻合以下条件:

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

有好物的,及时向大妈们吼: [email protected]

微信栏目

当前应该是:

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

总之! 珠海的组委大妈们,决定开始坚持发文,方方面面细细同大家分享/交流

总之! 请大家告诉大家, 珠海生活中的技术社区 已经认真回归 微信,都来订阅吧!

订阅方法

GDG珠海 社区资源:


Author: Zoom.Quiet /mail / gittip / github