Plus rapide que la recherche binaire pour la liste ordonnée

Question

Y at-il un algorithme qui est plus rapide que la recherche binaire, pour la recherche dans les valeurs triées de tableau?

dans mon cas, j'ai des valeurs triées (peut-être toutes les valeurs de type) dans un tableau A, je dois revenir n si la valeur que je recherchais est à portée de A[n] and A[n+1]

Answer 1

Vous pouvez faire mieux que O (log n) si les valeurs sont des entiers, auquel cas le meilleur temps d'exécution le plus défavorable, en termes de n, est O (sqrt (log n)). Sinon, il n'y a aucun moyen de battre O (log n) sauf s'il y a des motifs dans la séquence d'entrée. Il existe deux approches pour battre O (log n) dans le cas des entiers. D'abord, vous pouvez utiliser des arbres y-fast qui stockent dans une table de hachage tous les préfixes pour lesquels vous stockez au moins un entier avec ce préfixe. Cela vous permet d'effectuer une recherche binaire pour trouver la longueur du préfixe correspondant le plus long. Cela vous permet de trouver le successeur d'un élément pour lequel vous recherchez l'instant O (log w) où w est le nombre de bits dans un mot. Il y a quelques détails à travailler pour faire ce travail et utiliser seulement l'espace linéaire, mais ils ne sont pas trop mauvais (voir le lien ci-dessous). Deuxièmement, vous pouvez utiliser des arbres de fusion, qui utilisent des astuces pour vous permettre d'effectuer des comparaisons w^O (1) en un nombre constant d'instructions, ce qui donne un temps de fonctionnement de O (log n/log w).

Le compromis optimal entre ces deux structures de données se produit lorsque log w = sqrt (log n), donnant un temps de fonctionnement de O (sqrt (log n)).

Pour plus de détails sur ce qui précède, voir des conférences 12 et 13 du cours d'Erik Demaine: http://courses.csail.mit.edu/6.851/spring07/lec.html

Answer 2

Oui et non. Oui, il y a des recherches qui sont plus rapides, en moyenne, qu'une recherche de bissection. Mais je crois qu'ils sont toujours O (lg N), juste avec une constante inférieure.

Vous souhaitez réduire le temps nécessaire à la recherche de votre élément. Généralement, il est souhaitable d'utiliser moins d'étapes, et une façon d'aborder cela est de maximiser le nombre attendu d'éléments qui seront éliminés à chaque étape. Avec la bissection, toujours exactement la moitié des éléments sont éliminés. Vous pouvez faire mieux que cela, SI vous savez quelque chose sur la distribution des éléments. Mais, l'algorithme de choix de l'élément de partition est généralement plus compliqué que le choix du point central, et cette complexité supplémentaire peut submerger tout gain de temps que vous espériez obtenir en utilisant moins d'étapes. Vraiment, dans un problème comme celui-ci, il vaut mieux attaquer les effets de second ordre comme la localisation du cache, que l'algorithme de recherche. Par exemple, lorsque vous effectuez une recherche binaire répétée, les mêmes éléments (premier, deuxième et troisième quartiles) sont très fréquemment utilisés. Par conséquent, les placer dans une seule ligne de cache peut être très supérieur à l'accès aléatoire à la liste. Diviser chaque niveau en disons 4 ou 8 sections égales (au lieu de 2) et faire une recherche linéaire à travers ceux-ci pourrait également être plus rapide que la recherche de bissection, car une recherche linéaire ne nécessite pas de calculer la partition et a aussi moins les dépendances de données pouvant provoquer des caches de cache.

Mais tous ces éléments sont toujours O (lg N).

Answer 3

Vous pouvez toujours les mettre dans une table de hachage, alors la recherche sera O (1). Cependant, cela nécessitera beaucoup de mémoire et si vous continuez d'ajouter des éléments, la table de hachage devra peut-être être remise en place. Le re-sketing est O (n) mais il sera amorti en O (1). Cela dépend essentiellement de savoir si vous pouvez vous permettre cet espace et si le cache potentiel manque.

Answer 4

Si les valeurs de la liste sont réparties uniformément, vous pouvez essayer une division pondérée au lieu d'une division binaire, par ex. Si la valeur désirée est au tiers de la limite inférieure actuelle à la valeur actuelle, vous pouvez essayer l'élément qui est également un tiers du chemin. Cela pourrait gravement souffrir sur les listes où les valeurs sont regroupées.

Answer 5

Une possibilité est de le traiter comme trouver les racines d'une fonction. Fondamentalement, la recherche:

a[i] <= i <= a[i + 1] 

équivaut à:

a[i] - i <= 0 <= a[i + 1] - i 

Ensuite, vous pouvez essayer quelque chose comme la méthode de Newton et ainsi de suite. Ces types d'algorithmes convergent fréquemment plus rapidement qu'une recherche binaire quand ils fonctionnent, mais je ne connais pas d'algorithme dont la convergence est garantie pour toutes les entrées.

http://en.wikipedia.org/wiki/Root-finding_algorithm

Answer 6

En recherche binaire vous diviser la liste en deux « sous-listes » et vous effectuez une recherche que la sous-liste qui peut contenir la valeur. Selon la taille de votre tableau, vous pourriez voir une accélération si vous divisez le tableau en plus de deux épissures.

