从140秒到2秒的优化
浏览:2991次 出处信息
从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内,收工。
建议继续学习:
- WEB系统需要关注的一些点 (阅读:14064)
- 30分钟3300%性能提升――python+memcached网页优化小记 (阅读:12110)
- 基于SSD的数据库性能优化 (阅读:7385)
- jQuery性能优化指南 (阅读:7303)
- 一次简单C程序的性能优化 (阅读:5582)
- mysql sql 百万级数据库优化方案 (阅读:5034)
- 一次神奇的MySQL优化 (阅读:4870)
- PHP最佳实践 (阅读:4921)
- Linux 64位, MySQL, Swap & Memory 优化 (阅读:4460)
- PHP 性能优化技巧-google (阅读:4388)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:倒置字符串中的单词
后一篇:C/C++循环获取文件中的每行数据(别以为很简单!) >>
文章信息
- 作者:超群.com 来源: 超群.com的博客
- 标签: 优化
- 发布时间:2009-11-18 13:14:14
建议继续学习
近3天十大热文
- [67] Go Reflect 性能
- [67] Oracle MTS模式下 进程地址与会话信
- [67] 如何拿下简短的域名
- [61] IOS安全–浅谈关于IOS加固的几种方法
- [60] 图书馆的世界纪录
- [59] 【社会化设计】自我(self)部分――欢迎区
- [58] android 开发入门
- [56] 视觉调整-设计师 vs. 逻辑
- [49] 给自己的字体课(一)——英文字体基础
- [47] 界面设计速成