C# Alberi binari e dizionari

Question

Sono alle prese con il concetto di quando utilizzare alberi di ricerca binaria e quando utilizzare i dizionari.

Nella mia applicazione ho fatto un piccolo esperimento che utilizzava la libreria C5 TreeDictionary (che a mio avviso è un albero di ricerca binaria rosso-nero) e il dizionario C#. Il dizionario era sempre più veloce nelle operazioni di aggiunta/ricerca e utilizzava sempre meno spazio di memoria. Ad esempio, alle 16809 <int, float> voci, il dizionario ha utilizzato 342 KiB mentre l'albero ha utilizzato 723 KiB.

Ho pensato che i BST dovessero essere più efficienti in termini di memoria, ma sembra che un nodo dell'albero richieda più byte di una voce in un dizionario. Cosa dà? C'è un punto in cui i BST sono meglio dei dizionari?

Inoltre, come una domanda laterale, qualcuno sa se c'è un + più memoria struttura dati veloce efficiente per la memorizzazione <int, float> paia di accesso tipo di dizionario di una delle strutture di cui?

Answer 1

ho pensato che la BST di dovevano essere più efficiente della memoria, ma sembra che un nodo dell'albero richiede più byte di una voce in un dizionario . Cosa dà? Esiste un punto in cui i BST sono meglio dei dizionari ?

Personalmente non ho mai sentito parlare di un simile principio. Anche ancora, è solo un principio generale, non un fatto categoriale inciso nel tessuto dell'universo.

In genere, i dizionari sono in realtà solo un involucro di fantasia su una serie di elenchi collegati. Si inserisce in qualcosa di simile dizionario:

LinkedList<Tuple<TKey, TValue>> list = 
    internalArray[internalArray % key.GetHashCode()]; 
if (list.Exists(x => x.Key == key)) 
    throw new Exception("Key already exists"); 
list.AddLast(Tuple.Create(key, value)); 

Così la sua quasi O (1) il funzionamento. Il dizionario utilizza la memoria O (internalArray.Length + n), dove n è il numero di elementi nella raccolta.

In BST generale può essere implementato come:

• legati liste, che utilizzano O (n) spazio, dove n è il numero di articoli della collezione.
• arrays, che utilizzano O (2 ^h - n) spazio in cui h è l'altezza dell'albero e n è il numero di elementi nella raccolta.
  • Dal alberi rosso-neri hanno un'altezza limitata di O (1,44 * n), un'implementazione serie dovrebbe avere un utilizzo della memoria limitata di circa O (2 ^1.44n - n)

Le probabilità sono, C5 TreeDictionary è implementato utilizzando matrici, che è probabilmente responsabile dello spazio sprecato.

Cosa dà? C'è un punto in cui i BST sono migliori dei dizionari?

Dizionari hanno alcune proprietà indesiderabili:

• Non può non essere sufficiente blocchi continugous di memoria per contenere il vostro dizionario, anche se i suoi requisiti di memoria sono molto meno rispetto a quella della RAM totale disponibile.

• La valutazione della funzione di hash può richiedere un tempo arbitrariamente lungo. Le stringhe, ad esempio, usano Reflector per esaminare il metodo System.String.GetHashCode - noterete che l'hashing richiede sempre un tempo O (n), il che significa che può richiedere molto tempo per stringhe molto lunghe. Sulla mano, confrontare le stringhe per l'ineguaglianza è quasi sempre più veloce dell'hashing, dal momento che potrebbe richiedere di esaminare solo i primi caratteri. È del tutto possibile che gli inserti degli alberi siano più veloci degli inserimenti del dizionario se la valutazione del codice hash richiede troppo tempo. Metodo

  • di Int32 GetHashCode è letteralmente return this, quindi si sarebbe hardpressed per trovare un caso in cui una tabella hash con le chiavi int è più lento di un dizionario albero.

alberi RB hanno alcune proprietà desiderabili:

• Potete trovare/rimuovere gli elementi Min e Max in O (log n), rispetto a O (n) utilizzando un dizionario.

• Se un albero viene implementato come elenco collegato anziché come matrice, l'albero è in genere più efficiente in termini di spazio rispetto a un dizionario.

