Pourquoi utiliser binaire rechercher s'il y a ternaire recherche?

https://stackoverflow.com/questions/3498382

29-09-2019
|

Question

J'ai récemment entendu parler ternaire recherche où l'on divise un tableau en 3 parties et comparer. Ici, il y aura deux comparaisons, mais il réduit le tableau à n / 3. Pourquoi ne pas que les gens utilisent autant?

La solution

En fait, les gens font usage des arbres k-aire pour k arbitraire.

Ceci est cependant un compromis entre.

Pour trouver un élément dans un arbre k-aire, vous avez besoin autour k * opérations ln (N) / ln (k) (rappelez-vous la formule de changement de base). Plus votre k est, les opérations plus générales dont vous avez besoin.

L'extension logique de ce que vous dites est « pourquoi ne pas que les gens utilisent un arbre N-aire pour les éléments de données N? ». Ce qui, bien sûr, serait un tableau.

Autres conseils

Une recherche ternaire vous donnera toujours la même complexité asymptotique O (log N) temps de recherche, et ajoute de la complexité à la mise en œuvre.

Le même argument peut dire pourquoi vous ne voudriez pas une recherche de quad ou de tout autre ordre supérieur.

Recherche 1 milliard (un milliard US - 1000000000) triées articles prendraient une moyenne d'environ 15 compare à la recherche binaire et environ 9 avec une recherche compare ternaire - pas un énorme avantage. Et notez que chaque « ternaire comparer » pourrait impliquer 2 comparaisons réelles.

Wow. Le plus Votés réponses manquer le bateau sur celui-ci, je pense.

Votre CPU ne supporte pas une seule opération ternaire logique; il casse la logique ternaire en plusieurs étapes de la logique binaire. Le plus code optimal pour la CPU est logique binaire. Si les puces étaient communes qui ont soutenu comme une seule opération logique ternaire, vous auriez raison.

B-arbres peut avoir plusieurs branches au niveau de chaque noeud; un arbre B-3 est l'ordre logique ternaire. Chaque pas vers le bas l'arbre prendra deux comparaisons au lieu d'un, et ce sera probablement l'amener à être plus lent dans le temps CPU.

B-arbres, cependant, sont assez communs. Si vous supposez que chaque nœud de l'arbre sera stocké quelque part séparément sur le disque, vous allez passer plus de temps à lire à partir du disque ... et la CPU ne sera pas un goulot d'étranglement, mais le disque sera. Donc, vous prenez un B-arbre avec 100.000 enfants par nœud, ou tout autre volonté à peine rentrent dans un bloc de mémoire. B-arbres avec ce genre de facteur de branchement serait rarement plus de trois nœuds de haut, et que vous avez seulement trois lectures de disque - trois arrêts à un goulot d'étranglement -. À la recherche d'un ensemble de données énorme, énorme

Révision:

arbres ternaires ne sont pas pris en charge par le matériel, ils courent moins vite.
B-tress commandes beaucoup, beaucoup, beaucoup plus élevé que 3 sont communs pour le disque d'optimisation de grands ensembles de données; une fois que vous avez Dépassé 2, aller plus haut que 3.

La seule façon une recherche ternaire peut être plus rapide qu'une recherche binaire est si une détermination de partition 3 voies peut être fait pendant moins d'environ 1,55 fois le coût d'une comparaison 2 voies. Si les éléments sont stockés dans un tableau trié, la détermination à 3 voies sera en moyenne 1,66 fois plus cher que la détermination 2 voies. Si des informations sont stockées dans un arbre, cependant, le coût pour aller chercher l'information est élevé par rapport au coût de comparer réellement, et la localité de cache signifie que le coût d'aller chercher au hasard une paire de données connexes ne sont pas bien pire que le coût d'aller chercher un donnée, un arbre ternaire ou n voies peut améliorer considérablement l'efficacité.

Qu'est-ce que vous fait penser la recherche ternaires devrait être plus rapide?

Nombre moyen de comparaisons:

in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search  =                   1 * ln(n)/ln(2) ~ 1.443*ln(n).

Le pire nombre de comparaisons:

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search  = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

Il semble donc que la recherche ternaire est pire.

En outre, notez que cette séquence se généralise à la recherche linéaire si nous sur

Binary search
Ternary search
...
...
n-ary search ≡ linear search

Alors, dans une recherche de n-aire, nous aurons « un seul COMPARE » qui pourrait prendre jusqu'à n comparaisons réelles.

