Блог

У меня есть текстовый файл, содержащий ~ 30 000 слов в алфавитном порядке, каждое в отдельной строке. У меня также есть Set<String> set , содержащий ~ 10 слов.

Я хочу проверить, есть ли какие-либо слова в моем set списке слов (текстовый файл).

До сих пор мой метод заключался в:

1. Откройте текстовый файл списка word
2. Прочитайте строку / слово
3. Проверьте, set содержит ли это слово
4. Повторите до конца файла списка word

Это кажется плохо оптимизированным. Например, если я проверяю слово в моем наборе, которое начинается с буквы b, я не вижу смысла проверять слова в текстовом файле, начинающемся с a amp; c, d, .. и т.д.

Моим предлагаемым решением было бы разделить текстовый файл на 26 файлов, по одному файлу для слов, которые начинаются с каждой буквы алфавита. Есть ли более эффективное решение, чем это?

Примечание: Я знаю, что 30 000 слов — это не такой большой список слов, но мне приходится выполнять эту операцию много раз на мобильном устройстве, поэтому производительность является ключевой.

Вы можете продолжить свой подход, используя хэш-наборы для всего файла списка слов. Сравнение строк обходится дорого, поэтому лучше создать хэш-набор из целых чисел. Вы должны прочитать список слов (при условии, что количество слов не увеличится с 30 000 до примерно 3 миллионов) один раз полностью и сохранить все слова в целочисленном хэш-наборе. При добавлении в целочисленный хэш-набор используйте:

 wordListHashSet.add(mycurrentword.hashcode());
  

Вы упомянули, что у вас есть хэш строки из 10 слов, которые необходимо проверить, есть ли они в списке слов. Опять же, вместо хэша строки создайте набор хэшей целого числа.
Создайте итератор этого набора хэшей целых чисел.

 Iterator it = myTenWordsHashSet.iterator();
  

Повторите это в цикле и проверьте наличие следующего условия:

 wordListHashSet.contains(it.next());
  

Если это верно, то у вас есть слово в списке слов.

Использование целочисленных хэш-карт — хорошая идея, когда производительность — это то, что вы ищете. Внутренне Java обрабатывает хэш каждой строки и сохраняет его в памяти таким образом, что повторный доступ к таким строкам выполняется очень быстро, быстрее, чем двоичный поиск со сложностями поиска от O (log n) почти до O (1) для каждого вызова элемента в списке слов.

Надеюсь, это поможет!

Вероятно, это не стоит того, чтобы тратить 30 000 слов, но давайте просто скажем, что у вас есть намного больше, скажем, 300 000 000 слов, и все еще нужно искать только 10 слов.

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

Вы могли бы рассмотреть возможность перебора вашего набора из 10 слов (возможно, разобрать его из файла в массив) и для каждой записи использовать алгоритм двоичного поиска, чтобы увидеть, содержится ли она в большем списке. Двоичный поиск должен занимать только O (logN), поэтому в данном случае log (30 000), что значительно быстрее, чем 30 000 шагов.

Поскольку вы будете повторять этот шаг один раз для каждого слова в вашем наборе, это должно занять 10 * log (30k)

Вы можете внести некоторые улучшения в зависимости от ваших потребностей.

Например, если файл остается неизменным, но ваш набор из 10 слов регулярно меняется, тогда вы можете загрузить файл в другой набор (HashSet). Теперь вам просто нужно выполнить поиск соответствия в этом новом наборе. Таким образом, ваш поиск всегда будет O (1).