• Allo stesso modo, è ridicola la facile scrittura di versioni immutabili di alberi che supportano l'inserimento/ricerca/eliminazione nel tempo O (log n). I dizionari non si adattano bene all'immutabilità, dal momento che è necessario copiare l'intero array interno per ogni operazione (in realtà, I hanno visto alcune implementazioni basate su array di finger tree immutabili, una sorta di struttura di dati del dizionario generale, ma l'implementazione è molto complesso).

• È possibile attraversare tutti gli elementi di un albero in ordine ordinato in spazio costante e tempo O (n), mentre è necessario eseguire il dump di una tabella hash in un array e ordinarlo per ottenere lo stesso effetto.

Quindi, la scelta della struttura dati dipende molto dalle proprietà necessarie. Se vuoi solo una borsa non ordinata e puoi garantire che la tua funzione di hash valuta rapidamente, vai con un dizionario .Net. Se hai bisogno di una borsa ordinata o hai una funzione hash a esecuzione lenta, vai con TreeDictionary.

Answer 2

Mi sembra che tu stia facendo un'ottimizzazione prematura.

Quello che ti suggerisco di creare è un'interfaccia per isolare la struttura che stai effettivamente utilizzando e quindi implementare l'interfaccia utilizzando il dizionario (che sembra funzionare meglio).

Se la memoria/prestazioni diventa un problema (che probabilmente non sarà per 20k- numeri), è possibile creare altre implementazioni di interfaccia e verificare quale funziona meglio. Non avrai bisogno di cambiare quasi nulla nel resto del codice (eccetto quale implementazione stai usando).

Answer 3

Ha senso che un nodo ad albero richiederebbe più spazio di memorizzazione di una voce di dizionario. Un nodo di un albero binario deve memorizzare il valore e entrambi i sottoalberi sinistro e destro. Il generico Dictionary<TKey, TValue> è implementato come una tabella hash che, presumo, utilizza un elenco collegato per ciascun segmento (valore più un puntatore/riferimento) o una sorta di rimappatura (solo il valore). Dovrei dare un'occhiata a Reflector per essere sicuro, ma per lo scopo di questa domanda non penso sia così importante.

Il parser della tabella hash, meno efficiente in termini di memoria/archiviazione. Se si crea una tabella hash (dizionario) e si inizializza la sua capacità su 1 milione, e lo si riempie solo di 10.000 elementi, allora sono abbastanza sicuro che mancherà molta più memoria di un BST con 10.000 nodi.

Tuttavia, non mi preoccuperei di nulla se la quantità di nodi/chiavi è solo in migliaia. Questo verrà misurato nei kilobyte, rispetto ai gigabyte della RAM fisica.

---

Se la domanda è "perché si vuole usare un albero binario invece di una tabella di hash?" Quindi la migliore risposta IMO è che gli alberi binari sono ordinati mentre quelli hash non lo sono. Puoi cercare una tabella hash solo per le chiavi che sono esattamente uguali a qualcosa; con un albero, puoi cercare un intervallo di valori, il valore più vicino, ecc. Questa è una distinzione piuttosto importante se stai creando un indice o qualcosa di simile.

Answer 4

L'interfaccia per un albero e una tabella di hash (che sto cercando di indovinare è ciò che il vostro dizionario è basato uno) dovrebbe essere molto simile. Girare sempre attorno a ricerche con chiave.

avevo sempre pensato un dizionario era meglio per la creazione di cose una volta e poi poi facendo un sacco di ricerche su di esso. Mentre un albero era meglio se lo stavi modificando in modo significativo. Tuttavia, non so da dove ho preso questa idea.

(I linguaggi funzionali utilizzano spesso gli alberi come base per le raccolte poiché è possibile riutilizzare la maggior parte dell'albero se si apportano piccole modifiche ad esso).

Answer 5

Non stai confrontando "mele con mele", un BST ti darà una rappresentazione ordinata mentre un dizionario ti consente di effettuare una ricerca su una coppia di valori chiave (nel tuo caso).

Non mi aspetterei molta dimensione nell'impronta di memoria tra i 2 ma il dizionario fornirà una ricerca molto più veloce. Per trovare un oggetto in un BST devi (potenzialmente) attraversare l'intero albero. Ma per fare una ricerca definitiva è sufficiente cercare in base alla chiave.