如何加速python的执行

Question

我有一个文本文件，有4623行，条目的形式是0和1的字符串（例如01010111）。我在一个字一个字地比较他们。我有几个字符串长度为1001000和10000的数据集。1000需要25小时，10000需要60小时来计算。有没有办法加快速度？我尝试使用多处理库，但它只是复制值。也许我用错了。代码：

f = open("/path/to/file/file.txt", 'r')
l = [s.strip('\n') for s in f]
f.close()

for a in range(0, len(l)):
    for b in range(0, len(l)):
        if (a < b):
            result = 0
            if (a == b):
                result = 1
            else:
                counter = 0
            for i in range(len(l[a])):
                if (int(l[a][i]) == int(l[b][i]) == 1):
                    counter += 1
            result = counter / 10000   
            print((a + 1), (b + 1), result)

我是python新手，所以我认为这段代码需要一些优化。任何帮助都是好的。提前谢谢。你知道吗

Answer 1

基础知识

两个字符串都是1的情况下，你的计数方式非常慢。下面是一个简单的例子：

In [24]: a = '1010' * 2500

In [25]: b = '1100' * 2500

In [27]: def test1():
    counter = 0            
    for i in range(len(a)):
        if int(a[i]) == int(b[i]) == 1:
            counter += 1
    return counter

In [28]: %timeit test1()
100 loops, best of 3: 4.07 ms per loop

将其与仅将1和0的字符串表示为位的字符串进行比较：

In [29]: aba = bitarray(a)

In [30]: bba = bitarray(b)

In [31]: def test2():
   ....:     return (aba & bba).count()
   ....: 

In [32]: %timeit test2()

100000 loops, best of 3: 1.99 µs per loop

这比以前快了2045倍。所以问题不是如何加速python，而是“我应该使用什么样的数据结构？”。你知道吗

规模更大

使用bitarray和一个包含10000行1001和0的文件，这不是最坏的情况，但是：

In [22]: from bitarray import bitarray

In [23]: testdata = open('teststrs.txt')

In [24]: l = [bitarray(line.rstrip()) for line in testdata]

In [25]: len(l)
Out[25]: 10000

In [26]: len(l[0])
Out[26]: 100

In [27]: combs = combinations(l, 2)

In [28]: %time res = [(a & b[:len(a)]).count() for a, b in combs]
CPU times: user 1min 14s, sys: 396 ms, total: 1min 15s
Wall time: 1min 15s

或者使用产品，如示例代码中所示：

In [30]: from itertools import product

In [31]: prod = product(l, repeat=2)

In [32]: %time res = [(a & b[:len(a)]).count() for a, b in prod]
CPU times: user 2min 51s, sys: 628 ms, total: 2min 52s
Wall time: 2min 51s

注意：

我跳过了您的结果处理，因为您尚未打开它，而且它包含死代码：

if a == b:

永远不会是True，因为在前面如果您选中a < b。我认为你有缩进或逻辑错误，意思是：

    if a < b:
        result = 0
    elif a == b:
        result = 1
    else:
        counter = 0
        for i in range(len(l[a])):
            if (int(l[a][i]) == int(l[b][i]) == 1):
                counter += 1
        result = counter / 10000
    print((a + 1), (b + 1), result)

“真实”数据

最坏的情况，如果我理解正确的话：

In [1]: src = map(lambda i: '{:010000b}\n'.format(i), iter(lambda: random.getrandbits(10000), None))

In [2]: import random

In [3]: from itertools import islice

In [4]: with open('teststrs.txt', 'w') as datafile:
    datafile.writelines(islice(src, 0, 4623))

...

In [35]: testdata = open('teststrs.txt')

In [36]: l = [bitarray(line.rstrip()) for line in testdata]

In [37]: prod = product(l, repeat=2)

In [38]: %time res = [(a & b).count() for a, b in prod]
CPU times: user 52.1 s, sys: 424 ms, total: 52.5 s
Wall time: 52.5 s

In [39]: len(l)
Out[39]: 4623

In [40]: len(l[0])
Out[40]: 10000

注意，我作弊并跳过了切片b。移动所有的内存是非常昂贵的，切片可以创建新的拷贝：

In [43]: %time res = [(a & b[:len(a)]).count() for a, b in prod]
CPU times: user 29min 40s, sys: 676 ms, total: 29min 41s
Wall time: 29min 40s

因此，如果您事先知道了最大位宽度，或者甚至根据数据计算出最大位宽度，我认为用零填充较短的位数组，然后进行整个“计数1”是有益的：

In [18]: def test():                     
    with open('teststrs.txt') as testdata:
        lines = [line.strip() for line in testdata]
    max_len = max(map(len, lines))
    l = [bitarray(line.ljust(max_len, '0')) for line in lines]
    prod = product(l, repeat=2)
    return [(a & b).count() for a, b in prod]
   ....: 

In [19]: %timeit test()
1 loops, best of 3: 43.9 s per loop

这里teststrs.txt文件由4623个1'和0'的混合长度（随机选择100、1000或10000）串组成