Problem

Grałem na różne sposoby (w Pythonie 2.7), aby wyodrębnić listę (słów, częstotliwości) krotek z korpusu lub listy łańcuchów i porównać ich wydajność. O ile wiem, w normalnym przypadku z nieposortowaną listąCountermetoda zcollections moduł jest lepszy od wszystkiego, co wymyśliłem lub znalazłem w innym miejscu, ale nie wydaje się, aby w pełni wykorzystywał zalety wstępnie posortowanej listy i opracowałem metody, które łatwo go pokonały w tym specjalnym przypadku . Krótko mówiąc, czy istnieje jakikolwiek wbudowany sposób informowaniaCounter z faktu, że lista jest już posortowana, aby ją jeszcze przyspieszyć?

(Następna sekcja jest na nieposortowanych listach, gdzie licznik działa magicznie; możesz przeskoczyć do końca, gdzie traci swój urok, gdy ma do czynienia z posortowanymi listami.)

Niesortowane listy wprowadzaniaJedno podejście, które nie działa

Naiwnym podejściem byłoby użyciesorted([(word, corpus.count(word)) for word in set(corpus)]), ale ten niezawodnie prowadzi do problemów z runtime, gdy tylko twój korpus ma kilka tysięcy elementów - nic dziwnego, ponieważ wielokrotnie przeglądasz całą listę n słów m, gdzie m jest liczbą unikalnych słów.

Sortowanie listy + wyszukiwanie lokalne

