Perché collections.Counter è molto più lento di ".count?

Question

Ho un compito semplice: contare quante volte ogni lettera si verifica in una stringa. Ho usato uno Counter() per questo, ma su un forum ho visto le informazioni che utilizzando dict()/Counter() è molto più lento rispetto all'utilizzo di string.count() per ogni lettera. Ho pensato che sarebbe intervenuto attraverso la stringa solo una volta, e la soluzione string.count() avrebbe dovuto iterarlo per quattro volte (in questo caso). Perché lo Counter() è così lento?

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

Answer 1

Counter() consente di contare qualsiasi oggetto lavabile, non solo sottostringhe. Entrambe le soluzioni sono O(n) -time. Le tue misurazioni mostrano che il sovraccarico di iterazione e hashing dei singoli caratteri di Counter() è maggiore di quello di eseguire s.count() 4 volte.

Counter()può uso C aiutante per contare elementi, ma a quanto pare lo fa stringhe non particolari casi e utilizza l'algoritmo generale applicabile per qualsiasi altro iterabile cioè, processing a single character involves multiple Python C API calls to advance the iterator, get previous value (a lookup in the hash table), increment counter, set new value (a lookup in the hash table):

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); 
    } 

confrontarlo con FASTSEARCH() overhead per i bytrest:

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

Answer 2

La classe Counter eredita da dict, mentre string.count è il seguente C-implementazione (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; 
} 

Guess, che uno è più veloce? :)