Огромный статический массив строк

Question

Хорошая идея хранить слова словаря с 100.000 слов в статическом массиве строк. Я работаю над проверкой орфографии и подумал, что так будет быстрее.

Answer 1

Обычно вы предпочитаете класс Java Collections Framework, а не массив Java, для чего-то нетривиального. В данном конкретном случае у вас есть Set<String> (поскольку слова не должны появляться в словаре более одного раза).

A HashSet<String> обеспечивает постоянную производительность по времени для основных операций add, remove и contains и должна очень хорошо работать с String формулой хеш-кода.

Для больших словарей вы хотели бы использовать более сложные структуры данных, специально предназначенные для хранения набора строк (например, trie ), но для 100K слов достаточно HashSet.

Смотри также

• Структура учебных пособий по Java / коллекций
• Effective Java 2nd Edition, Item 25: Предпочитайте списки массивам

Answer 2

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

Answer 3

Как насчет подхода с использованием технологии базы данных в памяти, как, например, sqlite inmemory Это позволяет использовать эффективные запросы без дисковых накладных расходов

Answer 4

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

См. Перечисление, превышающее ограничение в 65535 байтов статического инициализатора ... что лучше сделать? .

Answer 5

Возможно, использование базы данных SQLite будет более эффективным? Я думаю, что именно это делает Firefox / Thunderbird для проверки орфографии, но я не совсем уверен.

Answer 6

Я думаю, что 100 000 - это не так много, что поиск будет неэффективным.Конечно, это зависит ... Было бы хорошо, если бы вы проверяли, существует ли слово в массиве - это алгоритм линейной сложности.Вы можете упорядочить таблицу, чтобы использовать алгоритм поиска по быстрой сортировке и сделать его более эффективным.

С другой стороны - если вы хотите найти, 5 наиболее вероятных слов (используя метод N-граммы или что-то)следует рассмотреть возможность использования Lucene или другой текстовой базы данных.