C # Binary Alberi e Dizionari

StackOverflow https://stackoverflow.com/questions/2151747

Domanda

Sto lottando con il concetto di quando usare alberi binari di ricerca e quando utilizzare dizionari.

Nella mia domanda ho fatto un piccolo esperimento che ha utilizzato il TreeDictionary libreria C5 (che credo sia un albero binario di ricerca rosso-nero), e il dizionario C #. Il dizionario è stato sempre più veloce a add / trovare le operazioni e anche sempre utilizzato meno spazio in memoria. Per esempio, a 16809 voci <int, float>, il dizionario utilizzato 342 KiB mentre l'albero utilizzato 723 KiB.

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. Ciò che dà? C'è un punto dove BST di sono meglio di dizionari?

Inoltre, come una domanda lato, qualcuno sa se esiste un più veloce + più memoria efficiente struttura di dati per la memorizzazione di coppie <int, float> per l'accesso di tipo dizionario rispetto sia delle strutture di cui?

È stato utile?

Soluzione

  

Ho pensato che la BST di avrebbero dovuto   essere più efficiente della memoria, ma sembra   che un nodo dell'albero richiede   più byte di una voce in un   dizionario. Ciò che dà? C'è un   punto in cui BST di sono meglio di   dizionari?

Ho personalmente mai sentito parlare di un tale principio. Ancora oggi, il suo solo un principio generale, non un fatto categorica inciso nel tessuto dell'universo.

In generale, dizionari sono in realtà solo un wrapper fantasia intorno una serie di liste collegate. Si inserisce nel dizionario qualcosa come: 

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 O (+ n internalArray.Length) di memoria, dove n è il numero di elementi della collezione.

In generale i BST può essere implementato come:

  • legati liste, che utilizzano O (n) spazio, dove n è il numero di articoli della collezione.
  • , che utilizzano O (2 h - n) spazio dove h è l'altezza dell'albero e n è il numero di elementi della collezione.
    • 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, il C5 TreeDictionary è implementato usando gli array, che è probabilmente responsabile per lo spazio sprecato.

  

Che cosa dà? C'è un punto dove   BST di sono meglio di dizionari?

I dizionari hanno alcune proprietà indesiderabili:

  • Ci potrebbe 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ò prendere un arbitrariamente lungo periodo di tempo. Strings, ad esempio, utilizzare Reflector per esaminare il metodo System.String.GetHashCode - noterete hashing una stringa sempre prende O (n), il che significa che può richiedere molto tempo per stringhe molto lunghe. Da un lato, confrontando stringhe per la disuguaglianza quasi sempre più veloce di hashing, dal momento che può richiedere guardando solo le prime caratteri. Il suo tutto possibile per inserti albero per essere più veloce di inserti del dizionario se la valutazione codice hash richiede troppo tempo.

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

Gli alberi RB hanno alcune proprietà desiderabili:

  • Si possono trovare / rimuovere gli elementi Min e Max in O (log n), rispetto al tempo O (n) usando un dizionario.

  • Se un albero è implementata come lista collegata, piuttosto che un array, l'albero è di solito più spazio efficiente di un dizionario.

  • Allo stesso modo, la sua ridicola facile scrivere versioni immutabili di alberi che sostengono di inserimento / ricerca / cancellazione in O (log n). Dizionari non si adattano bene alla immutabilità, dal momento che è necessario copiare l'intero array interno per ogni operazione (in realtà, I sono visto alcune implementazioni basate su array di alberi dita immutabili, una sorta di uso generale di dati dizionario struttura, ma l'implementazione è molto complessa).

  • È possibile attraversare tutti gli elementi in un albero in modo ordinato nello spazio costante e il tempo O (n), mentre avresti bisogno di scaricare una tabella hash in un array e ordinare per ottenere lo stesso effetto.

Quindi, la scelta della struttura dati in realtà dipende da quali proprietà è necessario. Se si desidera solo un sacchetto non ordinata e può garantire che la funzione di hash valutare rapidamente, andare con un dizionario .Net. Se avete bisogno di un sacchetto ordinato o avere una funzione di hash in esecuzione lenta, andare con TreeDictionary.

Altri suggerimenti

Non ha senso che un nodo della struttura richiederebbe più spazio di archiviazione di una voce del dizionario. Un nodo albero binario deve memorizzare il valore e entrambi i sottoalberi sinistro e destro. Il Dictionary<TKey, TValue> generica è implementato come una tabella hash, che - sto supponendo - o usa una lista concatenata per ciascun segmento (valore più uno del puntatore / riferimento) o una sorta di rimappatura (solo il valore). Mi piacerebbe avere una sbirciatina in Reflector per essere sicuri, ma per lo scopo di questa domanda non credo che sia così importante.

