¿Hay una manera de hacer que las colecciones.Counter (Python2.7) tenga en cuenta que su lista de entrada está ordenada?

El problema

He estado jugando con diferentes formas (en Python 2.7) para extraer una lista de tuplas (palabra, frecuencia) de un corpus, o lista de cadenas, y comparar su eficiencia. Por lo que puedo decir, en el caso normal con una lista sin clasificar, el método de Counter del módulo de collections es superior a cualquier cosa que haya encontrado o encontrado en otro lugar, pero no parece aprovechar mucho los beneficios. de una lista pre-ordenada y he encontrado métodos que lo superan fácilmente en este caso especial. Entonces, en resumen, ¿hay alguna forma integrada de informar a Counter del hecho de que una lista ya está ordenada para acelerarla más?

(La siguiente sección es en listas sin clasificar donde Counter trabaja con magia; es posible que desee saltar hacia el final donde pierde su encanto cuando se trata de listas ordenadas).

Listas de entrada sin clasificar

Un enfoque que no funciona.

El enfoque ingenuo sería usar sorted([(word, corpus.count(word)) for word in set(corpus)]) , pero uno de ellos le pone de manera confiable en problemas de tiempo de ejecución tan pronto como su corpus tenga unos pocos miles de elementos. – no es sorprendente ya que está repasando la lista completa de n palabras m muchas veces, donde m es el número de palabras únicas.

Ordenar la lista + búsqueda local

Entonces, lo que intenté hacer antes de encontrar Counter era asegurarse de que todas las búsquedas sean estrictamente locales al ordenar primero la lista de entrada (también tengo que eliminar los dígitos y los signos de puntuación y convertir todas las entradas en minúsculas para evitar duplicados como ‘foo’ , ‘Foo’, y ‘foo:’).

 #Natural Language Toolkit, for access to corpus; any other source for a long text will do, though. import nltk # nltk corpora come as a class of their own, as I udnerstand it presenting to the # outside as a unique list but underlyingly represented as several lists, with no more # than one ever loaded into memory at any one time, which is good for memory issues # but rather not so for speed so let's disable this special feature by converting it # back into a conventional list: corpus = list(nltk.corpus.gutenberg.words()) import string drop = string.punctuation+string.digits def wordcount5(corpus, Case=False, lower=False, StrippedSorted=False): '''function for extracting word frequencies out of a corpus. Returns an alphabetic list of tuples consisting of words contained in the corpus with their frequencies. Default is case-insensitive, but if you need separate entries for upper and lower case spellings of the same words, set option Case=True. If your input list is already sorted and stripped of punctuation marks/digits and/or all lower case, you can accelerate the operation by a factor of 5 or so by declaring so through the options "Sorted" and "lower".''' # you can ignore the following 6 lines for now, they're only relevant with a pre-processed input list if lower or Case: if StrippedSorted: sortedc = corpus else: sortedc = sorted([word.replace('--',' ').strip(drop) for word in sorted(corpus)]) # here we sort and purge the input list in the default case: else: sortedc = sorted([word.lower().replace('--',' ').strip(drop) for word in sorted(corpus)]) # start iterating over the (sorted) input list: scindex = 0 # create a list: freqs = [] # identify the first token: currentword = sortedc[0] length = len(sortedc) while scindex < length: wordcount = 0 # increment a local counter while the tokens == currentword while scindex < length and sortedc[scindex] == currentword: scindex += 1 wordcount += 1 # store the current word and final score when a) a new word appears or # b) the end of the list is reached freqs.append((currentword, wordcount)) # if a): update currentword with the current token if scindex < length: currentword = sortedc[scindex] return freqs 

Encontrar collections.Counter

