Как ускорить выполнение python

Question

У меня есть текстовый файл с 4623 строками и строками в форме строки 0 и 1 (например, 01010111). Я сравниваю их по характеру. У меня есть несколько наборов данных с длиной строки символов 100, 1000 и 10000. Требуется 25 часов для 1000 и 60 часов для расчета 10 000. Есть ли способ ускорить его? Я пытался использовать многопроцессорную библиотеку, но она просто дублирует значения. Возможно, я использую это неправильно. Код:

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 строк 100 1 и 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) 

«Real» Данные

С вашим худшем случае, если я правильно понял:

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 

Так что, если вы знаете максимальную разрядность заранее, или даже вычислить его из данных Я думаю, что было бы полезно для прокладки короткие bitarrays с нулями, а затем сделать все «подсчитывать 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 смешанных длин (случайный выбор 100, 1000 или 10000) строк 1 'и 0'.