Strutture dati importanti nella ricerca

Question

Mi interessa insegnarmi diverse strutture di dati, cosa di cui attualmente so poco. Il mio piano è di implementare alcune strutture chiave in modo da capire come funzionano. Sto cercando suggerimenti su importanti strutture di dati per cominciare.

Sono interessato principalmente a strutture di dati che sono rilevanti per le applicazioni di ricerca (ad esempio Google/Lucene) e al compromesso generale tra il calcolo ritardato e la precomputazione. Mi interesso anche delle strutture dati distribuite - strutture dati che possono scalare centinaia/migliaia di server - e strutture dati probabilistiche - strutture dati che aiutano a trovare una risposta approssimativa, ma non hanno bisogno di essere sempre corrette.

Wikipedia ha una list of data structures. Attualmente sto pensando:

• tabella hash
• albero B +
• R-Tree
• KD-Tree
• Radix-Tree
• Bloom filtrare

Esistono scelte migliori?

Infine, c'è qualche (grave) problema con l'attuazione di queste strutture in un linguaggio come C#?

Answer 1

Molto ambizioso. Ho votato la tua domanda solo per il suo scopo.

MIT ha una on-line algorithms and data structures course. Il companion book è un classico. Non sono sicuro se affronta le caratteristiche distribuite e probabilistiche, ma ti forniranno un'eccellente base sui fondamenti.

Aggiungerei albero rosso-nero, tabelle hash, trie patricia e salti gli elenchi nella tua agenda.

Buona fortuna.

Answer 2

Dato che hai poca conoscenza di DS, penso che dovresti iniziare con gli elenchi (elenchi singoli e doppiamente collegati).

Quindi è possibile studiare diverse strutture dati ad albero.

Anche perché sei interessato a DS correlato alla ricerca, penso che dovresti studiare B-tree + tree e hash table.

The Algorithm Design Manual è un buon libro per ulteriori informazioni sugli algoritmi.

Answer 3

per la ricerca, gli algoritmi sono più importanti delle strutture di dati. Quando cerchi un ampio spazio di ricerca, spesso devi disporre di metodi sofisticati per potare lo spazio di ricerca.

Si potrebbe guardare algoritmi di ricerca classici come alfa-beta, A *, AO *.

poi guardare qualcosa di simile in modo iterativo approfondimento di ricerca.

Negli algoritmi di ricerca, cose come pile e liste collegate (che sono in realtà una forma di pila) e alberi sono più importanti delle tabelle hash, alberi B ecc. Naturalmente, ci saranno senza dubbio tabelle hash, ma non sarà il cuore dell'algoritmo.

Ecco alcuni più importanti algorithsm ricerca:

1. B * ricerca
2. backtracking
3. ricerca fascio
4. best-prima ricerca
5. ricerca bidirezionale
6. ricerca in salita
7. ricottura simulata
8. IDA *
9. approfondimento iterativo in profondità di ricerca
10. mini-max ricerca
11. ricerca vicino più prossimo
12. diffusione attivazione
13. stato di ricerca spaziale (non una tecnica, solo un modo di concettualizzare un problema) .

Per quanto riguarda le strutture dati specifiche per la ricerca, non ne hai davvero bisogno. Fondamentalmente, hai solo bisogno del tuo normale kit di strumenti di strutture dati - alberi, hash, liste.

Answer 4

Se hai intenzione di affrontare questo genere di cose con un linguaggio funzionale dovresti dare un'occhiata a Strutture dati puramente funzionali di Chris Okasaki. Lezione di base è la seguente: le strutture dati con cui si ha familiarità con la programmazione imperativa potrebbero non essere la scelta migliore per la programmazione funzionale. Mi aspetto che ci sia un sacco di materiale simile su cui cercare Google.