Как организовать словарь для быстрой работы с ним?

Question

[nadom]

Добрый день.

Делаю небольшую игру, что-то вроде "эрудита" и вот возник у меня вопрос.
Для реализации логики компьетра необходимо иметь и хранить в памяти базу и возможных слов для ходов (кууууча существительных), она же нужна и для проверки правильности хода игрока.

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

Если бы речь шла о числах, то выбор понятен - дерево или сортированный массив/список/тд.
А вот что придумать для быстрого поиска строк?

Answer 1

[asd111]

Немного теории

Answer 2

[Станислав Макаров]

Из структур данных попробуйте посмотреть вот это (если конечно вам нужен поиск подстроки, а не всей строки целиком): https://ru.wikipedia.org/wiki/%D0%A1%D1%83%D1%84%D... , там есть ссылки на известные труды, что касается "не загружать оперативную память" - в общем-то для любой структуры данных можно организовать гибридное хранение - сам индекс построить заранее и хранить на диске (вполне логичный ход в случае предварительно подготовленного словаря), а в память загружать части индекса. Однако это значительно усложнит алгоритмы, нужно это вам или нет - зависит от деталей поставленной задачи (объем словаря, предельное время поиска и т.д.)

Answer 3

[Сергей Протько]

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

Comments

[nadom]

Выборка довльно сложная.

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

А в случае хода компьюетра - это поиск слов, состоящих из указанных символов.

[Сергей Протько]

nadom: проверка введенных слов - отсортированный массив строк и бинарный поиск - норм. Быстро и просто. ПО второму пункту чуть сложнее. Я бы организовал индекс по вхождению символов в строки.

[nadom]

Бинарный поиск я и сам догадался использовать.
Но он мешает второму поиску.

Можно подробнее про индекс.