Esto es mucho mejor, pero aún no es tan rápido como usar la clase Counter del módulo de colecciones, que crea un diccionario de entradas de {palabra: frecuencia de palabra} (todavía tenemos que hacer el mismo borrado y reducción, pero sin ordenación) :

 from collections import Counter cnt = Counter() for word in [token.lower().strip(drop) for token in corpus]: cnt[word] += 1 # optionally, if we want to have the same output format as before, # we can do the following which negligibly adds in runtime: wordfreqs = sorted([(word, cnt[word]) for word in cnt]) 

En el corpus de Gutenberg con aprox. 2 millones de entradas, el método de Contador es aproximadamente un 30% más rápido en mi máquina (5 segundos en lugar de 7.2), lo que se explica principalmente a través de la rutina de clasificación que consume alrededor de 2.1 segundos (si no tiene y no quiere instale el paquete nltk (Natural Language Toolkit) que ofrece acceso a este corpus, cualquier otro texto adecuadamente largo que se divida apropiadamente en una lista de cadenas a nivel de palabra le mostrará lo mismo.)

Comparando el rendimiento

Con mi método idiosincrásico de temporización utilizando la tautología como condicional para retrasar la ejecución, esto nos da para el método de contador:

 import time >>> if 1: ... start = time.time() ... cnt = Counter() ... for word in [token.lower().strip(drop) for token in corpus if token not in [" ", ""]]: ... cnt[word] += 1 ... time.time()-start ... cntgbfreqs = sorted([(word, cnt[word]) for word in cnt]) ... time.time()-start ... 4.999882936477661 5.191655874252319 

(Vemos que el último paso, el de dar formato a los resultados como una lista de tuplas, ocupa menos del 5% del tiempo total).

En comparación con mi función:

 >>> if 1: ... start = time.time() ... gbfreqs = wordcount5(corpus) ... time.time()-start ... 7.261770963668823 

Listas de entrada ordenadas: cuando el Counter “falla”

Sin embargo, como puede haber notado, mi función permite especificar que la entrada ya está ordenada, despojada de basura puntual y convertida a minúsculas. Si ya hemos creado una versión convertida de la lista para otras operaciones, usarla (y declararlo así) puede acelerar mucho el funcionamiento de mi wordcount5 :

 >>> sorted_corpus = sorted([token.lower().strip(drop) for token in corpus if token not in [" ", ""]]) >>> if 1: ... start = time.time() ... strippedgbfreqs2 = wordcount5(sorted_corpus, lower=True, StrippedSorted=True) ... time.time()-start ... 0.9050078392028809 

Aquí, hemos reducido el tiempo de ejecución por un factor de apr. 8 por no tener que ordenar el corpus y convertir los ítems. Por supuesto, esto último también es cierto cuando se alimenta a Counter con esta nueva lista, por lo que es de esperar que también sea un poco más rápido, pero no parece aprovecharse del hecho de que está ordenado y ahora toma el doble de tiempo que mi función donde está Fue 30% más rápido que antes:

 >>> if 1: ... start = time.time() ... cnt = Counter() ... for word in sorted_corpus: ... cnt[word] += 1 ... time.time()-start ... strippedgbfreqs = [(word, cnt[word])for word in cnt] ... time.time()-start ... 1.9455058574676514 2.0096349716186523 

Por supuesto, podemos usar la misma lógica que usé en wordcount5 : incrementar un contador local hasta que encontremos una nueva palabra y luego almacenar la última palabra con el estado actual del contador y restablecer el contador a 0 para la siguiente palabra – solo uso Counter como almacenamiento, pero la eficiencia inherente del método Counter parece haberse perdido, y el rendimiento está dentro del rango de mi función para crear un diccionario, con la carga adicional de convertir a una lista de tuplas que ahora parece más problemática de lo que usaba Cuando estábamos procesando el corpus crudo:

 >>> def countertest(): ... start = time.time() ... sortedcnt = Counter() ... c = 0 ... length = len(sorted_corpus) ... while c < length: ... wcount = 0 ... word = sorted_corpus[c] ... while c < length and sorted_corpus[c] == word: ... wcount+=1 ... c+=1 ... sortedcnt[word] = wcount ... if c >> strippedbgcnt = countertest() 0.920727014542 1.08029007912 

