Pourquoi utiliser la recherche binary s’il y a une recherche ternaire?

J’ai récemment entendu parler de la recherche ternaire dans laquelle nous divisons un tableau en trois parties et comparons. Ici, il y aura deux comparaisons mais cela réduit le tableau à n / 3. Pourquoi les gens ne l’utilisent-ils pas beaucoup?

    En fait, les gens utilisent des arbres k-ary pour k arbitraire.

    C’est cependant un compromis.

    Pour trouver un élément dans un arbre k-ary, il vous faut autour des opérations k * ln (N) / ln (k) (rappelez-vous la formule de changement de base). Plus votre k est grand, plus vous avez besoin d’opérations globales.

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

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

    On peut dire le même argument pour savoir pourquoi vous ne voudriez pas une recherche quadri ou tout autre ordre supérieur.

    La recherche de 1 milliard (un milliard de dollars – 1 000 000 000) d’éléments sortingés prendrait en moyenne une quinzaine de comparaisons avec la recherche binary et environ 9 comparent avec une recherche ternaire – ce qui n’est pas un énorme avantage. Et notez que chaque «comparaison ternaire» peut impliquer 2 comparaisons réelles.

    Sensationnel. Je pense que les réponses les mieux votées manquent le bateau sur celui-ci.

    Votre CPU ne prend pas en charge la logique ternaire en une seule opération. il brise la logique ternaire en plusieurs étapes de la logique binary. Le code le plus optimal pour le processeur est la logique binary. Si les puces étaient courantes et supportaient la logique ternaire en une seule opération, vous auriez raison.

    Les B-Trees peuvent avoir plusieurs twigs à chaque nœud; un arbre B-order-3 est une logique ternaire. Chaque étape de l’arborescence prendra deux comparaisons au lieu d’une, ce qui ralentira probablement le temps CPU.

    Les arbres B, cependant, sont assez communs. Si vous supposez que chaque nœud de l’arborescence sera stocké séparément sur le disque, vous passerez le plus clair de votre temps à lire à partir du disque … et le processeur ne sera pas un goulot d’étranglement, mais le disque le sera. Donc, vous prenez un B-Tree avec 100 000 enfants par nœud, ou quoi que ce soit d’autre rentre à peine dans un bloc de mémoire. Les B-Tree avec ce type de facteur de twigment auront rarement plus de trois nœuds de haut, et vous ne disposerez que de trois lectures de disque – trois arrêts à un goulot d’étranglement – pour rechercher un énorme jeu de données énorme.

    Révision:

    • Les arborescences ternaires ne sont pas sockets en charge par le matériel, elles s’exécutent donc moins vite.
    • B-tress avec des commandes beaucoup, beaucoup, beaucoup plus élevé que 3 sont courants pour l’optimisation de grands ensembles de données; une fois que vous avez dépassé 2, passez plus de 3.

    La seule façon pour une recherche ternaire d’être plus rapide qu’une recherche binary consiste à déterminer la détermination d’une partition à trois pour moins de 1,55 fois le coût d’une comparaison bidirectionnelle. Si les éléments sont stockés dans un tableau sortingé, la détermination à 3 voies sera en moyenne 1,66 fois plus coûteuse qu’une détermination bidirectionnelle. Si les informations sont stockées dans une arborescence, le coût d’extraction des informations est élevé par rapport au coût réel de la comparaison et la localisation de la mémoire cache signifie que le coût de l’extraction aléatoire d’une paire de données connexes est bien inférieur au coût d’extraction d’une seule. le datum, un arbre ternaire ou n-way peut grandement améliorer l’efficacité.

    Qu’est-ce qui vous fait penser que la recherche Ternary 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). 

    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 soit pire.

    Notez également que cette séquence se généralise à la recherche linéaire si nous continuons

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

    Ainsi, dans une recherche n-aire, nous aurons “une seule COMPARE” qui pourrait prendre jusqu’à une comparaison réelle.

    La recherche “Terinary” (ternaire?) Est plus efficace dans le meilleur des cas, ce qui impliquerait de rechercher le premier élément (ou peut-être le dernier, selon la comparaison que vous faites en premier). Pour les éléments plus éloignés de la fin que vous vérifiez en premier, alors que deux comparaisons réduiraient le tableau de 2/3 à chaque fois, les deux mêmes comparaisons avec la recherche binary réduiraient l’espace de recherche de 3/4.

    Ajoutez à cela, la recherche binary est plus simple. Il suffit de comparer et d’obtenir la moitié ou l’autre plutôt que de comparer, sinon moins que le premier tiers, sinon comparer, sinon moins que le deuxième tiers, sinon obtenir le dernier tiers.

    La recherche ternaire peut être utilisée efficacement sur des architectures parallèles – FPGA et ASIC. Par exemple, si la mémoire FPGA interne requirejse pour la recherche est inférieure à la moitié de la ressource FPGA, vous pouvez créer un bloc de mémoire en double. Cela permettrait d’accéder simultanément à deux adresses mémoire différentes et d’effectuer toutes les comparaisons en un seul cycle d’horloge. C’est l’une des raisons pour lesquelles le FPGA à 100 MHz peut parfois surpasser le processeur à 4 GHz 🙂

    Voici quelques preuves expérimentales aléatoires que je n’ai pas encore vérifiées, montrant que c’est plus lent que la recherche binary.

    Presque tous les manuels et sites Web sur les arbres de recherche binary ne parlent pas vraiment d’arbres binarys! Ils vous montrent des arbres de recherche ternaires! Les vrais arbres binarys stockent les données dans leurs feuilles et non dans les nœuds internes (sauf pour les clés à naviguer). Certains appellent ces arbres-feuilles et font la distinction entre les arbres-nœuds présentés dans les manuels scolaires:

    J. Nievergelt, C.-K. Wong: Limites supérieures pour la longueur totale de la trajectoire des arbres binarys, Journal ACM 20 (1973) 1–6.

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

    2.1 Deux modèles d’arbres de recherche

    Dans les grandes lignes que nous venons de décrire, nous avons supprimé un point important qui, au premier abord, semble anodin, mais qui conduit à deux modèles différents d’arbres de recherche, l’un ou l’autre étant fortement préférable.

    Si nous comparons dans chaque nœud la clé de requête avec la clé contenue dans le nœud et que nous suivons la twig gauche si la clé de requête est plus petite et la twig droite si la clé de requête est plus grande, que se passe-t-il si elles sont égales? Les deux modèles d’arbres de recherche sont les suivants:

    1. Prenez la twig de gauche si la clé de requête est plus petite que la clé de noeud; sinon, prenez la twig droite jusqu’à ce que vous atteigniez une feuille de l’arbre. Les clés dans le nœud intérieur de l’arbre sont uniquement à titre de comparaison; tous les objects sont dans les feuilles.

    2. Prenez la twig de gauche si la clé de requête est plus petite que la clé de noeud; prendre la twig de droite si la clé de requête est plus grande que la clé de noeud; et prenez l’object contenu dans le nœud s’ils sont égaux.

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

    {Dans le modèle 1, l’arbre sous-jacent est un arbre binary, alors que dans le modèle 2, chaque nœud d’arbre est en réalité un nœud ternaire avec un voisin intermédiaire spécial.

    {Dans le modèle 1, chaque nœud intérieur a un sous-arbre gauche et un sous-arbre droit (chacun étant un nœud feuille de l’arbre), alors que dans le modèle 2, nous devons autoriser des nœuds incomplets. object de comparaison et clé sont garantis pour exister.

    La structure d’un arbre de recherche du modèle 1 est donc plus régulière que celle d’un arbre du modèle 2; c’est, du moins pour la mise en œuvre, un net avantage.

    {Dans le modèle 1, traverser un nœud intérieur ne nécessite qu’une seule comparaison, alors que dans le modèle 2, il faut deux comparaisons pour vérifier les trois possibilités.

    En effet, les arbres de même hauteur dans les modèles 1 et 2 contiennent au plus approximativement le même nombre d’objects, mais il faut deux fois plus de comparaisons dans le modèle 2 pour atteindre les objects les plus profonds de l’arbre. Bien sûr, dans le modèle 2, il y a aussi des objects qui sont atteints beaucoup plus tôt. l’object dans la racine est trouvé avec seulement deux comparaisons, mais presque tous les objects sont sur ou près du niveau le plus profond.

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

    Cela se voit facilement car l’arbre de hauteur h a comme sous-arbre gauche et droit un arbre de hauteur au plus h – 1 chacun, et dans le modèle 2 un object supplémentaire entre eux.

    {Dans le modèle 1, les clés des nœuds intérieurs servent uniquement à des comparaisons et peuvent réapparaître dans les feuilles pour l’identification des objects. Dans le modèle 2, chaque touche apparaît une seule fois, avec son object.

    Il est même possible dans le modèle 1 que certaines clés utilisées pour la comparaison n’appartiennent à aucun object, par exemple si l’object a été supprimé. En séparant conceptuellement ces fonctions de comparaison et d’identification, cela n’est pas surprenant, et dans les structures ultérieures, nous pourrions même avoir besoin de définir des tests artificiels ne correspondant à aucun object, juste pour obtenir une bonne division de l’espace de recherche. Toutes les clés utilisées pour la comparaison sont nécessairement distinctes car dans un arbre du modèle 1, chaque nœud intérieur comporte des sous-arbres gauche et droit non vides. Ainsi, chaque clé apparaît au plus deux fois, une fois comme clé de comparaison et une fois comme clé d’identification dans la feuille.

    Le modèle 2 est devenu la version préférée des manuels scolaires car dans la plupart des manuels, la distinction entre object et clé n’est pas faite: la clé est l’object. Ensuite, il devient naturel de dupliquer la clé dans l’arborescence. Mais dans toutes les applications réelles, la distinction entre clé et object est très importante. On ne veut presque jamais suivre seulement un ensemble de chiffres; les nombres sont normalement associés à d’autres informations, qui sont souvent beaucoup plus grandes que la clé elle-même.

    Vous avez peut-être entendu la recherche ternaire dans ces énigmes qui impliquent de peser des choses sur des balances. Ces échelles peuvent donner 3 réponses: la gauche est plus claire, les deux sont identiques ou la gauche est plus lourde. Donc, dans une recherche ternaire, il ne faut que 1 comparaison. Cependant, les ordinateurs utilisent la logique booléenne, qui n’a que 2 réponses. Pour faire la recherche ternaire, il faudrait en fait faire 2 comparaisons au lieu de 1. Je suppose que dans d’autres cas, cela est encore plus rapide que ce que les affiches précédentes ont mentionné, mais vous pouvez voir que la recherche ternaire n’est pas toujours meilleure et plus déroutant et moins naturel à mettre en œuvre sur un ordinateur.

    Théoriquement, le minimum de k/ln(k) est atteint en e et comme 3 est plus proche de e que 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 binary pourrait être plus rapide est que le code pour elle aura moins de twigs et fonctionnera plus rapidement sur les processeurs modernes. .

    Je viens de poster un blog sur la recherche ternaire et j’ai montré quelques résultats. J’ai également fourni quelques implémentations de niveau initiales sur mon repo git. Je suis totalement d’accord avec tout le monde sur la partie théorique de 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 en codage. J’ai trouvé que si vous avez un grand dataset et que vous devez le chercher plusieurs fois, la recherche ternaire a un avantage. Si vous pensez pouvoir faire mieux avec une recherche ternaire, allez-y.

    Bien que vous obteniez la même complexité big-O (ln n) dans les deux arbres de recherche, la différence réside dans les constantes. Vous devez faire plus de comparaisons 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.