Python实现一个C版本的双向循环队列listex

周末在家花了半天时间写了一个简单的双向循环链表，为什么要这样做，一是想比较一下Python原生的list和双向链表的性能差距是怎样的；二是看libuv的QUEUE源码，感觉libuv实现双向循环链表的方式还是很优雅的，打算借用一下。

代码地址：https://github.com/Whosemario/ThinkIdeaEx/tree/master/python_list_ex

安装

> python setup.py build_ext --inplace

本地会生成一个listex.so的动态链接库。

性能对比

1.append方法

双向循环链表测试代码：

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

输出结果如下：

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

输出结果如下：

total time: 1.8892519474

上面的结果可以看出来Python List的append的效率更高，这个是在意料之中的，Python List向后插入本来性能就不差，原因是Python List在容量不足时候会扩容，容量足够的时候append的内部实现就是数组赋值，性能肯定不差；而我的listex，在每次插入一个PyObject的时候，都要malloc一个队列节点（ListexNode）, 这个性能就会差很多了。

2.pop方法

原生Python List从下标为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

输出结果如下：

total time: 2.07851791382

使用listex，获取第一个listex node，并从队列中剔除：

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

这种情况双向链表的优势就很明显了，Python List每次都要从头部pop出一个值，因此每次都要进行数据的整体移动，性能就很耗了。

关于此工程

现在这个双向链表的代码还是不完整，后面将会持续更新。