Structures de données importantes dans la recherche

Question

Je m'intéresse à m'enseigner différentes structures de données, quelque chose que je connais très peu actuellement. Mon plan est de mettre en place quelques structures clés pour que je comprenne comment elles fonctionnent. Je cherche des suggestions sur des structures de données importantes pour commencer. Je m'intéresse principalement aux structures de données qui sont pertinentes pour les applications de recherche (par exemple Google/Lucene) et le compromis général entre le calcul différé et le précalcul. Je m'intéresse également aux structures de données distribuées - des structures de données qui peuvent évoluer sur des centaines/milliers de serveurs - et aux structures de données probabilistes - des structures de données qui aident à trouver une réponse approximative mais n'ont pas toujours besoin d'être correctes.

Wikipédia a un list of data structures. J'envisage actuellement:

• table de Hash
• B + -Tree
• R-Tree
• KD-Tree
• Radix-Tree
• filtre de Bloom

Y at-il meilleurs choix?

Enfin, y a-t-il un problème (majeur) à implémenter ces structures dans un langage comme F #?

Answer 1

Très ambitieux. J'ai voté votre question juste pour sa portée. Le MIT a un on-line algorithms and data structures course. Le companion book est un classique. Je ne suis pas sûr si elle aborde les fonctionnalités distribuées et probabilistes, mais ils vous donneront une excellente base dans les principes fondamentaux.

J'ajouterais l'arborescence rouge-noir, les tables de hachage, les listes patricia trie et les listes de sauts à votre agenda.

Bonne chance.

Answer 2

Comme vous avez très peu de connaissances sur DS, je pense que vous devriez commencer par les listes (Listes simples et doublement liées).

Ensuite, vous pouvez étudier différentes structures de données arborescentes.

Aussi puisque vous êtes intéressé par la recherche liée à la DS, je pense que vous devriez étudier B-tree + arbres et table de hachage.

The Algorithm Design Manual est un bon livre pour en savoir plus sur les algorithmes.

Answer 3

Pour la recherche, les algorithmes sont plus importants que les structures de données. Lorsque vous recherchez un grand espace de recherche, vous devez souvent avoir des méthodes sophistiquées pour élaguer l'espace de recherche.

Vous pouvez regarder des algorithmes de recherche classiques tels que alpha-beta, A *, AO *.

Ensuite, regardez quelque chose comme approfondir itérativement la recherche. Dans les algorithmes de recherche, les choses comme les piles et les listes liées (qui sont vraiment une forme de pile) et les arbres sont plus importants que les tables de hachage, les arbres B, etc. Bien sûr, vous aurez certainement des tables de hachage dedans, mais ce ne sera pas le cœur de l'algorithme.

Voici quelques recherche algorithsm plus importante:

1. B * Recherche
2. retours en arrière
3. recherche faisceau
4. best-première recherche
5. recherche bidirectionnelle
6. recherche colline escalade
7. recuit simulé
8. IDA *
9. profondeur première recherche approfondissement itérative
10. recherche mini-max
11. recherche du plus proche voisin
12. propagation activation
13. recherche espace d'état (pas une technique, juste une façon de conceptualiser un problème) .

En ce qui concerne les structures de données spécifiques pour la recherche, vous n'en avez vraiment pas besoin. Fondamentalement, vous avez juste besoin de votre boîte à outils régulière de structures de données - arbres, hachages, listes.

Answer 4

Si vous allez aborder ce genre de chose avec un langage fonctionnel, vous devriez jeter un oeil à Structures de données purement fonctionnelles par Chris Okasaki. La leçon de base est: les structures de données que vous connaissez pour la programmation impérative peuvent ne pas être les meilleurs choix pour la programmation fonctionnelle. Je pense qu'il y a beaucoup de matériel similaire pour Google.