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, elCountermétodo de lacollections El módulo 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 informarCounter ¿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 clasificarUn enfoque que no funciona.

El enfoque ingenuo sería utilizarsorted([(word, corpus.count(word)) for word in set(corpus)]), pero ese problema te lleva de manera confiable a problemas de tiempo de ejecución tan pronto como tu corpus tiene unos pocos miles de elementos, lo que no es sorprendente ya que estás 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

Así que lo que intenté hacer antes de encontrarCounter fue 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

Hallazgocollections.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 - cuandoCounter '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 dicha versión convertida de la lista para algunas otras operaciones, usarla (y declararlo así) puede acelerar mucho el funcionamiento de miwordcount5:

>>> 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.Counter con esta nueva lista, 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 era un 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é enwordcount5 - Incrementar un contador local hasta que nos encontremos con 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 usarCounter como almacenamiento, pero la eficiencia inherente de laCounter El método parece 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 solía ser cuando procesábamos el corpus en bruto:

>>> 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 < length:
...             word = sorted_corpus[c]
...     print time.time()-start
...     return sorted([(word, sortedcnt[word]) for word in sortedcnt])
...     print time.time()-start
... 
>>> strippedbgcnt = countertest()
0.920727014542
1.08029007912

(La similitud de los resultados no es realmente sorprendente ya que estamos inhabilitando en efectoCounterde los métodos propios y abusando de él como un almacén para los valores obtenidos con la misma metodología que antes.)

Por lo tanto, mi pregunta: ¿Hay una manera más idiomática de informarCounter ¿Su lista de entrada ya está ordenada y, por lo tanto, para mantener la clave actual en la memoria en lugar de volver a buscarla cada vez que, de manera previsible, se encuentra con el siguiente token de la misma palabra? En otras palabras,¿Es posible mejorar aún más el rendimiento en una lista pre-ordenada combinando la eficiencia inherente de laCounter/dictionary Clase con los beneficios obvios de una lista ordenada.¿O ya estoy raspando un límite duro con .9 segundos para contar una lista de entradas de 2M?

Probablemente 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 paraset(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 programació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 sumar 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 intento 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 J.F. Sebastian (del formato[("word", int), ("Word", int)], ("word2", int),...]) en minúsculas, elimínelos de puntuación y contraiga 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 del contador y la conversión de cadenas como primer paso. Pero tal vez hay un método basado en el diccionario para lo que estoy haciendo ensum_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 < length and inputlist[ilindex][0] > currentword:
            currentword = inputlist[ilindex][0]
    return freqs

def count_words_defaultdict2(words, loc=False): 
    """modified version of J.F. 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 intentos iniciales de usar groupy para hacer el trabajo que actualmente realizasum_sorted()y / ostriplast(), pero no pude encontrar la manera de engañarlo para sumar[entry[1]] para una lista de entradas encount_words'resultados ordenados porentry[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), <itertools._grouper object at 0x1031bb290>), (('a', 2), <itertools._grouper object at 0x1031bb250>), (('a', 3), <itertools._grouper object at 0x1031bb210>), (('a', 5), <itertools._grouper object at 0x1031bb2d0>), (('a', 8), <itertools._grouper object at 0x1031bb310>), (('b', 3), <itertools._grouper object at 0x1031bb350>), (('b', 7), <itertools._grouper object at 0x1031bb390>)]

# 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)]