La rada la tabella hash, il meno efficiente in termini di archiviazione / memoria. Se si crea una tabella di hash (dizionario) e inizializzate la sua capacità di 1 milione, e solo riempirlo con 10.000 elementi, quindi sono abbastanza sicuro che avrebbe mangiato un sacco più memoria di un BST con 10.000 nodi.

Ancora, non mi preoccuperei di tutto questo se la quantità di nodi / chiavi è solo nell'ordine delle migliaia. Che sta per essere misurato nei kilobyte, a fronte di gigabyte di RAM fisica.

Se la domanda è "perché si vuole usare un albero binario invece di una tabella di hash?" Poi la risposta migliore è IMO che gli alberi binari sono ordinate mentre tabelle hash non lo sono. È possibile cercare solo una tabella hash per le chiavi che sono esattamente uguali a qualcosa; con un albero, è possibile cercare un intervallo di valori, valore più vicino, ecc Questa è una distinzione molto importante se si sta creando un indice o qualcosa di simile.

Mi sembra che stai facendo un'ottimizzazione prematura.

Quello che io suggerirei a voi è quello di creare un'interfaccia per isolare quale struttura si sta usando, e quindi implementare l'interfaccia con il dizionario (che sembra funzionare meglio).

Se la memoria / prestazione diventa un problema (che probabilmente non per 20k- numeri), quindi è possibile creare altre implementazioni di interfaccia, e verificare quale funziona bests. Non sarà necessario cambiare quasi nulla nel resto del codice (tranne che l'attuazione si sta utilizzando).

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. ruota sempre intorno ricerche con chiave.

Avevo sempre pensato che 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 si stesse modificando in modo significativo. Comunque, io non so dove ho preso l'idea dal.

(I linguaggi funzionali spesso usano alberi come base per essi raccolte, come si può ri-uso più dell'albero se si fanno piccole modifiche ad esso).

Non stai confrontando "mele con mele", un BST vi darà un ha ordinato rappresentazione mentre un dizionario permette di fare una ricerca su una coppia chiave-valore (nel tuo caso).

Non mi aspettavo molto di dimensioni nella occupazione di memoria tra il 2, ma il dizionario vi darò una ricerca molto più veloce. Per trovare un elemento in un BST voi (potenzialmente) necessario per attraversare l'intero albero. Ma per fare un dictnary occhiata è sufficiente Lookup in base alla chiave.

Un BST equilibrato è preferibile se è necessario per proteggere la vostra struttura dati da picchi di latenza e di hash collisioni attacchi.

La prima avviene quando una struttura a matrice garantiti cresce una viene ridimensionata, il secondo è una proprietà inevitabile algoritmo di hashing come proiezione dallo spazio infinito ad una gamma limitata intero.

Un altro problema in .NET è che non c'è LOH, e con un dizionario sufficientemente grande si esegue in una frammentazione LOH. In questo caso è possibile utilizzare un BST, pagando un prezzo di grande classe di complessità algoritmica.

In breve, con un BST sostenuta dal mucchio di assegnazione che si ottiene momento peggiore caso O (log (N)), con tabella hash si ottiene O (N) momento peggiore caso.

BST ha un prezzo di O (log (N)) tempo medio, peggio di cache località più allocazioni di heap, ma ha garanzie di latenza ed è protetto dagli attacchi del dizionario e la frammentazione della memoria.

Da notare che la BST è anche un soggetto alla frammentazione della memoria su altre piattaforme, non utilizzando un garbage collector compattazione.

Per quanto riguarda la dimensione della memoria, la classe .NET Dictionary`2 è più efficiente della memoria, perché memorizza i dati come una lista concatenata off-mucchio, che memorizza solo il valore e l'offset. BST deve memorizzare oggetto di intestazione (come ogni nodo è un'istanza di classe sul mucchio), due puntatori, e alcuni dati albero aumentata per gli alberi bilanciati. Ad esempio, un albero rosso-nero avrebbe bisogno di un valore booleano interpretato come colore (rosso o nero). Questo è almeno 6 parole della macchina, se non mi sbaglio. Così, ogni nodo in un albero rosso-nero sul sistema a 64 bit è un minimo di:

3 parole per l'intestazione = 24 byte 2 parole per i puntatori bambino = 16 byte 1 parola per il colore = 8 byte almeno 1 parola per byte il valore 8+ = 24 + 16 + 8 + 8 = 56 byte (+8 byte se l'albero utilizza un puntatore nodo padre).

Allo stesso tempo, la dimensione minima della voce del dizionario sarebbe appena 16 byte.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top