Więc to, co próbowałem zrobić, zanim znalazłemCounter upewniłem się, że wszystkie wyszukiwania są ściśle lokalne, najpierw sortując listę wejściową (muszę także usunąć cyfry i znaki interpunkcyjne oraz przekonwertować wszystkie wpisy na małe litery, aby uniknąć duplikatów takich jak 'foo', 'Foo' i '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

Odkryciecollections.Counter

Jest to o wiele lepsze, ale wciąż nie tak szybkie, jak użycie klasy Counter z modułu kolekcji, która tworzy słownik wpisów {słowo: częstotliwość słowa} (nadal musimy wykonać to samo usuwanie i obniżanie, ale bez sortowania) :

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

Na korpusie Gutenberga z ok. 2 miliony wpisów, metoda Counter jest o około 30% szybsza na mojej maszynie (5 sekund, w przeciwieństwie do 7.2), co wyjaśniono głównie za pomocą procedury sortowania, która zajmuje około 2,1 sekundy (jeśli nie masz i nie chcesz zainstaluj pakiet nltk (Natural Language Toolkit), który oferuje dostęp do tego korpusu, każdy inny odpowiednio długi tekst odpowiednio podzielony na listę ciągów na poziomie słowa pokaże ci to samo.)

Porównywanie wydajności

Z moją idiosynkratyczną metodą pomiaru czasu przy użyciu tautologii jako warunku opóźnienia wykonania, daje to nam metodę licznika:

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

(Widzimy, że ostatni krok formatowania wyników jako listy krotek zajmuje mniej niż 5% całkowitego czasu).

W porównaniu do mojej funkcji:

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

Posortowane listy wejść - kiedyCounter „zawiedzie”

Jednak, jak zapewne zauważyłeś, moja funkcja pozwala określić, że dane wejściowe są już posortowane, pozbawione śmieci interpunkcyjnych i przekonwertowane na małe litery. Jeśli już stworzyliśmy tak skonwertowaną wersję listy dla niektórych innych operacji, jej użycie (i zadeklarowanie jej) może bardzo przyspieszyć działanie mojegowordcount5:

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

Tutaj skróciliśmy czas działania o około. 8 nie trzeba sortować korpusu i konwertować przedmiotów. Oczywiście to ostatnie odnosi się również do karmieniaCounter z tą nową listą, więc oczekuje się, że jest też nieco szybszy, ale wydaje się, że nie wykorzystuje faktu, że jest posortowany i teraz zajmuje dwa razy więcej czasu niż moja funkcja, gdzie był o 30% szybszy przed:

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

Oczywiście możemy użyć tej samej logiki, z której korzystałemwordcount5 - zwiększanie lokalnego licznika, aż natkniemy się na nowe słowo i dopiero wtedy zapiszemy ostatnie słowo z bieżącym stanem licznika i zresetujemy licznik do 0 dla następnego słowa - tylko używającCounter jako przechowywanie, ale wrodzona wydajnośćCounter metoda wydaje się zagubiona, a wydajność jest w zakresie moich funkcji do tworzenia słownika, z dodatkowym obciążeniem polegającym na konwersji na listę krotek, które teraz wydają się bardziej kłopotliwe niż kiedyś, gdy przetwarzaliśmy surowy korpus:

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

(Podobieństwo wyników nie jest zaskakujące, ponieważ w efekcie wyłączamyCounterwłasne metody i nadużywanie go jako sklepu dla wartości uzyskanych przy użyciu tej samej metodologii, co poprzednio.)

Dlatego moje pytanie: Czy istnieje bardziej idiomatyczny sposób informowaniaCounter że jego lista wejściowa jest już posortowana i sprawia, że ​​w ten sposób zachowuje bieżący klucz w pamięci, a nie szuka go na nowo za każdym razem, gdy - przewidywalnie - napotka następny znak tego samego słowa? Innymi słowy,czy możliwe jest dalsze zwiększenie wydajności na wstępnie posortowanej liście, łącząc nieodłączną wydajnośćCounter/dictionary klasa z oczywistymi zaletami posortowanej listylub czy już zaczepiam się na twardym limicie z 0,9 sekundy na zestawienie listy wpisów 2M?

Prawdopodobnie nie ma wiele miejsca na ulepszenia - dostaję czasy około .55 sekund, gdy robienie najprostszej rzeczy, o której mogę pomyśleć, wciąż wymaga iterowania przez tę samą listę i sprawdzania każdej indywidualnej wartości, a .25 dlaset(corpus) bez liczenia, ale może jest tam jakaś magia itertools, która pomogłaby zbliżyć się do tych liczb?

(Uwaga: jestem względnym nowicjuszem w Pythonie i ogólnie w programowaniu, więc wybacz, jeśli przegapiłem coś oczywistego).

Edytuj 1 grudnia:

Inną rzeczą, oprócz samego sortowania, które sprawia, że ​​wszystkie moje metody są powolne, jest konwersja każdego z ciągów 2M na małe i pozbawienie ich interpunkcji lub cyfr, które mogą zawierać. Próbowałem wcześniej, aby to skrócić, licząc nieprzetworzone ciągi, a dopiero potem konwertując wyniki i usuwając duplikaty, jednocześnie sumując ich liczniki, ale musiałem zrobić coś złego, ponieważ sprawiało to, że rzeczy były nieco wolniejsze. Dlatego powróciłem do poprzednich wersji, konwertując wszystko w surowym korpusie, a teraz nie mogę całkiem zrekonstruować tego, co tam zrobiłem.

Jeśli spróbuję teraz, ulepszam konwertowanie łańcuchów jako ostatnie. Nadal to robię, zapętlając listę (wyników). To, co zrobiłem, to napisanie kilku funkcji, które między nimi konwertują klucze w wyniku zwycięskiej metody J._. Sebastiana default_dict (formatu[("word", int), ("Word", int)], ("word2", int),...]) na małe litery i usuń je z interpunkcji, i zwinąć liczby wszystkich kluczy, które pozostały identyczne po tej operacji (kod poniżej). Zaletą jest to, że teraz obsługujemy listę około 50 tys. Wpisów, w przeciwieństwie do> 2M w korpusie. W ten sposób mam teraz 1,25 sekundy na przejście od korpusu (jako listy) do licznika słów bez rozróżniania wielkości liter, ignorując znaki interpunkcyjne na moim komputerze, w dół od około 4.5 z metodą Counter i konwersją ciągu jako pierwszy krok. Ale może istnieje metoda oparta na słownikach dla tego, co robięsum_sorted() także?

Kod:

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

Podjąłem kilka pierwszych prób użycia groupy do wykonania aktualnie wykonywanej pracysum_sorted()i / lubstriplast(), ale nie mogłem całkiem zrozumieć, jak skłonić go do podsumowania[entry[1]] listę wpisów wcount_words„wyniki posortowane wedługentry[0]. Najbliższy dostałem to:

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