Das Problem

Ich habe auf verschiedene Arten (in Python 2.7) herumgespielt, um eine Liste von (Wort-, Häufigkeits-) Tupeln aus einem Korpus oder einer Liste von Zeichenfolgen zu extrahieren und ihre Effizienz zu vergleichen. Soweit ich das beurteilen kann, wird im Normalfall bei einer unsortierten Liste dieCounterMethode aus demcollections Das Modul ist allem überlegen, was ich mir ausgedacht oder woanders gefunden habe, aber es scheint die Vorteile einer vorsortierten Liste nicht besonders zu nutzen, und ich habe Methoden entwickelt, die es in diesem speziellen Fall leicht übertreffen . Also, kurz gesagt, gibt es eine eingebaute Möglichkeit zu informierenCounter von der Tatsache, dass eine Liste bereits sortiert ist, um sie weiter zu beschleunigen?

(Der nächste Abschnitt befasst sich mit unsortierten Listen, in denen Counter auf magische Weise arbeitet. Sie können zum Ende springen, wo es beim Umgang mit sortierten Listen seinen Reiz verliert.)

Unsortierte EingabelistenEin Ansatz, der nicht funktioniert

Der naive Ansatz wäre zu verwendensorted([(word, corpus.count(word)) for word in set(corpus)]), aber dieser bringt Sie zuverlässig in Laufzeitprobleme, sobald Ihr Korpus einige tausend Elemente lang ist - nicht überraschend, da Sie die gesamte Liste von n Wörtern m oft durchlaufen, wobei m die Anzahl der eindeutigen Wörter ist.

Sortieren der Liste + lokale Suche

Also, was habe ich stattdessen versucht, bevor ich gefunden habeCounter Stellen Sie sicher, dass alle Suchanfragen ausschließlich lokal sind, indem Sie zuerst die Eingabeliste sortieren (ich muss auch Ziffern und Satzzeichen entfernen und alle Einträge in Kleinbuchstaben umwandeln, um Duplikate wie 'foo', 'Foo' und 'foo:' zu vermeiden). .

#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

Findencollections.Counter

Dies ist viel besser, aber immer noch nicht so schnell wie die Verwendung der Counter-Klasse aus dem Collections-Modul, die ein Wörterbuch mit {word: frequency of word} -Einträgen erstellt (wir müssen immer noch das gleiche Stripping und Lowering durchführen, aber keine Sortierung). :

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

Auf dem Gutenbergkorpus mit ca. Mit 2 Millionen Einträgen ist die Zählermethode auf meinem Computer ungefähr 30% schneller (5 Sekunden im Gegensatz zu 7,2), was hauptsächlich durch die Sortierroutine erklärt wird, die ungefähr 2,1 Sekunden dauert (wenn Sie keine haben und nicht wollen) Installieren Sie das nltk-Paket (Natural Language Toolkit), das Zugriff auf dieses Korpus bietet. Jeder andere ausreichend lange Text, der in eine Liste von Zeichenfolgen auf Wortebene aufgeteilt ist, zeigt dasselbe an.)

Leistung vergleichen

Mit meiner eigenwilligen Methode des Timings unter Verwendung der Tautologie als Bedingung für die Verzögerung der Ausführung ergibt sich für die Zählermethode Folgendes:

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

(Wir sehen, dass der letzte Schritt, das Formatieren der Ergebnisse als Tupelliste, weniger als 5% der Gesamtzeit in Anspruch nimmt.)

Im Vergleich zu meiner Funktion:

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

Sortierte Eingabelisten - wannCounter 'scheitert'

Wie Sie vielleicht bemerkt haben, können Sie mit meiner Funktion festlegen, dass die Eingabe bereits sortiert, vom Satzzeichenmüll befreit und in Kleinbuchstaben konvertiert wird. Wenn wir bereits eine solche konvertierte Version der Liste für einige andere Operationen erstellt haben, kann die Verwendung (und Deklaration) der Liste die Operation von my sehr beschleunigenwordcount5:

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

Hier haben wir die Laufzeit um den Faktor ca. reduziert. 8, indem Sie den Korpus nicht sortieren und die Elemente konvertieren müssen. Letzteres gilt natürlich auch beim FütternCounter Mit dieser neuen Liste ist es wahrscheinlich auch ein bisschen schneller, aber es scheint die Tatsache nicht auszunutzen, dass es sortiert ist und jetzt doppelt so lange dauert wie meine Funktion, bei der es zuvor 30% schneller war:

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

