Важные структуры данных в поиске

Question

Я заинтересован в преподавании различных структур данных, о чем я сейчас очень мало знаю. Мой план состоит в том, чтобы реализовать несколько ключевых структур, чтобы я понял, как они работают. Для начала я ищу предложения по важным структурам данных.

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

Википедия имеет list of data structures. Я в настоящее время рассматривает:

• Хэш таблица
• B + -Tree
• R-Tree
• KD-Tree
• Radix-Tree
• Bloom фильтр

Есть лучший выбор?

И, наконец, есть ли (основная) проблема с реализацией этих структур на языке, таком как F #?

Answer 1

Очень амбициозный. Я проголосовал за ваш вопрос только за его объем.

MIT имеет on-line algorithms and data structures course. companion book - классика. Я не уверен, что это касается распределенных и вероятностных функций, но они дадут вам отличное обоснование основ.

Я бы добавил красно-черное дерево, хеш-таблицы, patricia trie и пропустил списки в вашу повестку дня.

Удачи.

Answer 2

Поскольку у вас очень мало знаний о DS, я думаю, вам следует начать с списков (Single and doubly Linked Lists).

Затем вы можете изучать различные структуры данных дерева.

Также, поскольку вас интересует DS, связанная с поиском, я думаю, вам следует изучить B-tree + tree и hash table.

The Algorithm Design Manual - хорошая книга, чтобы узнать больше об алгоритмах.

Answer 3

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

Вы можете посмотреть на классические алгоритмы поиска, такие как альфа-бета, A *, AO *.

Затем посмотрите на что-то вроде итеративно углубляющегося поиска.

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

Вот некоторые более важно найти algorithsm:

1. B * Поиск
2. возвратов
3. поиска луча
4. самый первый поиск
5. двунаправленного поиска
6. поиска пониженная
7. моделированный отжиг
8. IDA *
9. итеративным углублением поиск в глубину
10. мини-макс поиск
11. ближайший сосед поиска
12. распространяется активация
13. пространство состояний поиска (а не технику, а только способ концептуализации проблемы) ,

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

Answer 4

Если вы собираетесь заняться подобным делом с функциональным языком, вы должны взглянуть на Чисто функциональные структуры данных by Chris Okasaki. Основной урок: структуры данных, с которыми вы знакомы для императивного программирования, могут быть не лучшим выбором для функционального программирования. Я ожидаю, что есть много похожих материалов для Googled.