Есть ли способ сделать collection.Counter (Python2.7) осведомленным о том, что его входной список отсортирован?

Проблема

Я поиграл с разными способами (в Python 2.7), чтобы извлечь список (слово, частота) кортежей из корпуса или список строк и сравнить их эффективность. Насколько я могу судить, в обычном случае с несортированным спискомCounterметод изcollections Модуль превосходит все, что я придумал или нашел в другом месте, но он, кажется, не пользуется преимуществами предварительно отсортированного списка, и я нашел методы, которые легко справляются с этим в этом особом случае , Итак, вкратце, есть ли встроенный способ сообщитьCounter из того, что список уже отсортирован для дальнейшего ускорения его?

(Следующий раздел находится в несортированных списках, где Counter работает с магией; вы можете перейти к концу, где он теряет свое очарование при работе с отсортированными списками.)

Несортированные списки вводаОдин подход, который не работает

Наивный подход будет использоватьsorted([(word, corpus.count(word)) for word in set(corpus)]), но этот надежно доставит вас к проблемам во время выполнения, как только ваш корпус будет насчитывать несколько тысяч элементов - неудивительно, так как вы просматриваете весь список из n слов m много раз, где m - количество уникальных слов.

Сортировка списка + локальный поиск

Так что я пытался сделать вместо того, чтобы найтиCounter Убедитесь, что все поиски строго локальны, сначала отсортировав входной список (я также должен удалить цифры и знаки препинания и преобразовать все записи в нижний регистр, чтобы избежать дубликатов, таких как 'foo', 'Foo' и '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
обнаружениеcollections.Counter

Это намного лучше, но все же не так быстро, как при использовании класса Counter из модуля коллекций, который создает словарь записей {word :quency of word} (мы все равно должны сделать то же самое разбор и понижение, но без сортировки) :

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

На корпусе Гутенберга с ок. 2 миллиона записей, метод Counter на моей машине примерно на 30% быстрее (5 секунд вместо 7.2), что в основном объясняется с помощью процедуры сортировки, которая потребляет около 2,1 секунды (если у вас ее нет и вы не хотите установите пакет nltk (Natural Language Toolkit), который предлагает доступ к этому корпусу, любой другой достаточно длинный текст, соответствующим образом разделенный на список строк на уровне слов, покажет вам то же самое.)

Сравнение производительности

С моим уникальным методом определения времени, использующим тавтологию как условие задержки выполнения, это дает нам для счетчика метод:

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

(Мы видим, что последний шаг, форматирование результатов в виде списка кортежей, занимает менее 5% от общего времени.)

По сравнению с моей функцией:

>>> if 1:
...     start = time.time()
...     gbfreqs = wordcount5(corpus)
...     time.time()-start
... 
7.261770963668823
Сортированные списки ввода - когдаCounter «Терпит неудачу»

Однако, как вы могли заметить, моя функция позволяет указать, что ввод уже отсортирован, очищен от пунктуального мусора и преобразован в нижний регистр. Если мы уже создали такую преобразованную версию списка для некоторых других операций, ее использование (и объявление об этом) может очень ускорить работу моего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

Здесь мы сократили время выполнения в ок. 8 не сортируя корпус и не преобразовывая предметы. Конечно, последнее также верно при кормленииCounter с этим новым списком, так что, вероятно, он также немного быстрее, но, похоже, он не использует тот факт, что он отсортирован и теперь занимает в два раза больше времени, чем моя функция, где он был на 30% быстрее:

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

Конечно, мы можем использовать ту же логику, что и вwordcount5 - увеличивать локальный счетчик до тех пор, пока мы не столкнемся с новым словом, и только затем сохранить последнее слово с текущим состоянием счетчика, и сбросить счетчик до 0 для следующего слова - только с использованиемCounter в качестве хранилища, но присущей эффективностиCounter Кажется, что метод потерян, и производительность в пределах моей функции по созданию словаря, с дополнительным бременем преобразования в список кортежей, теперь выглядит более хлопотно, чем раньше, когда мы обрабатывали необработанный корпус:

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

(Сходство результатов на самом деле не удивительно, так как мы фактически отключаемCounterсобственные методы и использование его в качестве хранилища для значений, полученных по той же методологии, что и раньше.)

Поэтому мой вопрос: есть ли более идиоматический способ сообщитьCounter что его входной список уже отсортирован и, таким образом, он сохраняет текущий ключ в памяти, а не ищет его заново каждый раз, когда он - как и ожидалось - встречает следующий токен того же слова? Другими словами,Можно ли улучшить производительность в предварительно отсортированном списке, комбинируя присущийCounter/dictionary класс с очевидными преимуществами отсортированного списка, или я уже искал жесткое ограничение с 0,9 секундами для подсчета списка 2M записей?

Вероятно, не так уж много возможностей для улучшения - у меня есть время около .55 секунд, когда я выполняю простейшую вещь, о которой я могу подумать, что все же требуется перебирать один и тот же список и проверять каждое отдельное значение, и .25 дляset(corpus) без подсчета, но, может быть, есть какая-то магия itertools, которая поможет приблизиться к этим фигурам?

(Примечание: я относительный новичок в Python и в программировании в целом, поэтому извините, если я пропустил что-то очевидное.)

Изменить 1 декабря:

Еще одна вещь, помимо самой сортировки, которая замедляет все мои методы, описанные выше, - это преобразование каждой строки 2M в строчные буквы и удаление из них знаков препинания или цифр, которые они могут содержать. Раньше я пытался сократить это, подсчитывая необработанные строки и только затем конвертируя результаты и удаляя дубликаты при суммировании их количества, но я, должно быть, сделал что-то не так, потому что все стало немного медленнее. Поэтому я вернулся к предыдущим версиям, конвертировав все в сыром корпусе, и теперь не могу полностью реконструировать то, что я там делал.

Если я попробую это сейчас, я получу улучшение от преобразования строк в последнюю очередь. Я все еще делаю это, перебирая список (результатов). Я написал пару функций, которые между ними конвертировали бы ключи в выводе выигрышного метода default_dict Дж. Ф. Себастьяна (формата[("word", int), ("Word", int)], ("word2", int),...]) в нижний регистр и лишить их знаков пунктуации и свернуть счетчики для всех ключей, которые были оставлены идентичными после этой операции (код ниже). Преимущество заключается в том, что мы сейчас обрабатываем список из примерно 50 тысяч записей, а не более 2 миллионов в корпусе. Таким образом, теперь у меня есть 1,25 секунды для перехода от корпуса (в виде списка) к количеству слов без учета регистра без учета знаков препинания на моем компьютере, по сравнению с 4,5 с использованием метода Counter и преобразования строк в качестве первого шага. Но, возможно, есть метод на основе словаря для того, что я делаю вsum_sorted() также?

Код:

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

Я предпринял несколько первых попыток использовать groupy для выполнения работы, выполняемой в настоящее времяsum_sorted()и / илиstriplast(), но я не мог понять, как обмануть это в суммировании[entry[1]] для списка записей вcount_wordsрезультаты отсортированы поentry[0], Самое близкое, что я получил, было:

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

Ответы на вопрос(3)

Ваш ответ на вопрос