¿Por qué las colecciones son mucho más lentas que ” .count?

Tengo una tarea simple: contar cuántas veces aparece cada letra en una cadena. He usado un Counter() para eso, pero en un foro vi información de que usar dict() / Counter() es mucho más lento que usar string.count() para cada letra. Pensé que iba a interactuar a través de la cadena solo una vez, y la solución string.count() tendría que string.count() cuatro veces (en este caso). ¿Por qué el Counter() tan lento?

 >>> timeit.timeit('x.count("A");x.count("G");x.count("C");x.count("T")', setup="x=''", number=10000) 0.07911698750407936 >>> timeit.timeit('Counter(x)', setup="from collections import Counter;x=''", number=10000) 2.1727447831030844 >>> 2.1727447831030844 / 0.07911698750407936 27.462430656767047 >>> 

Counter() permite contar cualquier objeto hashable, no solo subcadenas. Ambas soluciones son tiempo O(n) . Sus mediciones muestran que la sobrecarga de iteración y hash de caracteres individuales por Counter() es mayor que ejecutar s.count() 4 veces.

Counter() puede usar C helper para contar elementos, pero parece que no tiene cadenas de casos especiales y usa el algoritmo general aplicable para cualquier otro iterable, es decir, el procesamiento de un solo carácter implica múltiples llamadas a la API de Python C para avanzar el iterador, obtener un valor previo ( una búsqueda en la tabla hash), contador de incrementos, establecer un nuevo valor (una búsqueda en la tabla hash) :

  while (1) { key = PyIter_Next(it); if (key == NULL) break; oldval = PyObject_GetItem(mapping, key); if (oldval == NULL) { if (!PyErr_Occurred() || !PyErr_ExceptionMatches(PyExc_KeyError)) break; PyErr_Clear(); Py_INCREF(one); newval = one; } else { newval = PyNumber_Add(oldval, one); Py_DECREF(oldval); if (newval == NULL) break; } if (PyObject_SetItem(mapping, key, newval) == -1) break; Py_CLEAR(newval); Py_DECREF(key); } 

Compárelo con la FASTSEARCH() de FASTSEARCH() para las secuencias de bytes:

  for (i = 0; i < n; i++) if (s[i] == p[0]) { count++; if (count == maxcount) return maxcount; } return count; 

La clase Counter hereda de dict , mientras que string.count es la siguiente implementación de C (CPython 3.3):

 /* stringlib: count implementation */ #ifndef STRINGLIB_FASTSEARCH_H #error must include "stringlib/fastsearch.h" before including this module #endif Py_LOCAL_INLINE(Py_ssize_t) STRINGLIB(count)(const STRINGLIB_CHAR* str, Py_ssize_t str_len, const STRINGLIB_CHAR* sub, Py_ssize_t sub_len, Py_ssize_t maxcount) { Py_ssize_t count; if (str_len < 0) return 0; /* start > len(str) */ if (sub_len == 0) return (str_len < maxcount) ? str_len + 1 : maxcount; count = FASTSEARCH(str, str_len, sub, sub_len, maxcount, FAST_COUNT); if (count < 0) return 0; /* no match */ return count; } 

Adivina, ¿cuál es más rápido? 🙂