Comprensione degli alberi di fusione?

mi sono imbattuto nel Wikipedia page per loro:Comprensione degli alberi di fusione?

e ho letto la classe note file PDF collegati in fondo, ma diventa a mano ondulato sulla struttura dati in sé e va in un sacco di dettagli su la funzione sketch(x). Penso che parte della mia confusione sia che i giornali stanno cercando di essere molto generici e vorrei un esempio specifico da visualizzare.

Questa struttura dati è appropriata per la memorizzazione di dati in base a chiavi arbitrarie a 32 o 64 bit integer? Come si differenzia da un albero B? C'è una sezione che dice che è fondamentalmente un B-tree con un fattore di ramificazione B = (lg n)^(1/5). Per un albero completamente popolato con chiavi a 32 bit, B sarebbe 2. Questo diventa solo un albero binario? Questa struttura dati ha l'intenzione di utilizzare stringhe di bit molto più lunghe come chiavi?

My Googling non ha rivelato nulla di molto utile, ma gradirei qualsiasi link valido sull'argomento. Questa è davvero solo una curiosità passeggera, quindi non sono stato disposto a pagare i PDF allo portal.acm.org.

fonte

2010-10-07 xscott

Penso che ottenga 5 chiavi in un nodo ad albero B a 32 bit. –

@ xscott- Si consiglia di esaminare gli alberi di Van Emde Boas (vEB-trees) come alternativa. Gli alberi di fusione corrono in O (lg n/lg lg n), dove gli alberi di vEB vengono eseguiti in tempo O (lg lg n) per operazione, con asintoticamente più veloce. Inoltre, gli alberi di vEB sono sostanzialmente più facili da capire degli alberi di fusione, almeno IMHO. – templatetypedef

Ho letto (solo un passaggio rapido) la carta seminale e mi sembra interessante. Risolve anche la maggior parte delle tue domande nella prima pagina.

È possibile scaricare la carta dal here

HTH!

fonte

2010-11-04 02:11:08

Giuro di rispettare le condizioni. Grazie per il link! – xscott

Friggin Rapidshare non mi permette di scaricare il link. Davvero molto frustrante. – xscott

@xscott Solo suggerire un altro modo per condividere un pdf in un ambiente parzialmente privato (cioè non indicizzato da google) per preservare la "non ripubblicazione" Limitazione del copyright –

Ho letto la carta dell'albero di fusione. Le idee sono abbastanza intelligenti, e con termini di notazione O può dare il caso di vincere.

Non è chiaro per me che sia una vittoria in pratica. Il fattore costante conta molto e i progettisti di chip lavorano molto duramente per gestire riferimenti locali economici.

Deve avere B nei suoi finti alberi B piuttosto piccoli per macchine reali (B = 5 per 32 bit, forse 10 per 64 bit). Che molti indicatori si adattino praticamente a una linea di cache. Dopo il primo tocco di linea della cache (che non può evitare) di diverse centinaia di cicli, puoi eseguire praticamente una ricerca lineare attraverso i tasti in pochi cicli per chiave, il che significa che un'implementazione tradizionale con B-tree attentamente codificata sembra come dovrebbe superare gli alberi di fusione. (Ho costruito tale codice B-tree per supportare il nostro sistema di trasformazione del programma).

Richiede un elenco di applicazioni, ma non ci sono numeri comparativi.

Qualcuno ha qualche prova concreta? (Implementazioni e confronti?)

fonte

2010-11-09 18:51:52

Benvenuti nel mondo della teoria. Considera: se n è <= 2^32 allora loglog n è 5. Quindi se la costante di notazione O aumenta di cinque volte (rispetto a una soluzione di log n), non ottieni nulla, o addirittura perdi. L'importanza di questo risultato è teorica: in linea di principio è possibile superare asintoticamente la barriera log n. A proposito, ci sono stati progressi da allora. Il miglior ordinamento di interi ora è aggiornato O (n loglog n). – Ari

@ Ari: Sì, conosci teoria e pratica: -} Ref to O (n loglog n) paper? Ha lo stesso problema di costanti nella pratica? –

Y. Han, ordinamento deterministico in O (n loglog n) tempo e spazio lineare. STOC 2002, pp. 602-608. La versione ufficiale è J. Algorithms 50 (1): 96-105 (2004). Non ho ancora letto tutto, ma dato che si basa su Fusion Trees ed Exponential Trees dovrei dire che non c'è modo che la costante gli consenta di battere l'ordinamento convenzionale O (n log n) per qualsiasi n pratico. – Ari

L'idea alla base dell'albero della fusione è in realtà abbastanza semplice. Supponiamo che tu abbia le chiavi w-bit (diciamo a 64 bit), l'idea è di comprimere (cioè abbozzare) ogni 64 tasti consecutivi in un array di 64 elementi. La funzione di schizzi assicura una mappatura temporale costante tra le chiavi originali e l'indice di array per un determinato gruppo. Quindi, la ricerca della chiave diventa la ricerca del gruppo contenente la chiave, che è O (log (n/64)). Come puoi vedere, la sfida principale è la funzione di disegno.

fonte

2016-02-28 16:19:43 jzl106

Comprensione degli alberi di fusione?

risposta

Problemi correlati