Важные структуры данных в поиске
Я интересуюсь обучением мне различные структуры данных, что-то, о чем я в настоящее время знаю очень мало. Мой план состоит в том, чтобы реализовать несколько ключевых структур, таким образом, я понимаю, как они работают. Я ищу предложения на важных структурах данных для запуска с.
Я, прежде всего, интересуюсь структурами данных, которые относятся к поисковым приложениям (например, Google / Lucene) и общий компромисс между задержанным вычислением и предварительным вычислением. Я также интересуюсь распределенными структурами данных - структуры данных, которые могут масштабироваться через сотни / тысячи серверов - и вероятностных структур данных - структуры данных, которые помогают нахождению приблизительного ответа, но не должны всегда быть корректными.
Википедия имеет список структур данных. Я в настоящее время рассматриваю:
- Хеш-таблица
- B +-Tree
- R-дерево
- KD-дерево
- Дерево основания
- Фильтр цветка
Есть ли лучший выбор?
Наконец, есть ли какая-либо (главная) проблема с реализацией этих структур на языке как F#?
4 ответа
Очень амбициозно. Я проголосовал за ваш вопрос только ради его рамок.
MIT имеет он-лайн алгоритмы и структуры данных курса . Сопутствующая книга - классика. Я не уверен, что в ней рассматриваются распределенные и вероятностные особенности, но они дадут вам отличное обоснование в основах.
Я бы добавил красно-черное дерево, хэш-таблицы, Патрисию Три и списки пропусков в вашу повестку дня.
Удачи.
Если вы собираетесь заниматься подобными вещами на функциональном языке, то вам следует взглянуть на Purely Functional Data Structures Криса Окасаки. Основной урок заключается в том, что структуры данных, с которыми вы знакомы для императивного программирования, могут быть не лучшим выбором для функционального программирования. Я ожидаю, что есть много похожего материала, для которого нужно погуглить
.Для поиска алгоритмы более важны, чем структуры данных. При поиске в большом поисковом пространстве часто требуются сложные методы обрезки пространства поиска.
Можно посмотреть на классические алгоритмы поиска, такие как альфа-бета, A*, AO*.
Затем посмотреть на что-то вроде итеративного углубления поиска.
В поисковых алгоритмах такие вещи, как стеки и связанные списки (которые на самом деле являются разновидностью стека) и деревья более важны, чем хэш-таблицы, B-деревья и т.д. Конечно, хэш-таблицы там, несомненно, будут, но это не будет сердцевиной алгоритма.
Вот несколько более важных алгоритмов поиска:
- B* поиск
- обратный поиск
- лучший поиск
- лучший поиск
- двунаправленный поиск
- поиск в горах
- имитирующий отжиг
- IDA*
- итеративный глубинный поиск
- мини-максовый поиск
- поиск ближайшего соседа
- активация расширения
- поиск в пространстве (не метод, просто способ концептуализации задачи). Что касается специфических структур данных для поиска, то они действительно не нужны. В принципе, нужен просто обычный инструментарий структур данных - деревья, хэши, списки .
Поскольку вы очень мало знаете о DS, я думаю, что вам следует начать со списков (одиночных и двойных списков)
Затем вы сможете изучать различные структуры данных деревьев.
Также, поскольку вы интересуетесь DS, относящимся к поиску, я думаю, что вам следует изучить B-дерево+ деревья и хэш-таблицу.
Руководство по проектированию алгоритмов является хорошей книгой, чтобы узнать больше об алгоритмах.
.