Pourquoi la recherche binaire est-elle plus rapide que la recherche ternaire?

La recherche dans un tableau de éléments à l'aide de la recherche binaire prend, dans le pire des cas, le itérations car, à chaque étape, nous coupons la moitié de notre espace de recherche. Si, au lieu de cela, nous utilisions la "recherche ternaire", nous réduirions les deux tiers de notre espace de recherche à chaque itération, le pire des cas devrait donc prendre itérations ... $N$ $\log_2 N$ $\log_3 N < \log_2 N$

Il semble que la recherche ternaire soit plus rapide, alors pourquoi utilisons-nous la recherche binaire?

algorithms algorithm-analysis runtime-analysis search-algorithms binary-search Le carré moyen
la source

Ne pourrait-on pas utiliser le même raisonnement à propos de la recherche quaternaire? Ou même la recherche décimale ... ou n'importe quoi plus grand que 2.

d'alar'cop

S'il

La recherche linéaire est souvent plus rapide que la recherche binaire sur des problèmes de taille petite à moyenne sur du matériel moderne, car elle est cohérente avec le cache et presque toutes les branches sont correctement prédites.

Pseudonyme le

Aussi 2 * log_3 (N) = log_3 (N ^ 2) si cela parle à votre intuition.

PawelP

Mettons cela en termes intuitifs. Si l'utilisation d'une recherche à 3 est plus rapide parce qu'elle réduit l'espace de recherche à chaque itération, alors l'utilisation d'une recherche à un million n'est-elle pas plus rapide? Mais vous pouvez facilement voir qu'en moyenne, il vous faudrait effectuer 500 000 contrôles dans chaque itération pour déterminer la millionième tranche contenant la cible. Clairement, la réduction de l’espace de recherche de moitié à chaque itération et plus, vous donne le maximum d’ informations en une seule étape, de manière fiable.

ErikE

Réponses:

\log_{2} (n) + O (1)

$\log_2(n)+O(1)$

2 \cdot \log_{3} (n) + O (1)

$2 \cdot \log_3(n) + O(1)$

2 \cdot \log_{3} (n) + O (1) = 2 \cdot \frac{\log (2)}{\log (3)} \log_{2} (n) + O (1)

$2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1)$

2 \cdot \frac{\log (2)}{\log (3)} > 1

$2 \cdot \frac{\log(2)}{\log(3)} > 1$

$n$

$n$ $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ $k$

DCTLib
la source

Et LHS est linéaire et RHS est logarithmique, donc cela ne va pas aider pour un quaternaire ou quelque chose de plus que cela .... Belles explications ... Merci

The Mean Square

Par souci d’exhaustivité, notez qu’une mesure abstraite telle que le nombre de comparaisons d’éléments peut ou non dominer le temps d’exécution réel. En particulier, vous devrez peut-être prendre en compte le nombre d'erreurs de cache que vous êtes susceptible de rencontrer dans de longues baies avec l'une ou l'autre des recherches. (Ici, ils coïncident. Je note cela parce que le PO demande "Pourquoi est-ce plus rapide?", Et répondre à cela par une mesure abstraite peut être trompeur pour certains algorithmes.)

Raphael

Dans une recherche ternaire, 1/3 du temps, vous aurez seulement besoin d'une comparaison (faites une comparaison inférieure: si dans le tiers inférieur, vous n'avez pas besoin de la seconde comparaison). Cela fait ternary seulement environ 5% plus lentement au lieu de 25% (dans ce monde dans lequel nous ne nous soucions que du nombre de comparaisons). Je ne suis pas sûr de savoir comment généraliser ceci à n-aire, bien que je soupçonne que cela ne va jamais plus vite que binaire.

Aaron Dufour

@AaronDufour: Puisqu'il est possible d'effectuer une recherche quaternaire en comparant d'abord l'élément du milieu, puis en ignorant le résultat des autres comparaisons, le seul moyen d'effectuer une recherche quaternaire serait plus rapide si trois comparaisons pouvaient être effectuées en parallèle à moindre coût que deux comparaisons. pourrait être effectuée séquentiellement.

Supercat

@AaronDufour Mais vous amortissez les éléments à rechercher, et je ne comprends pas bien pourquoi c'est acceptable. Dans le pire des cas, les deux comparaisons peuvent être effectuées à chaque étape.

Sasho Nikolov

DCTLib a raison, mais oubliez les calculs une seconde.