(La similitud de los resultados no es realmente sorprendente, ya que estamos inhabilitando los métodos propios de Counter y abusando de ellos como una reserva de valores obtenidos con la misma metodología que antes).

Por lo tanto, mi pregunta: ¿Existe una forma más idiomática de informar a Counter que su lista de entrada ya está ordenada y, por lo tanto, mantener la clave actual en la memoria en lugar de buscarla cada vez que, de manera predecible, encuentra el siguiente token de misma palabra? En otras palabras, ¿ es posible mejorar aún más el rendimiento en una lista pre-ordenada combinando la eficiencia inherente de la clase de Counter / dictionary con los beneficios obvios de una lista ordenada , o ya estoy superando un límite duro con .9 segundos? ¿Para contar una lista de entradas de 2M?

Es probable que no haya mucho margen de mejora: tengo tiempos de alrededor de .55 segundos cuando hago la cosa más simple que puedo pensar que aún requiere iterar a través de la misma lista y verificar cada valor individual, y .25 para el set(corpus) sin un recuento, pero tal vez haya algo de magia de itertools que ayude a acercarse a esas cifras.

(Nota: soy un principiante relativo de Python y de la progtwigción en general, así que disculpe si me he perdido algo obvio).

Edición del 1 de diciembre:

Otra cosa, además de la clasificación en sí misma, que hace que todos mis métodos anteriores sean lentos, es convertir cada una de las cadenas 2M en minúsculas y eliminarlas de cualquier puntuación o número de dígitos que puedan incluir. Antes he tratado de hacer un atajo al contar las cadenas no procesadas y solo luego convertir los resultados y eliminar los duplicados al sumr sus cuentas, pero debo haber hecho algo mal porque hizo que las cosas fueran un poco más lentas. Por lo tanto, volví a las versiones anteriores, convirtiendo todo en el corpus en bruto, y ahora no puedo reconstruir lo que hice allí.

Si lo bash ahora, obtengo una mejora al convertir las cadenas en último lugar. Todavía lo estoy haciendo en bucle sobre una lista (de resultados). Lo que hice fue escribir un par de funciones que convertirían las claves en la salida del método default_dict ganador de JF Sebastian (de formato [("word", int), ("Word", int)], ("word2", int),...] ) en minúsculas, elimínelos de puntuación y reduzca los recuentos de todas las claves que quedaron idénticas después de esa operación (código a continuación). La ventaja es que ahora estamos manejando una lista de aproximadamente 50k entradas en lugar de> 2M en el corpus. De esta manera, ahora tengo 1,25 segundos para pasar del corpus (como una lista) a un recuento de palabras que no distingue entre mayúsculas y minúsculas, ignorando los signos de puntuación en mi máquina, por debajo de aproximadamente 4.5 con el método de Contador y la conversión de cadenas como primer paso. ¿Pero quizás hay un método basado en el diccionario para lo que estoy haciendo en sum_sorted() también?

Código:

 def striplast(resultlist, lower_or_Case=False): """function for string conversion of the output of any of the `count_words*` methods""" if lower_or_Case: strippedresult = sorted([(entry[0].strip(drop), entry[1]) for entry in resultlist]) else: strippedresult = sorted([(entry[0].lower().strip(drop), entry[1]) for entry in resultlist]) strippedresult = sum_sorted(strippedresult) return strippedresult def sum_sorted(inputlist): """function for collapsing the counts of entries left identical by striplast()""" ilindex = 0 freqs = [] currentword = inputlist[0][0] length = len(inputlist) while ilindex < length: wordcount = 0 while ilindex < length and inputlist[ilindex][0] == currentword: wordcount += inputlist[ilindex][1] ilindex += 1 if currentword not in ["", " "]: freqs.append((currentword, wordcount)) if ilindex  currentword: currentword = inputlist[ilindex][0] return freqs def count_words_defaultdict2(words, loc=False): """modified version of JF Sebastian's winning method, added a final step collapsing the counts for words identical except for punctuation and digits and case (for the latter, unless you specify that you're interested in a case-sensitive count by setting l(ower_)o(r_)c(ase) to True) by means of striplast().""" d = defaultdict(int) for w in words: d[w] += 1 if col=True: return striplast(sorted(d.items()), lower_or_case=True) else: return striplast(sorted(d.items())) 

