Есть ли способ сделать 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)]