Natürlich können wir die gleiche Logik verwenden, die ich verwendet habewordcount5 - Inkrementieren eines lokalen Zählers, bis wir auf ein neues Wort stoßen, und erst dann Speichern des letzten Wortes mit dem aktuellen Zustand des Zählers und Zurücksetzen des Zählers auf 0 für das nächste Wort - nur unter Verwendung vonCounter als Speicher, aber die inhärente Effizienz derCounter Die Methode scheint verloren zu sein, und die Leistung liegt innerhalb des Bereichs meiner Funktionen zum Erstellen eines Wörterbuchs. Die zusätzliche Belastung durch das Konvertieren in eine Liste von Tupeln ist jetzt problematischer als früher bei der Verarbeitung des Rohkorpus:

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

(Die Ähnlichkeit der Ergebnisse ist nicht wirklich überraschend, da wir sie tatsächlich deaktivierenCountereigene Methoden und missbrauchen sie als Speicher für Werte, die mit der gleichen Methode wie zuvor erhalten wurden.)

Daher meine Frage: Gibt es eine idiomatischere Art zu informierenCounter dass seine Eingabeliste bereits sortiert ist und damit der aktuelle Schlüssel im Speicher bleibt, anstatt ihn jedes Mal neu aufzusuchen, wenn er - vorhersehbar - auf das nächste Token desselben Wortes stößt? Mit anderen Worten,ist es möglich, die Leistung auf einer vorsortierten Liste weiter zu verbessern, indem die inhärente Effizienz derCounter/dictionary Klasse mit den offensichtlichen Vorteilen einer sortierten Liste, oder kratze ich bereits mit 0,9 Sekunden an einem harten Limit, um eine Liste mit 2 Millionen Einträgen zu zählen?

Wahrscheinlich gibt es nicht viel Raum für Verbesserungen - ich bekomme Zeiten von etwa 0,55 Sekunden, wenn ich das einfachste mache, was ich mir vorstellen kann, dass es immer noch erforderlich ist, die gleiche Liste zu durchlaufen und jeden einzelnen Wert zu überprüfen, und 0,25 fürset(corpus) ohne Zählung, aber vielleicht gibt es da draußen ein paar magische Werkzeuge, die helfen, diesen Zahlen näher zu kommen?

(Hinweis: Ich bin ein Anfänger in Bezug auf Python und das Programmieren im Allgemeinen. Entschuldigen Sie, wenn ich etwas Offensichtliches verpasst habe.)

1. Dez. bearbeiten:

Abgesehen von der eigentlichen Sortierung, die alle meine oben genannten Methoden verlangsamt, besteht eine weitere Aufgabe darin, jede einzelne 2M-Zeichenfolge in Kleinbuchstaben umzuwandeln und alle möglichen Satzzeichen oder Ziffern zu entfernen. Ich habe vorher versucht, dies zu verkürzen, indem ich die unverarbeiteten Zeichenfolgen gezählt habe und dann die Ergebnisse konvertiert und Duplikate entfernt habe, während ich ihre Anzahl addiert habe, aber ich muss etwas falsch gemacht haben, um die Dinge etwas langsamer zu machen. Ich bin daher zu den vorherigen Versionen zurückgekehrt, habe alles im Rohkorpus konvertiert und kann jetzt nicht ganz rekonstruieren, was ich dort getan habe.

Wenn ich es jetzt versuche, bekomme ich eine Verbesserung, wenn ich die Zeichenfolgen zuletzt konvertiere. Ich mache es immer noch, indem ich eine Liste (der Ergebnisse) durchlaufe. Was ich getan habe, war ein paar Funktionen zu schreiben, die die Schlüssel in der Ausgabe von J.F. Sebastians gewinnender default_dict-Methode (of format) konvertieren würden[("word", int), ("Word", int)], ("word2", int),...]) in Kleinbuchstaben und entfernen Sie die Satzzeichen. Reduzieren Sie dann die Anzahl aller Schlüssel, die nach dieser Operation noch identisch waren (Code unten). Der Vorteil ist, dass wir jetzt eine Liste von ungefähr 50.000 Einträgen bearbeiten, im Gegensatz zu den> 2 Millionen Einträgen im Korpus. Auf diese Weise habe ich jetzt 1,25 Sekunden Zeit, um vom Korpus (als Liste) zu einer Wortzählung überzugehen, bei der die Interpunktionszeichen auf meinem Computer ignoriert werden, von ungefähr 4,5 mit der Counter-Methode und der Zeichenfolgenkonvertierung als erstem Schritt. Aber vielleicht gibt es eine wörterbuchbasierte Methode für das, was ich machesum_sorted() auch?

Code:

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

Ich habe einige erste Versuche unternommen, Groupy zu verwenden, um die Aufgabe zu erledigen, die derzeit von ausgeführt wirdsum_sorted()und / oderstriplast(), aber ich konnte nicht ganz herausfinden, wie ich es zur Summierung bringen könnte[entry[1]] für eine Liste von Einträgen incount_words'Ergebnisse sortiert nachentry[0]. Der nächste, den ich bekam, war:

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