O problema

Eu tenho brincado com diferentes maneiras (no Python 2.7) para extrair uma lista de tuplas (palavra, frequência) de um corpus, ou lista de strings, e comparando sua eficiência. Tanto quanto eu posso dizer, no caso normal, com uma lista não classificada, oCountermétodo docollections O módulo é superior a qualquer coisa que eu tenha encontrado ou encontrado em outro lugar, mas parece que não tira muito proveito dos benefícios de uma lista pré-ordenada e eu desenvolvi métodos que a superam facilmente neste caso especial . Então, em resumo, existe alguma maneira interna de informarCounter do fato de que uma lista já está classificada para acelerar ainda mais?

(A próxima seção é em listas não ordenadas, onde Counter funciona como mágica; você pode querer pular para o final, onde perderá seu charme ao lidar com listas ordenadas.)

Listas de entrada não ordenadasUma abordagem que não funciona

A abordagem ingênua seria usarsorted([(word, corpus.count(word)) for word in set(corpus)]), mas aquele confia-lo em problemas de tempo de execução, logo que o seu corpo é de alguns milhares de itens de comprimento - não é de estranhar, já que você está correndo pela lista inteira de palavras muitas vezes, onde m é o número de palavras únicas.

Classificando a lista + pesquisa local

Então, o que eu tentei fazer antes de encontrarCounter Certifique-se de que todas as pesquisas são estritamente locais, primeiro classificando a lista de entrada (eu também tenho que remover dígitos e pontuação e converter todas as entradas em letras minúsculas para evitar duplicatas como 'foo', 'Foo' e '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

Encontrarcollections.Counter

Isso é muito melhor, mas ainda não é tão rápido quanto usar a classe Counter do módulo collections, que cria um dicionário de {palavra: frequência de palavra} entradas (ainda temos que fazer o mesmo descarte e redução, mas nenhuma classificação) :

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

No corpus de Gutenberg com aprox. 2 milhões de entradas, o método Counter é aproximadamente 30% mais rápido na minha máquina (5 segundos em oposição a 7.2), o que é explicado principalmente pela rotina de ordenação que consome cerca de 2.1 segundos (se você não tem e não quer instalar o pacote nltk (Natural Language Toolkit), que oferece acesso a este corpus, qualquer outro texto adequadamente longo, apropriadamente dividido em uma lista de strings no nível da palavra, mostrará o mesmo.

Comparando desempenho

Com o meu método idiossincrático de temporização usando a tautologia como uma condição para atrasar a execução, isso nos dá o método do 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 o último passo, o de formatar os resultados como uma lista de tuplas, ocupa menos de 5% do tempo total.)

Comparado com minha função:

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

Listas de entrada ordenadas - quandoCounter 'falha'

No entanto, como você deve ter notado, minha função permite especificar que a entrada já está classificada, despojada de lixo pontual e convertida em minúsculas. Se já criamos uma versão convertida da lista para outras operações, usá-la (e declará-la) pode acelerar muito a operação do meu computador.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

Aqui, reduzimos o tempo de execução por um fator de appr. 8 por não ter que ordenar o corpus e converter os itens. Claro que o último também é verdade quando a alimentaçãoCounter com essa nova lista, portanto, é também um pouco mais rápido, mas parece que não aproveita o fato de ser classificada e agora demora o dobro da minha função, onde era 30% mais rápida 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

Claro, podemos usar a mesma lógica que eu useiwordcount5 - incrementar um contador local até encontrarmos uma nova palavra e só depois armazenar a última palavra com o estado atual do contador e redefinir o contador para 0 para a próxima palavra - usando somenteCounter como armazenamento, mas a eficiência inerente doCounter o método parece perdido, e o desempenho está dentro do alcance da minha função para criar um dicionário, com o fardo extra de converter para uma lista de tuplas agora parecendo mais problemática do que costumava ser quando estávamos processando o corpus 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

(A semelhança dos resultados não é realmente surpreendente, pois estamos desabilitandoCounterpróprios métodos e abusando dele como uma loja para valores obtidos com a mesma metodologia de antes.)

Portanto, minha pergunta: existe uma maneira mais idiomática de informarCounter que sua lista de entrada já está classificada e para manter a chave atual na memória, em vez de procurá-la sempre que - previsivelmente - encontrar o próximo símbolo da mesma palavra? Em outras palavras,É possível melhorar ainda mais o desempenho em uma lista pré-classificada, combinando a eficiência inerenteCounter/dictionary classe com os benefícios óbvios de uma lista classificada, ou já estou arranhando um limite rígido com 0,9 segundos para registrar uma lista de entradas de 2 milhões?

Provavelmente não há muito espaço para melhorias - eu tenho tempos em torno de 0,5 segundos quando faço a coisa mais simples que eu posso pensar que ainda requer iteração através da mesma lista e verificação de cada valor individual, e 0,25 paraset(corpus) sem uma conta, mas talvez haja alguma mágica lá fora que ajudaria a chegar perto desses números?

(Nota: sou um novato relativamente ao Python e à programação em geral, então desculpe se eu perdi alguma coisa óbvia).

Editar 1 de dezembro:

Outra coisa, além da própria classificação, que torna todos os meus métodos acima lentos, é converter cada uma das strings de 2M em minúsculas e retirá-las de qualquer pontuação ou dígitos que elas possam incluir. Eu tentei antes para o atalho, contando as seqüências de caracteres não processadas e só então converter os resultados e remover duplicatas ao somar suas contagens, mas devo ter feito algo de errado para isso tornou as coisas um pouco mais lentas. Portanto, reverti para as versões anteriores, convertendo tudo no corpus bruto, e agora não consigo reconstruir o que fiz lá.

Se eu tentar agora, eu recebo uma melhoria da conversão das strings por último. Eu ainda estou fazendo isso através de uma lista (de resultados). O que fiz foi escrever algumas funções que iriam converter as chaves na saída do método default_dict de J.F. Sebastian (de formato[("word", int), ("Word", int)], ("word2", int),...]) em letras minúsculas e tira-os da pontuação, e reduz as contagens de todas as chaves que foram deixadas idênticas após essa operação (código abaixo). A vantagem é que agora estamos lidando com uma lista de aproximadamente 50 mil entradas, em oposição às> 2M no corpus. Desta forma, estou agora em 1,25 segundos para ir do corpus (como uma lista) para uma contagem de palavras sem distinção entre maiúsculas e minúsculas, ignorando os sinais de pontuação na minha máquina, de 4.5 com o método Counter e conversão de string como primeiro passo. Mas talvez haja um método baseado em dicionário para o que estou fazendosum_sorted() também?

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()))

Eu fiz algumas primeiras tentativas de usar groupy para fazer o trabalho feito atualmente porsum_sorted()e / oustriplast(), mas eu não consegui descobrir como enganar isso[entry[1]] para uma lista de entradas emcount_words'resultados classificados porentry[0]. O mais perto que cheguei foi:

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