周末在家花了半天時間寫了一個簡單的雙向循環(huán)鏈表蒋荚，為什么要這樣做莽鸭，一是想比較一下Python原生的list和雙向鏈表的性能差距是怎樣的司恳；二是看libuv的QUEUE源碼物遇，感覺libuv實(shí)現(xiàn)雙向循環(huán)鏈表的方式還是很優(yōu)雅的嫂丙，打算借用一下娘赴。
代碼地址：
https://github.com/Whosemario/ThinkIdeaEx/tree/master/python_list_ex
安裝
> python setup.py build_ext --inplace
本地會生成一個listex.so的動態(tài)鏈接庫。
性能對比
1.append方法
雙向循環(huán)鏈表測試代碼：
import time
import listex
li = listex.listex()
start_ts = time.time()
for i in xrange(0, 10000000):
li.append(i)
end_ts = time.time()
print "total time:", end_ts - start_ts
輸出結(jié)果如下：
total time: 2.71579694748
原生Python List測試代碼：
import time
import listex
li = listex.listex()
start_ts = time.time()
for i in xrange(0, 10000000):
li.append(i)
end_ts = time.time()
print "total time:", end_ts - start_ts
輸出結(jié)果如下：
total time: 1.8892519474
上面的結(jié)果可以看出來Python List的append的效率更高跟啤，這個是在意料之中的诽表，Python List向后插入本來性能就不差，原因是Python List在容量不足時候會擴(kuò)容隅肥，容量足夠的時候append的內(nèi)部實(shí)現(xiàn)就是數(shù)組賦值竿奏，性能肯定不差；而我的listex腥放，在每次插入一個PyObject的時候泛啸，都要malloc一個隊(duì)列節(jié)點(diǎn)（ListexNode）, 這個性能就會差很多了。
2.pop方法
原生Python List從下標(biāo)為0的地方pop出值：
import time
import listex
li = []
for i in xrange(0, 100000):
li.append(i)
start_ts = time.time()
for i in xrange(0, 100000):
li.pop(0)
end_ts = time.time()
print "total time:", end_ts - start_ts
輸出結(jié)果如下：
total time: 2.07851791382
使用listex秃症，獲取第一個listex node候址，并從隊(duì)列中剔除：
import time
import listex
li = listex.listex()
for i in xrange(0, 100000):
li.append(i)
start_ts = time.time()
for i in xrange(0, 100000):
li.get_head().remove()
end_ts = time.time()
print "total time:", end_ts - start_ts
輸出幾個如下：
total time: 0.0255160331726
這種情況雙向鏈表的優(yōu)勢就很明顯了吕粹，Python List每次都要從頭部pop出一個值，因此每次都要進(jìn)行數(shù)據(jù)的整體移動岗仑，性能就很耗了匹耕。
關(guān)于此工程
現(xiàn)在這個雙向鏈表的代碼還是不完整，后面將會持續(xù)更新荠雕。