Vous pouvez déterminer la région de la baie que vous recherchez en conservant un index que vous recherchez en premier. Comme dans un annuaire téléphonique d'une grande ville, où vous pouvez voir de l'extérieur, où vous devez commencer à chercher. (J'ai du mal à exprimer mon idée dans le texte, et je n'ai pas encore trouvé de lien anglais qui l'explique mieux).

Answer 7

Tout d'abord, mesure avant de faire l'optimisation.

Avez-vous vraiment besoin d'optimiser cette recherche?

Si oui, alors d'autre part, pensez d'abord à la complexité algorithmique. Par exemple. pouvez-vous utiliser un arbre (comme un std::map, par exemple) au lieu d'un tableau? Si tel est le cas, cela dépend de la fréquence relative des insertions/suppressions par rapport aux recherches, mais la prémisse d'un tableau trié indique que les recherches sont fréquentes par rapport aux modifications de l'ensemble de données, de sorte qu'il serait logique insertions/suppressions, ce qui rend chaque recherche beaucoup plus rapide - à savoir le temps logarithmique. Si vous trouvez qu'en effet les temps de recherche sont un goulot d'étranglement qui doit être adressé, et non, aucun changement de représentation des données n'est possible, et la liste est courte, alors une recherche linéaire sera généralement plus rapide car elle fait moins de travail par comparision. Sinon, si la liste est plus longue et qu'aucune distribution particulière de valeurs n'est connue ou supposée, et que les valeurs ne peuvent pas être traitées comme numériques, la consommation de mémoire doit être constante (exclure la construction d'une table de hachage, disons) , alors la recherche binaire produit 1 bit d'information par comparaison et est probablement le meilleur que vous pouvez faire pour la première recherche.

Salutations & hth.

Answer 8

Si vous avez une énorme quantité de nombres à trouver, et par un coup de chance ils sont également triés, vous pouvez le faire en O (n + m) où m est le nombre de chiffres à trouver. Fondamentalement, juste votre algorithme de fusion typique, avec une légère modification pour enregistrer quelle valeur chaque nombre vérifié serait inséré avant, si elle devait être insérée dans le tableau.

Vous pouvez toujours échanger de l'espace ... Et le temps d'autres opérations.En supposant que tous vos éléments sont de taille constante p bits, vous pouvez faire un tableau massif qui stocke, pour chaque valeur possible que vous pourriez rechercher, l'indice de la prochaine plus grande valeur actuellement stockée. Ce tableau doit être 2^p * lg (n) bits, où n est le nombre de valeurs stockées. Chaque insertion ou suppression est O (2^p) mais typiquement autour de 2^p/n, parce que vous devez passer par la mise à jour de tous ces indices.

Mais votre recherche est maintenant O (1)! OK, OK, ce n'est pas vraiment pratique. Mais diviser l'entrée en blocs d'une manière similaire pourrait éventuellement réduire la constante devant votre journal. Peut-être.

Answer 9

Qu'en est-il de l'algo suivant? il est appelé recherche exponentielle et est l'une des variantes de la recherche binaire. http://en.m.wikipedia.org/wiki/Exponential_search

Recherche de l'élément k dans le tableau trié A de taille n. Recherche A [2^i] pour i = 0, 1, 2, ... jusqu'à ce que vous dépassiez la position de k dans A. puis effectuez une recherche binaire sur la partie du tableau gauche (plus petite) que i.

int exponential_search(int A[], int key) 
{ 
    // lower and upper bound for binary search 
    int lower_bound = 0; 
    int upper_bound = 1; 

    // calculate lower and upper bound 
    while (A[upper_bound] < key) { 
    lower_bound = upper_bound; 
    upper_bound = upper_bound * 2; 
    } 
    return binary_search(A, key, lower_bound, upper_bound); 
} 

Cet algo fonctionne sur O (log IDX) où IDX est l'indice de k dans A. (les deux stpes sont IDX journal). Dans le pire des cas, l'algo est dans O (log idx), si k est parmi les plus grands éléments de A ou plus grand que tout élément de A. La constante multiplicative est plus grande que pour la recherche binaire mais l'algo fonctionnerait plus vite tableaux et lors de la recherche de données qui est vers le début du tableau.

Je voudrais avoir une idée de la taille minimale n où cet algo devient préférable à la recherche binaire, mais je ne sais pas.

Answer 10

Bien que dans le cas général vous ne puissiez pas faire mieux que O (log N), vous pouvez au moins optimiser cela, réduisant ainsi significativement la constante de proportionnalité devant O (log N).

Si vous devez effectuer plusieurs recherches sur la même baie, vous pouvez les vectoriser en utilisant des extensions SIMD, réduisant ainsi encore plus le coût de calcul.

En particulier, si vous traitez des tableaux de nombres à virgule flottante qui satisfont certaines propriétés, il existe des moyens de construire un index spécial qui permet ensuite de rechercher le tableau dans O (1).

Tous les aspects ci-dessus sont discutés avec les résultats des tests dans: Cannizzo, 2015, Fast and Vectorizable Alternative to Binary Search in O(1) Applicable to a Wide Domain of Sorted Arrays of Floating Point Numbers Le papier est livré avec le code source sur github.