周末在家花了半天時(shí)間寫了一個(gè)簡(jiǎn)單的雙向循環(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
本地會(huì)生成一個(gè)listex.so的動(dòng)態(tài)鏈接庫(kù)。
性能對(duì)比
1.append方法
雙向循環(huán)鏈表測(cè)試代碼：
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測(cè)試代碼：
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的效率更高，這個(gè)是在意料之中的，Python List向后插入本來性能就不差，原因是Python List在容量不足時(shí)候會(huì)擴(kuò)容，容量足夠的時(shí)候append的內(nèi)部實(shí)現(xiàn)就是數(shù)組賦值，性能肯定不差；而我的listex，在每次插入一個(gè)PyObject的時(shí)候，都要malloc一個(gè)隊(duì)列節(jié)點(diǎn)（ListexNode）, 這個(gè)性能就會(huì)差很多了。
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，獲取第一個(gè)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
輸出幾個(gè)如下：
total time: 0.0255160331726
這種情況雙向鏈表的優(yōu)勢(shì)就很明顯了，Python List每次都要從頭部pop出一個(gè)值，因此每次都要進(jìn)行數(shù)據(jù)的整體移動(dòng)，性能就很耗了。
關(guān)于此工程
現(xiàn)在這個(gè)雙向鏈表的代碼還是不完整，后面將會(huì)持續(xù)更新。
