Почему collection.deque медленнее, чем collection.defaultdict? - PullRequest
Новая
       12

Почему collection.deque медленнее, чем collection.defaultdict?

2 голосов
/ 04 августа 2011

Простите, что я спрашивал в таком общем виде, так как я уверен, что их производительность зависит от того, как их используют, но в моем случае collections.deque был намного медленнее, чем collections.defaultdict, когда я хотел проверить существование значение.

Я использовал исправление орфографии от Питера Норвига , чтобы проверить вводимые пользователем данные по небольшому набору слов. Поскольку я не использовал словарь с частотами слов, я сначала использовал простой list вместо defaultdict, но заменил его на deque, как только я заметил, что поиск по одному слову занял около 25 секунд.

Удивительно, но это было не быстрее, чем использование list, поэтому я вернулся к использованию defaultdict, который возвращал результаты почти мгновенно.

Может кто-нибудь объяснить мне эту разницу в производительности?

Заранее спасибо

PS : Если кто-то из вас хочет воспроизвести то, о чем я говорил, измените следующие строки в сценарии Норвиг. 

-NWORDS = train(words(file('big.txt').read()))
+NWORDS = collections.deque(words(file('big.txt').read()))

-return max(candidates, key=NWORDS.get)
+return candidates

1 Ответ

10 голосов
/ 04 августа 2011

Эти три структуры данных не являются взаимозаменяемыми, они служат совершенно разным целям и имеют совершенно разные характеристики:

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

Все эти свойства важны, имейте их в виду, когда бы вывыберите один над другим.Что ломает вам голову в этом конкретном случае, так это сочетание последнего свойства словарей и количества возможных исправлений, которые необходимо проверить.Некоторая простая комбинаторика должна прийти к конкретной формуле для числа правок, которые этот код генерирует для данного слова, но каждый, кто достаточно часто неправильно предсказывал такие вещи, будет знать, что это будет удивительно большое число даже для средних слов.

Для каждого этих правок есть проверка edit in NWORDS, чтобы отсеять правки, которые приводят к неизвестным словам.Не проблема в программе Norvig, так как in проверки (проверки существования ключа), как упоминалось ранее, очень быстрые.Но вы поменяли словарь с последовательностью (deque)!Для последовательностей in должен выполнить итерацию по всей последовательности и сравнить каждый элемент с искомым значением (он может остановиться, когда найдет совпадение, но, поскольку наименьшее количество правок - это известные слова, находящиеся в начале очереди, обычновсе еще ищет все или большую часть deque).Поскольку существует довольно много слов, и тест проводится для каждого сгенерированного редактирования, вы в конечном итоге тратите 99% своего времени на линейный поиск в последовательности, где вы можете просто хешировать строку и сравнивать ее один раз (или самое большее - вслучай столкновений - несколько раз).

Если вам не нужны веса, вы можете концептуально использовать фиктивные значения, на которые вы никогда не обращали внимания, и при этом получить повышение производительности проверки O (1) in.Практически, вы должны просто использовать set, который использует почти те же алгоритмы, что и словари, и просто отсекает часть, в которой хранится значение (это было на самом деле впервые реализовано таким образом, я не знаю, насколько сильно эти два расходятсяпоскольку наборы были повторно реализованы в отдельном, отдельном модуле C).

...