Почему Collections.counter так медленно?

Question

Я пытаюсь решить основную задачу Rosalind о подсчете нуклеотидов в данной последовательности и возвращать результаты в списке. Для тех, кто не знаком с биоинформатикой, он просто подсчитывает количество вхождений четырех разных символов («A», «C», «G», «T») внутри строки.

Я ожидал, что collections.Counter будет самым быстрым методом (во-первых, потому что они утверждают, что они высокопроизводительные, а во-вторых, потому что я видел много людей, использующих его для этой конкретной проблемы).

Но, к моему удивлению, этот метод является самым медленным!

я сравнил три различных метода, используя timeit и работает два типа экспериментов:

• Запуск длинной последовательности несколько раз
• Запуск короткой последовательности много раз.

Вот мой код:

import timeit 
from collections import Counter 

# Method1: using count 
def method1(seq): 
    return [seq.count('A'), seq.count('C'), seq.count('G'), seq.count('T')] 

# method 2: using a loop 
def method2(seq): 
    r = [0, 0, 0, 0] 
    for i in seq: 
     if i == 'A': 
      r[0] += 1 
     elif i == 'C': 
      r[1] += 1 
     elif i == 'G': 
      r[2] += 1 
     else: 
      r[3] += 1 
    return r 

# method 3: using Collections.counter 
def method3(seq): 
    counter = Counter(seq) 
    return [counter['A'], counter['C'], counter['G'], counter['T']] 


if __name__ == '__main__': 

    # Long dummy sequence 
    long_seq = 'ACAGCATGCA' * 10000000 
    # Short dummy sequence 
    short_seq = 'ACAGCATGCA' * 1000 

    # Test 1: Running a long sequence once 
    print timeit.timeit("method1(long_seq)", setup='from __main__ import method1, long_seq', number=1) 
    print timeit.timeit("method2(long_seq)", setup='from __main__ import method2, long_seq', number=1) 
    print timeit.timeit("method3(long_seq)", setup='from __main__ import method3, long_seq', number=1) 

    # Test2: Running a short sequence lots of times 
    print timeit.timeit("method1(short_seq)", setup='from __main__ import method1, short_seq', number=10000) 
    print timeit.timeit("method2(short_seq)", setup='from __main__ import method2, short_seq', number=10000) 
    print timeit.timeit("method3(short_seq)", setup='from __main__ import method3, short_seq', number=10000) 

Результаты:

Test1: 
Method1: 0.224009990692 
Method2: 13.7929501534 
Method3: 18.9483819008 

Test2: 
Method1: 0.224207878113 
Method2: 13.8520510197 
Method3: 18.9861831665 

Метод 1 является способ быстрее чем метод 2 и 3 для обоих экспериментов !!

Поэтому у меня есть ряд вопросов:

• я делаю что-то неправильно, или это действительно медленнее, чем в двух других подходов? Может ли кто-нибудь запустить тот же код и поделиться результатами?

• Если мои результаты верны, (и, возможно, это должен быть другой вопрос), существует ли более быстрый способ решить эту проблему, чем при использовании метода 1?

• Если count быстрее, то в чем дело с collections.Counter?

Answer 1

Это не потому, что collections.Counter медленно, на самом деле это довольно быстро, но это общий инструмент цели, подсчет символов является лишь одним из многих приложений.

С другой стороны, str.count просто подсчитывает символы в строках и его сильно оптимизирован для своей задачи.

Это означает, что str.count может работать на подстилающей C- char массива в то время как он может не создавать новые (или отрываясь существующих) длина-1-питон-строки во время итерации (что for и Counter делать).

---

Просто добавьте еще несколько контекстов к этому утверждению.

Строка хранится как массив C, обернутый как объект python.str.count знает, что строка является непрерывным массивом и, таким образом, преобразует символ, который вы хотите использовать, к символу C-, затем выполняет итерацию по массиву в собственном C-коде и проверяет равенство и, наконец, обертывает и возвращает количество найденных вхождений ,

С другой стороны, for и Counter используют протокол python-iteration-protocol. Каждый символ вашей строки будет обернут как объект python, а затем он (хеши и) сравнивает их в python.

Так что замедление происходит потому, что:

• Каждый символ должен быть преобразован в объект Python (это основная причина потери производительности)
• Петля выполняется в Python (не относится к Counter в питона 3.x, потому что он был переписан в C)
• Каждое сравнение должно быть сделано в Python (вместо того, чтобы просто сравнивающих чисел в C - символы представлены цифрами)
• счетчик должен хэш значения и ваша петля нуждается в i ndex ваш список.

---

Примечание причина замедления похожа на вопрос о Why are Python's arrays slow?.

---

Я сделал некоторые дополнительные тесты, чтобы выяснить, в какой момент collections.Counter должна быть более str.count предпочитали. Для этого я создал случайные строки, содержащие различные количества уникальных персонажей и график производительности:

from collections import Counter 
import random 
import string 

characters = string.printable # 100 different printable characters 

results_counter = [] 
results_count = [] 
nchars = [] 

for i in range(1, 110, 10): 
    chars = characters[:i] 
    string = ''.join(random.choice(chars) for _ in range(10000)) 
    res1 = %timeit -o Counter(string) 
    res2 = %timeit -o {char: string.count(char) for char in chars} 
    nchars.append(len(chars)) 
    results_counter.append(res1) 
    results_count.append(res2) 

и результат построена с использованием matplotlib:

import matplotlib.pyplot as plt 

plt.figure() 

plt.plot(nchars, [i.best * 1000 for i in results_counter], label="Counter", c='black') 
plt.plot(nchars, [i.best * 1000 for i in results_count], label="str.count", c='red') 
plt.xlabel('number of different characters') 
plt.ylabel('time to count the chars in a string of length 10000 [ms]') 
plt.legend() 

Результаты для Python 3.5

Результаты для Python 3.6 очень похожи, поэтому я не перечислял их явно.

Так что, если вы хотите посчитать 80 различных символов Counter становится быстрее/сравнимые, поскольку она пересекает строку только один раз, а не несколько раз, как str.count. Это будет слабо зависеть от длины строки (но тестирование показало лишь очень слабую разницу +/- 2%).

Результаты для Python 2.7

В Python-2.7 collections.Counter были реализованы с использованием Python (вместо C) и гораздо медленнее. Точка безубыточности для str.count и Counter может быть оценена только путем экстраполяции, потому что даже со 100 различными символами str.count все еще в 6 раз быстрее.

Answer 2

Разница во времени здесь довольно проста для объяснения. Все сводится к тому, что работает внутри Python и что работает как собственный код. Последний всегда будет быстрее, поскольку на нем не будет много накладных расходов.

Теперь это уже причина, по которой вызов str.count() четыре раза быстрее, чем что-либо еще. Хотя это итерация строки четыре раза, эти циклы выполняются в собственном коде. str.count реализован на C, поэтому это очень мало накладных расходов, что делает это очень быстро. Это действительно сложно превзойти, особенно когда задача такая простая (только для простого равенства символов).

Вашего второй метод сбора отсчетов в массиве на самом деле является менее производительной версией следующего:

def method4 (seq): 
    a, c, g, t = 0, 0, 0, 0 
    for i in seq: 
     if i == 'A': 
      a += 1 
     elif i == 'C': 
      c += 1 
     elif i == 'G': 
      g += 1 
     else: 
      t += 1 
    return [a, c, g, t] 

Здесь все четыре значения отдельными переменные, поэтому обновление их очень быстро. Это на самом деле немного быстрее, чем мутирующие элементы списка.

Общая производительность «проблема» здесь, однако, что это итерации строки в Python. Таким образом, это создает итератор строки, а затем производит каждый символ отдельно как фактический строковый объект. Это много накладных расходов и основная причина, почему каждое решение, которое работает путем итерации строки в Python, будет медленнее.

Эта проблема возникает с collection.Counter. Это implemented in Python, поэтому, несмотря на то, что он очень эффективен и гибкий, он страдает от той же проблемы, что он никогда не приближается к родным с точки зрения скорости.