Hice algunos bashs iniciales de usar groupy para hacer el trabajo que actualmente realiza sum_sorted() y / o striplast() , pero no pude encontrar la forma de engañarlo para que sume [entry[1]] para obtener una lista de entradas en count_words ‘resultados ordenados por entry[0] . Lo más cerca que conseguí fue:

 # "i(n)p(ut)list", toylist for testing purposes: list(groupby(sorted([(entry[0].lower().strip(drop), entry[1]) for entry in iplist]))) # returns: [(('a', 1), ), (('a', 2), ), (('a', 3), ), (('a', 5), ), (('a', 8), ), (('b', 3), ), (('b', 7), )] # So what I used instead for striplast() is based on list comprehension: list(sorted([(entry[0].lower().strip(drop), entry[1]) for entry in iplist])) # returns: [('a', 1), ('a', 2), ('a', 3), ('a', 5), ('a', 8), ('b', 3), ('b', 7)] 

Dada una lista ordenada de palabras como mencionas, ¿has probado el enfoque tradicional de Pythonic de itertools.groupby ?

 from itertools import groupby some_data = ['a', 'a', 'b', 'c', 'c', 'c'] count = dict( (k, sum(1 for i in v)) for k, v in groupby(some_data) ) # or count = {k:sum(1 for i in v) for k, v in groupby(some_data)} # {'a': 2, 'c': 3, 'b': 1} 

Para responder a la pregunta del título: Counter, dict, defaultdict, OrderedDict son tipos basados ​​en hash: para buscar un elemento, calculan un hash para una clave y lo utilizan para obtener el elemento. Incluso admiten teclas que no tienen un orden definido, siempre y cuando tengan capacidad de mantenimiento, es decir, Counter no puede aprovechar las entradas pre-ordenadas.

Las mediciones muestran que la clasificación de las palabras de entrada lleva más tiempo que contar las palabras utilizando un enfoque basado en el diccionario y ordenar el resultado combinado:

 sorted 3.19 count_words_Counter 2.88 count_words_defaultdict 2.45 count_words_dict 2.58 count_words_groupby 3.44 count_words_groupby_sum 3.52 

Además, el conteo de palabras en entradas ya ordenadas con groupby() toma solo una fracción del tiempo que toma ordenar las entradas en primer lugar y más rápido que los enfoques basados ​​en dict.

 def count_words_Counter(words): return sorted(Counter(words).items()) def count_words_groupby(words): return [(w, len(list(gr))) for w, gr in groupby(sorted(words))] def count_words_groupby_sum(words): return [(w, sum(1 for _ in gr)) for w, gr in groupby(sorted(words))] def count_words_defaultdict(words): d = defaultdict(int) for w in words: d[w] += 1 return sorted(d.items()) def count_words_dict(words): d = {} for w in words: try: d[w] += 1 except KeyError: d[w] = 1 return sorted(d.items()) def _count_words_freqdist(words): # note: .items() returns words sorted by word frequency (descreasing order) # (same as `Counter.most_common()`) # so the code sorts twice (the second time in lexicographical order) return sorted(nltk.FreqDist(words).items()) 

Para reproducir los resultados, ejecute este código .

