Comprendre les arbres de fusion?

je suis tombé sur le Wikipedia page pour eux:Comprendre les arbres de fusion?

Et je lis la classe note pdfs liées au fond, mais il obtient la main ondulée sur la structure de données elle-même et va dans beaucoup de détails sur la fonction sketch(x). Je pense qu'une partie de ma confusion est que les documents essaient d'être très généraux, et j'aimerais un exemple précis à visualiser.

Cette structure de données est-elle appropriée pour stocker des données basées sur des clés entières arbitraires de 32 ou 64 bits? En quoi diffère-t-il d'un arbre B? Il y a une section qui dit que c'est un B-tree avec un facteur de ramification B = (lg n)^(1/5). Pour un arbre entièrement peuplé avec des clés de 32 bits, B serait 2. Est-ce que cela devient un arbre binaire? Cette structure de données est-elle destinée à utiliser des chaînes de bits beaucoup plus longues en tant que clés?

Mon googling n'a rien révélé de terriblement utile, mais j'accueillerais de bons liens sur le sujet. C'est vraiment juste une curiosité passagère, donc je n'ai pas été prêt à payer pour les PDF au portal.acm.org pour le moment.

Source

2010-10-07 xscott

Je pense qu'il obtient 5 clés dans un nœud B arbre à 32 bits. –

@ xscott- Vous voudrez peut-être examiner les arbres de van Emde Boas (vEB-trees) comme alternative. Les arbres de fusion s'exécutent dans O (lg n/lg ng), où vEB-arbres s'exécutent en O (lg lg n) temps par opération, avec est asymptotiquement plus rapide. De plus, les arbres vEB sont sensiblement plus faciles à comprendre que les arbres de fusion, au moins à mon humble avis. – templatetypedef

J'ai lu (juste un passage rapide) le papier séminal et semble intéressant. Il répond également à la plupart de vos questions dans la première page.

Vous pouvez télécharger le document de here

HTH!

Source

2010-11-04 02:11:08

Je jure de respecter les conditions. Merci pour le lien! – xscott

Friggin Rapidshare ne me laisse pas télécharger le lien. Très frustrant vraiment. – xscott

@xscott Il vous suffit de suggérer une autre façon de partager un pdf dans un environnement partiellement privé (c'est-à-dire non indexé par google) afin de préserver le "non-republier" limitation de copyright –

J'ai lu le document sur l'arbre de fusion. Les idées sont assez intelligentes, et par des termes de notation O, il peut plaider pour une victoire.

Ce n'est pas clair pour moi que c'est une victoire en pratique. Le facteur constant est très important et les concepteurs de puces travaillent très dur pour gérer des références locales bon marché.

Il doit avoir B dans ses faux arbres B assez petit pour les machines réelles (B = 5 pour 32 bits, peut-être 10 pour 64 bits). Que de nombreux pointeurs s'inscrivent à peu près dans une ligne de cache. Après la première ligne de cache tactile (qu'il ne peut pas éviter) de plusieurs centaines de cycles, vous pouvez faire une recherche linéaire à travers les touches en quelques cycles par touche, ce qui signifie qu'une implémentation traditionnelle de B-tree codée avec soin devrait dépasser les arbres de fusion. (J'ai construit un tel code B-tree pour soutenir notre système de transformation de programme).

Il revendique une liste d'applications, mais il n'y a pas de chiffres comparatifs.

Quelqu'un at-il des preuves tangibles? (Implémentations et comparaisons?)

Source

2010-11-09 18:51:52

Bienvenue dans le monde de la théorie. Considérons: si n est <= 2^32 alors loglog n est 5. Donc si la constante de notation O augmente de cinq fois (par rapport à une solution log n), alors vous ne gagnez rien, ou même perdez. L'importance de ce résultat est théorique: il est possible en principe de surmonter asymptotiquement la barrière log n. BTW, il y a eu des progrès depuis. Le meilleur tri d'algo à ce jour fait O (n loglog n). – Ari

@Ari: Oui, connais la théorie et la pratique: -} Réf à O (n loglog n) papier? A-t-il le même problème de constantes en pratique? –

Y. Han, tri déterministe en temps O (n loglog n) et espace linéaire. STOC 2002, p. 602-608. La version de journal est J. Algorithms 50 (1): 96-105 (2004). Je n'ai pas tout lu, mais étant donné qu'il se fonde sur Fusion Arbres et arbres exponentiels, je dois dire qu'il n'y a aucun moyen que la constante lui permette de battre le tri classique O (n log n) pour n pratique. – Ari

L'idée derrière l'arbre de fusion est en réalité assez simple. Supposons que vous ayez des clés w-bit (disons 64 bits), l'idée est de compresser (c'est-à-dire d'esquisser) toutes les 64 touches consécutives dans un tableau de 64 éléments. La fonction d'esquisse assure une correspondance temporelle constante entre les clés d'origine et l'index de tableau pour un groupe donné. La recherche de la clé devient alors la recherche du groupe contenant la clé, qui est O (log (n/64)). Comme vous pouvez le voir, le principal défi est la fonction d'esquisse.

Source

2016-02-28 16:19:43 jzl106

Répondre

Questions connexes