Android-словарь TreeSet ускоряет время загрузки - PullRequest
4 голосов
/ 16 июня 2011

В моем словаре около 300000 слов (фактически сохраненных в формате txt (с разделителями новой строки) на SD-карте моего устройства Android). Я хочу построить структуру данных, которая заняла бы как можно меньше времени для вставки слов (String-s) из моего txt-файла в эту структуру данных. И этот DS должен быть очень быстрым для проверки, существуют ли слова в словаре (этот DS) или нет. Я попробовал несколько встроенных DS, и самым быстрым IMO был TreeSet. Существуют ли другие (не встроенные) DS, которые были бы быстрее вставлять / создавать DS и такие же, как TreeSet для поиска?

И еще одна вещь: я могу как-то помочь TreeSet, чтобы он быстрее вставлялся, переставляя мой текстовый файл (поместите слова в правильном порядке).

Привет

1 Ответ

5 голосов
/ 16 июня 2011

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

Если вы хотите сэкономить время сборки, а файл слов не меняется очень часто, очевидным улучшением скорости сборки является кэширование структуры данных. Какую бы структуру данных вы не использовали, создайте ее один раз, а затем сохраните структуру на SD-карте (а не просто храните строки). Стандартные структуры java.util могут быть сохранены с использованием Сериализация .

Если вам нужно самое быстрое время сборки, и ваш список слов отсортирован в алфавитном порядке или может быть, тогда вы можете просто сохранить его в массиве String. Время сборки снова будет очень коротким, а время поиска будет аналогично TreeSet (с использованием Arrays.binarySearch () ).

Если вам нужен более быстрый поиск, вы можете проверить Perfect Hash ing или Trie s, но их нет в стандартных библиотеках Java.

Три будут гораздо более эффективными в использовании памяти, чем любой из них, что может сделать его быстрее. ( Информация о поиске реализации )

Я удивлен, что TreeSet работает быстрее, чем HashSet в ваших экспериментах, а это значит, что вы можете работать в ситуации, когда выделение памяти стоит дорого. Помните ли вы, чтобы установить начальную емкость при выделении HashSet? Помните, чтобы избежать дорогостоящей перефразировки, вам нужно установить начальную емкость по крайней мере на количество элементов / 0,75 (коэффициент загрузки).

...