技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 从140秒到2秒的优化

从140秒到2秒的优化

浏览:3004次  出处信息

从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内,收工。

建议继续学习:

  1. WEB系统需要关注的一些点    (阅读:14247)
  2. 30分钟3300%性能提升――python+memcached网页优化小记    (阅读:12224)
  3. 基于SSD的数据库性能优化    (阅读:7487)
  4. jQuery性能优化指南    (阅读:7382)
  5. 一次简单C程序的性能优化    (阅读:5645)
  6. mysql sql 百万级数据库优化方案    (阅读:5118)
  7. 一次神奇的MySQL优化    (阅读:4971)
  8. PHP最佳实践    (阅读:5074)
  9. Linux 64位, MySQL, Swap & Memory 优化    (阅读:4562)
  10. PHP 性能优化技巧-google    (阅读:4521)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1