Установить против DAWG для проверки членства в словаре в Python
Мне нужно быстро проверить, есть ли данное слово в моем словаре (английский словарь). Меня интересует только скорость проверки членства (не добавление или удаление элементов), и использование памяти на самом деле не проблема.
Первоначально я использовал такой набор:
words = set(x.strip().lower() for x in open("/usr/share/dict/words").readlines())
if(word in words):
...
Моя программа заняла ок. 4s для запуска на тестовом входе. Затем я попытался оптимизировать ситуацию, используя DAWG ( http://pypi.python.org/pypi/pyDAWG) вместо этого, предварительно рассчитав DAWG и выбрав его:
words = pickle.load(open('wordlistDAWG.pyd'))
if(words.word2index(word) is not None):
...
На том же тестовом входе программе потребовалось около 40 секунд для запуска (включая несколько секунд для загрузки DAWG, которая меня не интересует). Я надеялся, что использование DAWG ускорит процесс!
Может быть, мне не хватает понимания того, как Python хэширует вещи - набор, который я лучше получу (O(1) членский тест), а не DAWG или Trie? Будет ли DAWG просто экономить память, а не вычисления?
Большое спасибо!
2 ответа
Я думаю, что DAWG не спасет ваши циклы процессора, если вы используете его в качестве замены набора.
Поиск набора равен O (1) относительно размера набора, и поиск DAWG также равен O (1) относительно количества элементов DAWG. DAWG-поиск - это O (N) относительно длины ключа поиска (для того, чтобы проверить, находится ли ключ в DAWG, когда ключ находится в DAWG, необходимы шаги len (key)). Поиск набора также O (N) относительно длины ключа (потому что хэш ключа должен быть вычислен). Так что это сводится к реализации, и
- хеш-карты обычно работают быстрее, чем другие структуры данных (включая DAWG и Tries);
- Набор Python хорошо оптимизирован; расчет хеш-функции для встроенных типов также оптимизирован; наборы / dicts в CPython имеют специализированные пути кода для ключей Unicode.
У DAWG может быть преимущество, когда элемент не находится в DAWG, потому что для этого потребуется меньше шагов (ключа), чтобы проверить это, и для вычисления шагов хешла (ключа) всегда нужны (хорошо, если значение хэша не кэшируется). Но даже в этом случае сложно превзойти встроенный набор.
Бесстыдный плагин - вы также можете попробовать https://pypi.python.org/pypi/DAWG - но __contains__ все еще примерно в 2 раза медленнее, чем у dict.
Кстати, pyDAWG Python-версия word2index делает много внутренних поисков, поэтому она не может быть быстрее, чем поиск с одним набором.
Вы используете идеальную функциональность хеширования, вызывая word2index который звучит так, как будто тебе не нужно. Почему ты не используешь exists вместо?