#python #dictionary #tree #lookup
#python #словарь #дерево #поиск
Вопрос:
Учитывая текст, который разделен на список слов, я хочу выполнить поиск каждого из слов в словаре слов, который также считывается из текстового файла и split('n') .
Вместо того, чтобы проверять, содержится ли каждое слово в словаре (что ужасно медленно) Мне нужно выбрать список элементов на основе подстановочных знаков * (‘*’ находится в конце, т.Е. Решение permuterm не требуется). Например, решение должно выбирать все элементы словаря, начинающиеся с ‘dep’, без обхода всего списка словарей.
В этом случае важна производительность. Я думал о Btree … но
- Какой был бы лучший пакет и тип данных для быстрой реализации на Python.
- Пожалуйста, предоставьте примеры кода
Комментарии:
1. Похоже, вам нужен какой-то пакет trie
2. Подстановочный знак всегда будет медленнее. Dicts работают с хэшами (постоянное время доступа).
3. @JBernardo: нет, это просто означает, что элементы должны начинаться с того, что предшествует «звезде»
4. Вот почему вы потеряете постоянный поиск по времени. т. Е. Это будет медленнее.
Ответ №1:
Используйте dawg, который более эффективен, чем Trie, с точки зрения отходов пространства. Существует несколько реализаций python, но для начала взгляните сюда.
Комментарии:
1. С веб-сайта: «… Если вас не волнует память или скорость [sic!], Просто сохраните свои слова «… Это быстрее?
2. Dawg определенно быстрее. Цитата с веб-сайта иронична. «просто сохраните свои слова в базе данных SQL или запустите 100 компьютеров в облаке. Я не возражаю. Больше возможностей для вас! »