从140秒到2秒的优化
November 12th, 2009 | by 超群.com | 知识共享署名-非商业性使用-相同方式共享，转载请保留链接。从2亿个0~2,000,000,000之间的数字样本中找出不重复的记录总数，首先想到的是bloom filter，转念一想既然全都是数字，bloom filter有点太重，bitarray也许更有效，于是第一个版本出来，部分代码如下：
ba = bitarray(212**4) cnt = 0 for i in data: if (not ba[i]): cnt += 1 ba[i] = True print cnt
大概需要140s左右，觉得if (not ba[i]):这个比较费，改了第二版：
for i in data: ba[i] = True print ba.count()
速度有所提升，到了120s左右，开始打起多核运算的主意了，山寨了一个map-reduce，首先通过maper把数据按照除4得余分成4份：
def maper(data): map_data = (array('I'),array('I'),array('I'),array('I')) for i in data: m = i % 4 map_data[m].append(i) return map_data
然后起了一个4个进程的woker pool分别计算，最后把结果汇总：
def worker(data): counter = bitarray(256**4) for i in data:counter[i] = True return counter.count() p = Pool(4) result = p.map(worker, data)
速度提高明显，到了50s左右，这个做法的问题是两次遍历：map的时候一次、reduce的时候又一次，于是开始想办法解决，把文件直接分开运算，不再map，把最后的结果做一下位或再计数：
p = Pool(4) result = p.map(worker, data) print (result[0] | result[1] | result[2] | result[3]).count()
到了26s左右，可能Python在进程间交换大数据量效率不是太好，再优化的空间有限，想起之前用Python的科学运算库做过数据挖掘，能不能用那个库试试，于是有了NumPy的版本：
import numpy as np print len(np.unique(np.fromfile('/path/to/data.dat', np.uint32)))
全部程序就这两行，速度到了12s，让人崩溃，NumPy的底层大多是C的实现，对代码做了一个profile，发现NumPy用了sort，有点浪费，如果我用C实现一部分功能的话效果应该会不错，注意到代码中有for i in data，data中有2亿条，就循环调用了2亿次，尝试把这个调用都封装在C里面，使用C级别的循环，于是用C扩展了一下bitarray包：
static PyObject * bitarray_fromarray(bitarrayobject *self, PyObject *pyo) { unsigned int *l; idx_t n1; Py_ssize_t nbytes, nitems, i; if (PyObject_AsReadBuffer(pyo, (const void **)&l, &nbytes) != 0) return Py_False; nitems = nbytes/sizeof(unsigned int); for (i=0; i<nitems; i++) { *(self->ob_item + l[i] / 8) |= ((char) 1) << (l[i])%8; } n1 = count(self); return PyLong_FromLongLong(n1); }
直接读取文件buffer到bitarray，python程序就变成了：
from bitarray import bitarray counter = bitarray(212 ** 4) fp = open('/path/to/data.datbk', 'rb') un = counter.fromarray(fp.read()) print un
一共5行代码，速度到了2s内，收工。
8 Responses to “从140秒到2秒的优化”
By 小宝 on Nov 13, 2009 | Reply
强悍！
By Yoyo on Nov 13, 2009 | Reply
的确厉害，强烈学习中
By est on Nov 13, 2009 | Reply
所以还是C快。。。
By sexla on Nov 14, 2009 | Reply
话说我是代码盲
By jackywdx on Nov 15, 2009 | Reply
博主很博学啊。仰望一下^_^
By 小明 on Nov 17, 2009 | Reply
你越来越牛了，赞。
By xLight on Nov 24, 2009 | Reply
和静态语言比循环速度吗？
By 超群.com on Nov 25, 2009 | Reply
@xLight
没有，这个不敢，我把循环包含在C这个level了。