Selon votre logique, alors, n -ary devrait être le plus rapide. Mais si vous y réfléchissez, n -ary est exactement égal à une recherche d’itération régulière (il suffit de parcourir la liste 1 par 1, mais dans l’ordre inverse). Tout d'abord, vous sélectionnez le dernier (ou l'avant-dernier) élément de la liste et comparez cette valeur à votre valeur de comparaison. Ensuite, vous supprimez cet élément de votre liste, puis choisissez le dernier élément de la nouvelle liste, qui n'est que l'avant-dernière valeur du tableau. À chaque fois, vous n'élimineriez qu'une valeur à la fois jusqu'à ce que vous trouviez votre valeur.

Au lieu de cela, vous devriez y penser comme ceci: comment puis-je éliminer le plus de valeurs de la liste à chaque itération? Dans une recherche binaire, vous éliminez toujours la moitié de la liste. Dans une recherche ternaire, il est possible (avec 33,33% de chances en réalité) d'éliminer les deux tiers de la liste, mais il est encore plus probable (66,66%) que vous n'éliminiez qu'un tiers de la liste. pour calculer O (n), vous devez regarder le pire des scénarios, qui est 1/3, inférieur à 1/2. À mesure que vous vous rapprochez de n, la situation empire encore davantage.

Non seulement le pire scénario sera amélioré avec la recherche binaire, mais votre temps moyen sera également amélioré. En regardant la valeur attendue (quelle partie de la liste pouvons-nous supprimer en moyenne), nous utilisons cette formule:

(P_lower) x (partie que nous pouvons supprimer si inférieur) + (P_higher) x (partie que nous pouvons supprimer si plus élevé) = E

Pour la recherche binaire, il s’agit de .5x.5 + .5x.5 = .5 (nous supprimons toujours la moitié de la liste). Pour les recherches ternaires, cette valeur est 0,666 x 333 + 0,333 x 666 = 0,44; à chaque étape, nous ne supprimerons probablement que 44% de la liste, ce qui la rend en moyenne moins efficace que la recherche binaire. Cette valeur culmine à 1/2 (la moitié de la liste) et diminue à mesure que vous vous rapprochez de n (itération inverse) et de 0 (itération régulière).

Ok, alors j'ai menti..il y a un peu de math impliquée, mais j'espère que ça aide!

dberm22
la source

C'est une excellente réponse.

The_Sympathizer

L'analyse des limites aide à comprendre les calculs difficiles! La recherche séquentielle n-aire a le même coût que la recherche linéaire O (n).

Shuva

-2

Veuillez noter que l'argument de comparaisons log (N) vs 2 log (N) est basé sur une interprétation naïve de l'algorithme. Si je devais vraiment m'asseoir et écrire ceci dans un assemblage x86, les résultats seraient inversés. Le problème réside dans l'utilisation d'entiers pour les cas de test combinés à un compilateur insuffisamment intelligent qui ne peut pas supprimer les comparaisons redondantes. Réessayez avec des chaînes et une fonction de comparaison de chaînes appropriée, puis codez-la pour appeler la fonction de comparaison une fois par boucle et vous constaterez que la recherche ternaire est encore plus rapide.

Josué
la source

Bien sûr, la recherche ternaire serait plus rapide si vous pouviez le faire avec une seule comparaison par itération. Mais, peu importe si des chaînes ou des entiers, vous ne pouvez pas.

FrankW

Les comparaisons ne seraient pas redondantes et le problème n’a rien à voir avec le compilateur. Afin de diviser l’espace de recherche en trois parties, vous avez besoin de 2 comparaisons. Dans une recherche binaire, vous n'avez qu'à comparer l'élément central et vous savez alors dans quelle moitié de l'espace de recherche se trouverait. Avec la recherche ternaire, vous auriez besoin de comparer avec l'élément situé à liste ET le 2/3 du chemin à travers la liste. Le type de données que vous comparez ou la langue que vous utilisez est sans importance. Accordé, si l'article est dans le 1er 3ème, vous pouvez arrêter après 1 comparaison.

Reirab

Sur certaines plates-formes, la recherche ternaire pourrait être plus rapide car elle laissait plus de temps à la CPU pour extraire les opérandes de la RAM avant de les utiliser pour la comparaison. Mais cela dépend totalement de la plate-forme utilisée, de ses latences et de ses caches.

Jpa

Darn it - mauvaise définition de la recherche ternaire.

Josué