проблема

[Ниже следует описание того, что приложение должно делать при каких ограничениях]

Я хочу структуру данных, которая ищет, еслиstring существует в списке из 250 000 слов, при этом используется только достаточное количество оперативной памяти и сохраняется время, необходимое для загрузки этой структуры данных в оперативную память небольшого размера (скажем, 0-8 секунд). Время, необходимое для поиска слова, также должно быть быстрым (скажем, от 0 до 0,5 секунды), но использование оперативной памяти более важно. Также должно быть возможно создать несколько игр (больше о том, что эта игра под названием «использовать»), не требуя значительно большего объема памяти.

Также было бы очень полезно узнать, какие слова начинаются сstring, но не настолько, чтобы жертвовать временем загрузки на много секунд.

использование

Это для автономной игры для Android. Ограниченный баран доступен.Максимальное количество оперативной памяти, которую приложение может использовать в соответствии с этим постом, составляет от 16 до 32 МБ оперативной памяти в зависимости от устройства. Мое пустое Android-приложение уже использует около 17 Мб (используя Memory Monitor в Android Studio). Мое устройство Android ограничивает использование оперативной памяти на 26 МБ, оставляя мне около 8 МБ свободного места для всего моегоActivity.

Варианты я пробовал

Все они кажутся обреченными по-разному.

HashMap - Читать все слова в объект хэш-карты.

1,1инициализировать скорость: медленно, чтобы прочитать каждое слово в хэш-карту с 23 секунд.

1.2использование оперативной памяти: использует значительное количество оперативной памяти, хотя я забыл, сколько именно.

1,3скорость поиска: Найти слово в списке было быстро, конечно.

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

Trie - внедрить RadixTree & Вы можете увидеть мою реализацию здесь.

2,1инициализировать скорость: медленно, чтобы прочитать каждое слово в RadixTree с 47 секунд.

2,2использование оперативной памяти: использует значительное количество оперативной памяти, так что Android несколько раз приостанавливает потоки.

2,3скорость поиска: Найти слово в списке было быстро.

2,4сужение возможных слов (необязательно): Сверхбыстрый, поскольку для нахождения всех возможных слов в качестве его потомков необходима только ссылка на узел в дереве. Вы можете играть во множество игр, сужая количество возможных слов, так как дополнительная игра требует только ссылки на узел в дереве!

сканер - Пройдите через файл слова последовательно

3,1инициализировать скорость: никто.

3,2использование оперативной памяти: никто.

3,3скорость поиска: около 20 секунд.

3,4сужение возможных слов (необязательно): не может быть сделано реально.

простой код:

String word;
String wordToFind = "example";
boolean foundWord = false;

while (wordFile.hasNextLine()) {
    word = wordFile.nextLine();
    if(word.equals(wordToFind)) {
        foundWord = true;
        break;
    }
}

test.close();

Варианты, которые я придумал:

Long-двоично-поиск-дерево: Преобразование списка слов в списокlongзатем читаем их и выполняем двоичный поиск по ним.

1,1инициализировать скорость: вероятно, такой же, как хэш-карта или чуть меньше, примерно с 20 секундами. Однако я надеюсь, что вызов Array.sort () не займет слишком много времени, пока не знаю.

1.2использование оперативной памяти: если вы используете только 12 букв или меньше слов с 26 буквенным алфавитом, вам нужно 5 бит (2 ^ 5 = 32) для кодирования строки. Массиву long потребуется 250 000 * 8 битов = около 2 Мб. Что не так уж и много.

1,3скорость поиска: Arrays.binarySearch ()

1.4сужение возможных слов (необязательно): Возможно сужение возможных слов, но я не уверен, как это сделать.По комментарию к этому посту.

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

2,1инициализировать скорость: не нужно (так как мне нужно заранее поставить каждое слово в нужном индексе)

2,2использование оперативной памяти: никто.

2,3скорость поиска: быстро.

2,4сужение возможных слов (необязательно): невозможно.

Конкретные вопросы у меня естьЯвляются ли варианты, о которых я думал, в разделе «Опции, о которых я подумал», жизнеспособными или есть вещи, которые я пропустил, но которые не позволили бы реализовать их?Есть ли варианты, о которых я не думал, которые лучше / равны по производительности?Конечные замечания

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

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