Nota: Es 3 veces más rápido si la secuencia perezosa de palabras de nltk se convierte en una lista ( WORDS = list(nltk.corpus.gutenberg.words()) pero el rendimiento relativo es el mismo:

 sorted 1.22 count_words_Counter 0.86 count_words_defaultdict 0.48 count_words_dict 0.54 count_words_groupby 1.49 count_words_groupby_sum 1.55 

Los resultados son similares a los de Python. ¿Es un diccionario lento para encontrar la frecuencia de cada personaje? .

Si desea normalizar las palabras (eliminar puntuación, hacerlas en minúsculas, etc.); vea las respuestas en ¿Cuál es la forma más eficiente en Python para convertir una cadena en minúsculas, eliminando todos los caracteres alfa que no sean ascii? . Algunos ejemplos:

 def toascii_letter_lower_genexpr(s, _letter_set=ascii_lowercase): """ >>> toascii_letter_lower_genexpr("ABC,-.!def") 'abcdef' """ return ''.join(c for c in s.lower() if c in _letter_set) def toascii_letter_lower_genexpr_set(s, _letter_set=set(ascii_lowercase)): return ''.join(c for c in s.lower() if c in _letter_set) def toascii_letter_lower_translate(s, table=maketrans(ascii_letters, ascii_lowercase * 2), deletechars=''.join(set(maketrans('', '')) - set(ascii_letters))): return s.translate(table, deletechars) def toascii_letter_lower_filter(s, _letter_set=set(ascii_letters)): return filter(_letter_set.__contains__, s).lower() 

Para contar y normalizar las palabras simultáneamente:

 def combine_counts(items): d = defaultdict(int) for word, count in items: d[word] += count return d.iteritems() def clean_words_in_items(clean_word, items): return ((clean_word(word), count) for word, count in items) def normalize_count_words(words): """Normalize then count words.""" return count_words_defaultdict(imap(toascii_letter_lower_translate, words)) def count_normalize_words(words): """Count then normalize words.""" freqs = count_words_defaultdict(words) freqs = clean_words_in_items(toascii_letter_lower_translate, freqs) return sorted(combine_counts(freqs)) 

Resultados

He actualizado el punto de referencia para medir varias combinaciones de count_words*() y toascii*() (no se muestran los pares 5×4):

 toascii_letter_lower_filter 0.954 usec small toascii_letter_lower_genexpr 2.44 usec small toascii_letter_lower_genexpr_set 2.19 usec small toascii_letter_lower_translate 0.633 usec small toascii_letter_lower_filter 124 usec random 2000 toascii_letter_lower_genexpr 197 usec random 2000 toascii_letter_lower_genexpr_set 121 usec random 2000 toascii_letter_lower_translate 7.73 usec random 2000 sorted 1.28 sec count_words_Counter 941 msec count_words_defaultdict 501 msec count_words_dict 571 msec count_words_groupby 1.56 sec count_words_groupby_sum 1.64 sec count_normalize_words 622 msec normalize_count_words 2.18 sec 

Los métodos más rápidos:

  • normalizar palabras – toascii_letter_lower_translate()

  • palabras de conteo (entrada groupby() – enfoque basado en groupby()

  • contar palabras – count_words_defaultdict()

  • es más rápido primero contar las palabras y luego normalizarlas – count_normalize_words()

Última versión del código: count-words-performance.py .

Una fuente de ineficiencia en el código del OP (que varias respuestas solucionaron sin comentar) es el exceso de confianza en las listas intermedias. No hay razón para crear una lista temporal de millones de palabras solo para iterar sobre ellas, cuando un generador funcionará.

Así que en lugar de

 cnt = Counter() for word in [token.lower().strip(drop) for token in corpus]: cnt[word] += 1 

debería ser justo

 cnt = Counter(token.lower().strip(drop) for token in corpus) 

Y si realmente quiere ordenar los recuentos de palabras alfabéticamente (¿para qué?), Reemplace esto

 wordfreqs = sorted([(word, cnt[word]) for word in cnt]) 

con este:

 wordfreqs = sorted(cnt.items()) # In Python 2: cnt.iteritems() 

Esto debería eliminar gran parte de la ineficiencia en el uso de Counter (o cualquier clase de diccionario usada de manera similar).