« Terinary » recherche (ternaire?) Est plus efficace au meilleur des cas, ce qui impliquerait la recherche du premier élément (ou peut-être le dernier, selon la comparaison que vous faites d'abord). Pour les éléments plus loin de la fin que vous vérifiez d'abord, alors que deux comparaisons réduiraient le tableau 2/3 à chaque fois, les deux mêmes comparaisons avec la recherche binaire réduiraient l'espace de recherche par 3/4.

Ajoutez à cela, la recherche binaire est plus simple. Vous venez de comparer et obtenir la moitié ou l'autre, plutôt que de comparer, si moins obtenir le premier tiers, d'autre comparer, si moins obtenir le deuxième tiers, obtenir le reste le dernier tiers.

recherche ternaires peut être utilisé efficacement sur des architectures parallèles - et FPGA ASICs. Par exemple, si la mémoire interne FPGA requise pour la recherche est moins de la moitié de la ressource FPGA, vous pouvez faire un bloc de mémoire en double. Cela permettrait à des adresses mémoire simultanément d'accéder à deux et faire toutes les comparaisons en un seul cycle d'horloge. Ceci est l'une des raisons pour lesquelles 100MHz FPGA peut parfois surperformer le CPU 4GHz:)

Voici des preuves expérimentales au hasard que je ont ne vérifie pas du tout montrant qu'il est plus lent que la recherche binaire.

Presque tous les manuels et sites sur les arbres binaires de recherche ne parlent pas vraiment sur les arbres binaires! Ils vous montrent ternaires arbres de recherche! Les vrais arbres binaires stockent des données dans leurs feuilles non noeuds internes (à l'exception des touches pour naviguer). Certains appellent ces arbres à feuilles et faire la distinction entre les arbres de nœuds indiqués dans les manuels scolaires:

J. Nievergelt, C.-K. Wong: Upper Bounds pour le chemin Durée totale de binaire arbres, Journal ACM 20 (1973) 1-6.

Ce qui suit à ce sujet est du livre de Peter Brass sur les structures de données.

2.1 Deux modèles de recherche Arbres

Dans les grandes lignes tout donné, nous supressed un point important qui semble au premier abord trivial, mais en effet il conduit à deux modèles différents d'arbres de recherche, soit de qui peut être combiné avec une grande partie du matériel suivant, mais dont est fortement préférable.

Si l'on compare à chaque nœud la clé de requête avec la clé contenue dans la noeud et suivez la branche gauche si la clé de requête est plus petite et la branche droite si la clé de requête est plus grande, alors ce qui se passe si elles sont égales? Les deux modèles des arbres de recherche sont les suivants:

Prenez branche gauche si la clé de requête est plus petite que la clé de noeud; sinon prendre la branche droite, jusqu'à ce que vous atteignez une feuille de l'arbre. Les touches du nœud intérieur de l'arbre ne sont à titre de comparaison; tous les objets sont dans les feuilles.
Prenez branche gauche si la clé de requête est plus petite que la clé de noeud; prendre la branche droite si la clé de requête est plus grande que la clé de noeud; et prendre l'objet contenu dans le noeud, si elles sont égales.

Ce point mineur a un certain nombre de conséquences:

{Dans modèle 1, l'arbre sous-jacent est un arbre binaire, alors que dans le modèle 2, chaque noeud d'arbre est vraiment un nœud ternaire avec un voisin milieu spécial.

{1 Dans le modèle, chaque noeud intérieur a un côté gauche et un sous-arbre droit (chacun éventuellement un noeud feuille de l'arbre), alors que dans le modèle 2, nous devons permettre incomplète nœuds, où sous-arbre gauche ou à droite peut-être manquant, et seule la objet de comparaison et la clé sont garantis Exister.

Ainsi, la structure d'un arbre de recherche de modèle 1 est plus régulier que celui d'un arbre de modèle 2; c'est, au moins pour la mise en œuvre, un net avantage.

{Dans le modèle 1, en traversant un noeud intérieur ne nécessite qu'une seule comparaison, alors que dans le modèle 2, nous avons besoin de deux comparaisons pour vérifier les trois possibilités.

En effet, les arbres de la même hauteur dans les modèles 1 et 2 contiennent au maximum environ le même nombre d'objets, mais on a besoin deux fois plus de comparaisons dans le modèle 2 pour atteindre les objets les plus profonds de l'arbre. Bien sûr, dans le modèle 2, il y a aussi certains objets qui ont atteint beaucoup plus tôt; l'objet dans la racine se trouve avec seulement deux comparaisons, mais presque tous les objets sont sur ou à proximité du plus profond niveau.

Théorème. Un arbre de hauteur h et le modèle 1 contient au plus 2 ^ objets h. Un arbre de hauteur h et le modèle 2 contient au plus 2 ^ h + 1 -. 1 objets

Ceci est facilement vu que l'arbre de hauteur h a comme sous-arbres gauche et à droite un arbre de hauteur au plus h - 1 chacun, et dans le modèle d'objet 2 une supplémentaire entre les.

{Dans le modèle 1, les clés de nœuds intérieurs servent uniquement pour des comparaisons et peut réapparaît dans les feuilles pour l'identification des objets. Dans le modèle 2, chaque clé apparaît une seule fois, en même temps que son objet.

Il est même possible dans le modèle 1 qu'il ya des clés utilisées pour la comparaison que n'appartiennent à aucun objet, par exemple, si l'objet a été supprimé. Par séparer conceptuellement ces fonctions de comparaison et d'identification, ce n'est pas surprenant, et dans des structures plus tard, nous pourrions même avoir besoin de définir artificielle Les tests ne correspondant à aucun objet, juste pour obtenir une bonne division de la recherche espace. Toutes les clés utilisées pour la comparaison sont nécessairement distincts parce que dans un modèle Une arborescence, chaque noeud intérieur a gauche non vide et les sous-arbres à droite. Donc, chaque touche se produit au plus deux fois, une fois que la comparaison kEY et une fois comme la clé d'identification la feuille.

Modèle 2 est devenu la version manuel préféré parce que dans la plupart des manuels la distinction entre l'objet et sa clé ne se fait pas: la clé est l'objet. Ensuite, il devient naturel de dupliquer la clé dans l'arborescence. Mais en toutes les applications réelles, la distinction entre la clé et l'objet est très important. On souhaite presque jamais de garder une trace de tout un ensemble de nombres; les nombres sont normalement associés à quelques informations supplémentaires, ce qui est souvent beaucoup plus grande que la clé elle-même.

Vous avez sans doute entendu ternaires recherche utilisé dans les énigmes qui impliquent des choses pesant sur des échelles. Ces échelles peuvent revenir 3 réponses: gauche est plus léger, les deux sont les mêmes, ou à gauche est plus lourd. Ainsi, dans une recherche de ternaire, il ne faut que 1 comparaison. Cependant, les ordinateurs utilisent la logique booléenne, qui a seulement 2 réponses. Pour ce faire, la recherche ternaire, vous auriez fait faire des comparaisons 2 au lieu de 1. Je suppose qu'il ya des cas où ceci est encore plus rapide que des affiches mentionné plus tôt, mais vous pouvez voir que la recherche ternaire est pas toujours mieux, et il est plus confus et moins naturelle à mettre en œuvre sur un ordinateur.

En théorie, le minimum de k/ln(k) est atteint à e et depuis le 3 est plus proche de e de 2 il nécessite moins de comparaisons. Vous pouvez vérifier que 3/ln(3) = 2.73.. et 2/ln(2) = 2.88.. La raison pour laquelle la recherche binaire pourrait être plus rapide est que le code pour elle aura moins de branches et courir plus vite sur les processeurs modernes.

Je viens posté un blog sur la recherche ternaire et je ont montré des résultats. J'ai également fourni quelques implémentations de niveau initial sur mon git repo Je suis totalement d'accord avec tout le monde au sujet de la partie théorique la recherche ternaire, mais pourquoi ne pas essayer? Selon la mise en œuvre cette partie est assez facile si vous avez trois ans d'expérience de codage. Je trouve que si vous avez énorme ensemble de données et vous devez le chercher plusieurs fois la recherche ternaire a un avantage. Si vous pensez que vous pouvez faire mieux avec un aller de recherche ternaire pour elle.

Bien que vous obtenez le même grand-O complexité (ln n) dans les deux arbres de recherche, la différence est dans les constantes. Vous devez faire des comparaisons plus pour un arbre de recherche ternaire à chaque niveau. Donc, la différence se résume à k / ln (k) pour un arbre de recherche k-aire. Cela a une valeur minimale à e = 2,7 et k = 2 fournit le résultat optimal.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow