ordereddict python 3 example

¿Por qué Collections.counter es tan lento?

Question

Estoy tratando de resolver el problema básico de Rosalind de contar nucleótidos en una secuencia dada y devolver los resultados en una lista. (Para aquellos que no están familiarizados con la bioinformática, solo cuentan el número de ocurrencias de 4 caracteres diferentes (''A'', ''C'', ''G'', ''T'') dentro de una cadena)

Esperaba que Collections.counter fuera el método más rápido (primero porque dicen ser de alto rendimiento, y segundo porque vi a mucha gente usándolo para este problema específico).

Pero para mi sorpresa este método es el más lento !!

Comparé tres métodos diferentes, usando timeit y ejecutando dos tipos de experimentos:

• Ejecutando una larga secuencia pocas veces
• Ejecutando una secuencia corta muchas veces.

Aquí está mi código:

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)

Resultados:

Test1:
Method1: 0.224009990692
Method2: 13.7929501534
Method3: 18.9483819008
Test2:
Method1: 0.224207878113
Method2: 13.8520510197
Method3: 18.9861831665

¡El Método 1 es MUCHO más rápido que los métodos 2 y 3 para ambos experimentos!

Entonces tengo una serie de preguntas:

¿Estoy haciendo algo mal o de hecho es más lento que los otros dos enfoques? ¿Podría alguien ejecutar el mismo código y compartir los resultados?

-En caso de que mis resultados sean correctos, (y tal vez esta debería ser otra pregunta) ¿Hay un método más rápido para resolver este problema que usar method1?

-Si la cuenta es mucho más rápida, ¿cuál es el trato con Collections.counter?

Answer 1

La diferencia de tiempo aquí es bastante simple de explicar. Todo se reduce a lo que se ejecuta dentro de Python y lo que se ejecuta como código nativo. Este último siempre será más rápido, ya que no viene con una gran cantidad de gastos de evaluación.

Ahora esa es la razón por la que llamar a str.count() cuatro veces es más rápido que cualquier otra cosa. Aunque esto itera la cadena cuatro veces, estos bucles se ejecutan en código nativo. str.count se implementa en C, por lo que tiene muy poca carga, lo que hace que sea muy rápido. Es realmente difícil superar esto, especialmente cuando la tarea es así de simple (buscando solo la igualdad de caracteres simples).

Su segundo método para recopilar los recuentos en una matriz es en realidad una versión menos eficiente de lo siguiente:

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]

Aquí, los cuatro valores son variables individuales, por lo que su actualización es muy rápida. Esto es en realidad un poco más rápido que mutar los artículos de la lista.

Sin embargo, el "problema" de rendimiento general aquí es que esto itera la cadena dentro de Python . Así que esto crea un iterador de cadena y luego produce cada carácter individualmente como un objeto de cadena real. Eso es mucho sobrecargado y la razón principal por la cual cada solución que funciona al iterar la cadena en Python será más lenta.

El mismo problema es con la collection.Counter . collection.Counter . Está implementado en Python, por lo que a pesar de que es muy eficiente y flexible, adolece del mismo problema que nunca es casi nativo en términos de velocidad.

Answer 2

No es porque collections.Counter . El contador es lento, en realidad es bastante rápido, pero es una herramienta de propósito general, contar caracteres es solo una de muchas aplicaciones.

Por otro lado, str.count solo cuenta los caracteres en cadenas y está muy optimizado para su única tarea.

Eso significa que str.count puede trabajar en la matriz de C- char subyacente, mientras que puede evitar la creación de nuevas (o buscando) cadenas de longitud-1-python existentes durante la iteración (que es lo que for y Counter do).

Solo para agregar un poco más de contexto a esta afirmación.

Una cadena se almacena como matriz C envuelta como objeto python. The str.count sabe que la cadena es una matriz contigua y, por lo tanto, convierte el carácter que desea co en un C- "carácter", luego itera sobre la matriz en código C nativo y verifica la igualdad y finalmente se ajusta y devuelve el número de encontrado ocurrencias.

Por otro lado, for Counter use el protocolo python-iteration. Cada carácter de su cadena será envuelto como python-object y luego (hashes y) los compara dentro de python.

Entonces la desaceleración es porque:

• Cada personaje tiene que convertirse en un objeto de Python (esta es la razón principal de la pérdida de rendimiento)
• El ciclo está hecho en Python (no aplicable a Counter en python 3.x porque fue reescrito en C)
• Cada comparación debe hacerse en Python (en lugar de simplemente comparar números en C, los caracteres están representados por números)
• El contador necesita ajustar los valores y tu ciclo necesita indexar tu lista.

Tenga en cuenta que el motivo de la ralentización es similar a la pregunta sobre ¿Por qué las matrices de Python son lentas? .

Hice algunos puntos de referencia adicionales para averiguar en qué punto collections.Counter debe ser str.count sobre str.count . Para este fin creé cadenas aleatorias que contenían diferentes cantidades de caracteres únicos y tracé el rendimiento:

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)

y el resultado fue trazado usando 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()

Resultados para Python 3.5

Los resultados para Python 3.6 son muy similares, así que no los listé explícitamente.

Entonces, si desea contar 80 caracteres diferentes, Counter vuelve más rápido / comparable porque atraviesa la cadena solo una vez y no varias veces como str.count . Esto dependerá débilmente de la longitud de la cuerda (pero las pruebas mostraron solo una diferencia muy débil +/- 2%).

Resultados para Python 2.7

En Python-2.7 collections.Counter se implementó usando python (en lugar de C) y mucho más lento. El punto de str.count para str.count y Counter solo se puede estimar por extrapolación, ya que incluso con 100 caracteres diferentes, la str.count es 6 veces más rápida.