À quelle vitesse pouvez-vous faire de la recherche linéaire?
Je suis à la recherche pour optimiser cette recherche linéaire:
static int
linear (const int *arr, int n, int key)
{
int i = 0;
while (i < n) {
if (arr [i] >= key)
break;
++i;
}
return i;
}
Le tableau est trié, et la fonction est supposée retourner à l'index du premier élément qui est plus grande ou égale à la clé. Ils matrice n'est pas grande (en dessous de 200 éléments) et sera établi une fois pour un grand nombre de recherches. Les éléments du tableau après la n-ième peuvent si nécessaire être initialisé à quelque chose d'approprié, si cela accélère la recherche.
Non, la recherche binaire n'est pas permis de recherche linéaire.
Modifier: Toutes mes connaissances sur ce sujet est maintenant résumée dans ce blog.
- Où est la question?
- La seule chose que vous pouvez faire est de profiter de toutes les instructions SIMD disponibles sur votre plateforme. (Test de quatre à la fois, par exemple.) Mais pourquoi vous ne vous seriez pas binaire de recherche, je ne sais pas.
- Vous n'avez pas à tester chaque élément; vous pouvez tester tous les kième élément si vous êtes alors autorisé à revenir en arrière. Aussi, si vous connaissez la plage d'éléments que vous pouvez mettre en place un tableau / table de hachage qui vous donne la réponse. Mais, vous risquez de ne pas tenir compte de ces "recherche linéaire".
- Pourquoi est-binaire de recherche (arbitrairement?) pas permis? Est-ce un réel problème ou une sorte de devoirs? Parce que si vous allez passer par la peine de trier les données, une recherche binaire est va être votre meilleure interprète.
- (Pensé au hasard: un, deux, sauter une poignée, mais qui peut tomber sur "non linéaire", et si c'est déjà trié, de tout non trivial de n sans le match prévu près de l'avant et associés localité questions ...)
- C'est fondamentalement une recherche binaire, où les "quelques" est "en restant sur la taille du tableau / 2".
- Binaire searsh sera donne de meilleurs résultats que si vous savez que l'élément que vous cherchez se trouve dans un de totalement imprévisible position. Si vous savez que l'élément cible est susceptible d'être à proximité du début du tableau, la recherche linéaire se surpasser les binaires de recherche. L'exemple classique est l'algorithme bien connu de la fusion de deux tableaux triés. Si les tableaux ont longueur à peu près égale, la fusion se fait avec recherche linéaire, depuis binaire sera beaucoup plus lente.
- Rappelez-vous binaire recherches besoin de votre ensemble de données à trier.
- en fait, j'ai lu quelque part que pour le petit tableau, la recherche linéaire peut être plus rapide: lwn.net/Articles/255364 (la discussion est dans les commentaires)
- Serait-il être considéré comme de la triche si vous avez numérisé chaque dixième élément premier et après avoir trouvé le premier pas inférieure à la clé, de revenir et de numérisation des dix dernières élément un par un? Quelle est la racine carrée de n au lieu de 10?
- C'est idéal pour des cas spécifiques, mais il n'y a rien pour indiquer qu'il ya quelque chose de spécial à propos de cet ensemble de données. Dans le cas générique, triés mais sinon piétonne ensemble de données va pour le mieux dans la plupart des cas d'utilisation avec une recherche binaire.
- Oui, pas de balayage de chaque élément serait de la triche. @GMan: Il y a BEAUCOUP de choses que vous pouvez faire avant d'avoir recours à SIMD. @Joe: C'est "à la maison" j'ai donné moi-même, que j'ai également déjà fait. Je suis juste curieux de savoir ce que les gens avec qui je n'ai pas pensé.
- Tout ce que vous faites sera essentiellement un gimped binaire de recherche.
- Voir le top-rated de réponse, par exemple. Beaucoup plus rapide que la simple recherche linéaire (je sais, j'ai comparé).
- Je suis surpris par cela. Quelle différence dérouler quatre faire?
- Dérouler en quatre vitesses en hausse de près de 50% à N=100 sur un Core i7. Dérouler en quatre avec une sentinelle des vitesses de plus de 50%.
- Toujours pas de solutions à l'aide de plusieurs threads?
- Probst: Ouais déroulage peut accélérer les choses, suppose que j'ai besoin de relire mon Code livre Complet 🙂 Voici le déroulement sujet de ce livre stevemcconnell.com/cctune.htm
- Oui, mais regardez le problème: ils ont à mettre en œuvre la recherche linéaire dans un tableau trié. C'est déjà suffisamment non-générique. Cela implique déjà quelque chose de spécifique. Pourquoi serait-on insister sur un linéaire de recherche dans un tableau trié? Peut-être qu'ils le font parce que la structure des requêtes favorise la recherche linéaire en particulier? Par exemple, si vous avez un ensemble ordonné de N éléments et d'avoir à faire à proximité de N commandés requêtes de recherche, différentiels linéaires de recherche sera supérieur à celui de la recherche binaire par un ordre de grandeur au moins.
- Probst: vous compilez avec les optimisations activées, droit?
- recherche binaire avec un prieuré de la connaissance de la distribution des données sera toujours plus rapide que la recherche linéaire dans la plupart des cas, le plus simple est d'utiliser les distances à interpoler linéairement le point charnière pour la prochaine itération au lieu d'aller au milieu de la plage (ce qui fonctionne le mieux si les données sont distribuées de manière uniforme, dans d'autres cas, la formule d'interpolation doit être proche de celle de la distribution)
- Si quelqu'un a insisté sur l'utilisation d'un linéaire de recherche sur les données triées, je voudrais juste revenir un résultat aléatoire, parce que quelqu'un qui insensé de ne pas en connaître la différence.
- Eh bien, si vous avez à faire M triés requêtes dans un tableau de N éléments triés, les asymptotiquement optimal algoirithm procède de la façon suivante: nous avons d'abord effectuer à cheval sur la recherche linéaire avec l'étape [N/M], c'est à dire faire de la recherche linéaire de sauter à chaque [N/M]-ème élément et ensuite faire la recherche binaire dans le segment trouvé de longueur [N/M]. Lorsque M est proche de N, [N/M] devient petit et binaire de recherche est "désactivé". Donc, pas de binarey de recherche, sous les conditions ci-dessus (c'est à dire suffisamment dense triés requêtes pour les mêmes données) ne sera pas plus rapide que la recherche linéaire. La recherche linéaire sera beaucoup plus rapide.
- Le dessus mélange de cheval-la recherche linéaire suivie par la recherche binaire est avéré être asymptotiquement optimale de l'algorithme qui réalise la limite théorique de la recherche de l'efficacité. Donc, pas de binaire de recherche est seulement plus rapide lorsque les requêtes sont rares. La densité des requêtes, la recherche linéaire gagne par une marge énorme. Et, encore une fois, pour les cas intermédiaires, l'algorithme optimal utilise le mélange des deux. Le résultat théorique est disponible à partir de cet article: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.5750
- Ce qui serait probablement le rendre beaucoup plus surprenant de découvrir que les différentiels linéaires de recherche sur les données triées sens parfait lorsque nous avons à faire à de multiples triés requêtes. Lorsque le nombre de requêtes approches de la taille des données, la recherche linéaire surpasse la recherche binaire par un ordre de grandeur. En outre, pour cette raison, pratiquement tout le monde l'utilise (c'est à dire la recherche linéaire) lors de la fusion de données triées. Ils ne réalisent pas que.
- ce n'est pas un
[code-golf]
problème. Si c'était à gauche balisé comme ça elle serait fermée en raison de code de golf de problèmes qui ne sont pas CW constamment fermé - la fusion de données triées prend le temps linéaire, mais ce n'est pas une recherche linéaire. Vous avez raison à propos de la recherche pour plusieurs valeurs à la fois, mais qui ne faisait pas partie de l'OP énoncé du problème.
- Oui, c'est la recherche linéaire 🙂 La classic fusion algorithme pour triés les tableaux repose sur la prise du courant minimal de l'élément dans les deux tableaux, et de l'envoyer vers la sortie. Il n'est pas évident, mais ce n'est en fait rien d'autre qu'un simple recherche linéaire des éléments d'un tableau dans un autre tableau. Il est tout simplement occulté un peu, de sorte que vous ne verrez pas tout de suite, mais la réalité c'est simple et compliqué la recherche linéaire.
- En outre, la même logique s'applique à la fusion ainsi: si vous êtes à la fusion de deux tableaux de l'significativement différents de longueur, il est préférable de passer à la recherche binaire pour la fusion. Mais si la longueur est approximativement le même, nous utilisons l'algorithme classique avec recherche linéaire.
- Je suis en désaccord, puisque les listes sont triées, vous avez des pointeurs pour le plus petit (ou plus grand) élément dans chacune, de sorte que vous ne sont jamais à la recherche du prochain élément de l'un des sous-listes, vous êtes seulement de décider de ce qui sous-liste de l'élément de.
- Non, vous êtes tout simplement en insistant sur une vision précise de ce qui se passe. Voici la althernative vision pour vous: pour effectuer la fusion de prendre le premier élément
a
de tableau triéA
et d'effectuer la recherche linéaire de cet élément dans le tableau triéB
. Ce qui nous donne un [éventuellement vide] de la séquence des éléments de tête dansB
, qui sont plus petits quea
. Nous nous déplaçons à l'intégralité de la séquence de sortie, suivie para
. Puis nous le répétons: prendre l'élément suivanta
deA
... et ainsi de suite. C'est tout. - À première vue, il peut sembler comme un algorithme différent, alors que si vous y réfléchissez un peu, vous verrez que c'est exactement la même classic fusion algorithme, vient d'être décrit en des termes différents 🙂 Encore une fois, la classic fusion algorithme est rien de plus qu'un légèrement obscurci la recherche linéaire. Et encore une fois, si les matrices sont de longueur différente, la façon correcte de faire de la fusion est d'utiliser les binaires de recherche: prendre
a
deA
, faire une recherche binaire dansB
, déplacer le début de la séquence deB
à la sortie, déplacera
à la sortie, de répétition. - Et encore une fois, l'universel asymptotiquement optimale de la stratégie est une combinaison linéaire et binaire de recherche, comme indiqué dans ma réponse ci-dessous.
Vous devez vous connecter pour publier un commentaire.
Bien, il fait à peu près autant de sens que d'une recherche linéaire dans un tableau trié!
(Plus sérieusement, pouvez-vous nous donner quelques indices sur le pourquoi de pas de binaire de recherche?)
Jusqu'à présent vous avez reçu plusieurs conseils plus que la recherche linéaire n'a pas de sens sur les données triées, quand binaire de recherche va travailler beaucoup plus efficacement à la place. Cela arrive souvent d'être l'un de ceux populaire "sonne juste" affirmations faites par des gens qui ne se soucient pas de donner le problème de trop de la pensée. En réalité, si l'on considère l'image plus grande, étant donné les bonnes circonstances, la recherche linéaire peut être beaucoup plus efficace que la recherche binaire.
Noter, que si nous considérons un unique requête de recherche pour un tableau trié, binaire de recherche est beaucoup plus efficace méthode de recherche linéaire. Il n'y a aucun argument à ce sujet. Aussi, lorsque vous effectuez plusieurs complètement aléatoire requêtes pour les mêmes données binaires de recherche gagne encore plus de la recherche linéaire.
Cependant, l'image commence à changer si nous considérons séquentielle des requêtes de recherche et ces requêtes ne sont pas exactement au hasard. Imaginez que les requêtes arrivent dans l'ordre de tri, c'est à dire chaque requête suivante est une valeur plus grande que la précédente requête. I. e. les requêtes sont également triés. BTW, ils n'ont pas à être à l'échelle mondiale et strictement triés, de temps à autre la séquence requête pourrait obtenir "reset", c'est à dire une valeur faible est interrogé, mais sur la moyenne de conséquence, les requêtes doivent arriver dans l'ordre croissant. En d'autres termes, les requêtes arrivent dans série, chaque série triée dans l'ordre croissant. Dans ce cas, si la durée moyenne de la série est comparable à la longueur de votre tableau, la recherche linéaire sera surpasser binaire de recherche par une marge énorme. Toutefois, afin de prendre avantage de cette situation, vous avez à mettre en œuvre votre recherche dans différentiels manière. C'est simple: si la requête suivante est plus grande que la précédente, vous n'avez pas besoin de lancer la recherche à partir du début du tableau. Au lieu de cela, vous pouvez effectuer une recherche à partir du point où la recherche précédente arrêté. La plus simpliste de la mise en œuvre (juste pour illustrer l'idée) peut se présenter comme suit
(Avertissement: la mise en œuvre est terriblement laid pour la raison évidente que le tableau est d'arriver de l'extérieur comme un paramètre, tandis que la recherche précédente de l'état est stocké en interne. Certes, c'est une mauvaise façon de le faire dans la pratique. Mais encore une fois, le ci-dessus est destiné à illustrer l'idée et pas plus).
Noter que la complexité de traitement de chaque série ordonnée de requêtes à l'aide de l'approche ci-dessus est toujours
O(N)
, indépendamment de la longueur de la série. En utilisant le binaire de recherche, la complexité seraitO(M * log N)
. Donc, pour des raisons évidentes lorsqueM
est proche deN
, c'est à dire les requêtes arrivent dans suffisamment longue série ordonnée, la recherche linéaire de manière significative surpasser binaire de recherche, tandis que pour les petitesM
la recherche binaire va gagner.Aussi, même si la série ordonnée de requêtes ne sont pas très longues, la modification ci-dessus peut encore vous donner une amélioration notable des performances de la recherche, de l'examen que vous ont à utiliser pour la recherche linéaire.
P. S. Comme une pièce supplémentaire de l'information sur la structure du problème:
Quand vous en avez besoin pour effectuer la recherche dans un tableau ordonné de longueur
N
et vous savez à l'avance que les demandes qui arriveront dans l'ordre de la série de [approximative, moyenne] longueurM
, l'algorithme optimal sera comme suitS = [N/M]
. Il peut aussi prendre le sens de "snap" la valeur deS
à l' [proche] puissance de 2. Pensez à votre tableau trié comme une séquence de blocs de longueurS
- dits S-blocs.S
(bien sûr, n'oubliez pas de démarrer à partir du bloc où la recherche précédente gauche).Ci-dessus est la plus optimale incrémentale de l'algorithme de recherche possible, dans un sens qu'il permet d'atteindre la limite théorique sur l'asymptotique de l'efficacité d'une répétition de recherche. Notez que si la valeur de
M
est beaucoup plus petite que laN
, l'algorithme de "automatiquement" l'évolution vers binaire de recherche, alors que quandM
est proche deN
l'algorithme de "automatiquement" favorise linéaire de recherche. Ce dernier a un sens, car dans un tel environnement, la recherche linéaire est significativement plus efficace que la recherche binaire.Tout cela c'est juste pour illustrer le fait que les déclarations générales comme "la recherche linéaire sur un tableau trié est toujours inutile" indiquent rien d'autre que le manque de connaissances de la part de ceux qui font de telles déclarations.
Puisque vous pouvez mettre des valeurs connues après la dernière entrée valide, ajouter un élément supplémentaire n+1 = max assurez-vous que la boucle ne va pas au-delà de la fin du tableau sans avoir à tester pour i < n.
Vous pouvez également essayer de dérouler la boucle, avec la même valeur sentinelle:
i
à-1
, puis pré-incrémentation dans le tableau d'indexation dans votre déroulée en boucle exemple. Qui vous fera économiser supplémentaires--i
à la fin.Tout d'abord, toute solution rapide doit utiliser la vectorisation de comparer de nombreux éléments à la fois.
Cependant, tous les vectorisé implémentations posté jusqu'à présent souffrent d'un problème commun: ils ont des branches. En conséquence, ils doivent introduire blockwise traitement de la matrice (afin de réduire les frais de branchement), ce qui conduit à de faibles performances pour les petits tableaux. Pour les grands tableaux de la recherche linéaire est de pire qu'un bien optimisé binaire de recherche, donc il n'y a pas de point dans l'optimisation de ce dernier.
Cependant, la recherche linéaire peut être mis en œuvre sans branches à tous. L'idée est très simple: l'index que vous voulez, c'est précisément le nombre d'éléments du tableau qui sont inférieures à la clé que vous recherchez. De sorte que vous pouvez comparer chaque élément du tableau à la valeur de la clé et la somme de tous les indicateurs:
Une chose amusante à propos de cette solution est qu'il serait de retour la même réponse, même si vous mélangez les array =) Bien que cette solution semble être assez lent, il peut être vectorisées avec élégance. La mise en œuvre fournis ci-dessous nécessite tableau 16 octets aligné. Aussi, le tableau doit être rempli avec INT_MAX éléments, car elle consomme 16 éléments à la fois.
La finale de la réduction d'un seul SSE2 registre peut être mis en œuvre avec SSE2 seulement si nécessaire, il ne devrait pas vraiment d'incidence sur la performance globale.
Je l'ai testé avec Visual C++ 2013 x64 compilateur Intel Core2 Duo E4700 (assez vieux, ouais). Le tableau de taille 197 est généré avec des éléments fournis par rand(). Le code complet avec tous les tests est ici. Voici le temps de réaliser de 32M de recherche:
L'OP le code original de processus de 10,6 millions de tableau par seconde (2,1 milliards d'éléments par seconde). L'suggéré code processus de 29,5 millions de matrices par seconde (5.8 milliards d'éléments par seconde).
Aussi, le code fonctionne bien pour les petits tableaux: même pour des matrices de 15 éléments, il est encore presque trois fois plus rapide que l'OP du code d'origine.
Ici est l'assembly généré:
Enfin, je tiens à noter qu'un bien optimisé binaire de recherche peut être effectuée plus rapidement en passant à l'décrit vectorisé la recherche linéaire dès que l'intervalle devient petit.
Mise à JOUR: Plus d'informations peuvent être trouvées dans mon blog sur la question.
Si vous êtes sur une plate-forme Intel:
mais qui ne trouve des correspondances exactes, ne sont pas plus grand que ou égal matchs.
En C, vous pouvez également utiliser Duff de l'Appareil:
repne scasd
est important de démarrage des frais généraux, et n'est même pas très vite par rapport à SIMD. (rep stos
etrep movs
sont de bonne qualité (en particulier pour les gros blocs à l'amortissement de leur démarrage, les frais généraux), et à l'intérieur fonctionner dans des de 16 octets ou 32 octets de morceaux, mais autant que je sache, le conditionnel rep-instructions de chaîne (scas et cmps) ne sont pas beaucoup plus qu'un scalaire boucle mises en œuvre dans le microcode.) Voir Agner de la Brume insn tables et l'Optimisation de l'Assemblée guide, et aussi d'autres liens dans le x86 balise wiki, à l'instar d'Intel manuel d'optimisation.Si une cible spécifique de la solution est acceptable, alors vous pouvez très facilement utiliser SIMD (ESS, AltiVec, ou ce que vous avez à disposition) pour obtenir ~ 4x speed-up en testant des 4 éléments à la fois plutôt que de simplement 1.
Intérêt, j'ai mis en place un simple SIMD mise en œuvre comme suit:
Sur un 2,67 GHz Core i7, de l'utilisation d'OpenSUSE x86-64 et gcc 4.3.2, je me déplace
7x - 8x
amélioration autour d'un assez large, de "sweet spot" où n = 100000 avec à la clé trouvée au milieu du tableau (c'est à dire result = n /2). Le rendement tombe à environ3.5x
lorsque n devient grand et le tableau est donc supérieur à la taille du cache (sans doute devenir la mémoire de la bande passante limitée dans ce cas). Performance diminue lorsque n est petit, en raison de l'inefficacité de la SIMD mise en œuvre (il a été optimisée pour n grand, bien sûr).8x
plus vite que les scalaires code, au mieux, avec le tableau des tailles de l'ordre de 100000 et la valeur de la clé étant trouvé à la moitié du tableau. Il tombe à environ3.5x
pour de très grands tableaux.gcc -O3
et c'est un x86-64 exécutable (deux fois plus nombreux registres SSE que les x86). Quand j'ai le temps, il je vais le faire dans une boucle (100 itérations) et en prenant le minimum de temps, ce qui signifie que pour tous, mais la première itération les caches être amorcée. Si vous êtes juste en timing une itération puis vos mesures peuvent être faussées. Et oui, bien sûr, la performance sera pareil pour les petits tableaux qui est attendu puisque la routine évalue les blocs de la matrice plutôt que des éléments individuels ou des vecteurs.Vous avez reçu de nombreuses suggestions pour des améliorations, mais vous avez besoin de mesurer chaque optimisation pour voir ce qui est au mieux de votre matériel et de votre compilateur.
Comme un exemple, dans la première version de cette réponse, j'ai deviné que par 100-200 les éléments du tableau, de la légère hausse des frais indirects de la recherche binaire devrait facilement être payé par beaucoup moins de sondes dans le tableau. Cependant, dans les commentaires ci-dessous, Marc Probst rapports qu'il voit la recherche linéaire jusqu'à environ 500 entrées sur son matériel. Cela renforce la nécessité de mesurer lors de la recherche pour les meilleures performances.
Note: Édité Marque ci-après les commentaires ci-dessous sur ses mesures de linéaire et binaire de recherche, de taille raisonnable, N.
Vous pouvez le faire en parallèle.
Si la liste est petite, peut-être qu'il ne sera pas la peine de diviser la recherche, mais si ont à traiter de nombreuses recherches, vous pouvez définitivement les exécuter en parallèle. Qui ne serait pas réduire le temps de latence des opérations, mais permettrait d'améliorer le débit.
Si vous aviez un ordinateur quantique, vous pouvez utiliser L'algorithme de Grover à la recherche de vos données en temps O(N1/2) et le temps à l'aide de O(log N) de l'espace de stockage. Sinon, ta question est assez stupide. Binaire de la recherche ou de l'une de ses variantes (trinary de recherche, par exemple) est vraiment votre meilleur choix. Faire des micro-optimisations sur un linéaire de recherche est stupide quand vous pouvez choisir un de qualité supérieure algorithme.
Je sais que ce sujet est vieux, mais je ne pouvais pas me garder de l'affichage. Mon optimisation pour une sentinelle de la recherche linéaire est:
La recherche de sentinelle grande amélioration est que son itération utilise une seule branche conditionnelle (key) au lieu de deux (index et clés).
dérouler avec fixe indices de tableau.
Vous pourriez éviter d'n vérifie de la même façon déroulement de la boucle ne
boucle vers l'arrière, ce qui pourrait être traduit...
...à ce (la "pourrait être" plus rapide ):
Autre que cela, seulement binaire de recherche peut rendre la recherche plus rapide
loop
n'est pas rapide; la plupart des instructions complexes sont plus lents que plusieurs instructions simples de nos jours. Aussi, woudln ce pas faire un mauvais usage de caches?cela pourrait vecteur de force des instructions (suggéré par Gman):
cela rend également moins d'instructions de branchement.
vous faire aider en veillant à ce tableau d'entrée est aligné à 16 frontière d'octet
une autre chose qui peut aider à la vectorisation (faisant verticale max de comparaison):
Vous pouvez rechercher un élément plus large qu'un int à un moment - plate-forme spécifiquement, cela peut être beaucoup plus ou moins rapidement en fonction de la façon dont il traite le plus grand nombre de données à lire. Par exemple, sur un système 64 bits, la lecture du tableau 2 éléments à la fois et la vérification de la hi/low éléments séparément pourrait courir plus vite en raison de moins d'I/O. Encore, c'est un O(n) la variété de tri n'importe quoi.
Cette réponse est un peu plus obscur que mon autre, donc je vais l'afficher séparément. Il s'appuie sur le fait que C garantit un résultat booléen false=0, true=1. X86 peut produire des booléens sans ramification, de sorte qu'il pourrait être plus rapide, mais je n'ai pas testé. Micro-optimisations comme celui-ci, toujours très dépendant de votre processeur et votre compilateur.
Comme avant, l'appelant est responsable de mettre une sentinelle de la valeur à la fin du tableau pour s'assurer que la boucle s'arrête.
La détermination de la quantité optimale de déroulement de la boucle prend de l'expérimentation. Vous souhaitez trouver le point de diminuer (ou négatif) retourne. Je vais prendre un BUTIN et essayer de 8 cette fois.
Edit: Marquer des points à l'extérieur, cette fonction apporte une dépendance dans chaque ligne sur la ligne précédente, ce qui limite la capacité du pipeline du processeur pour exécuter des opérations en parallèle. Ainsi permet d'essayer une petite modification à la fonction pour supprimer la dépendance. Maintenant, la fonction exige en effet des 8 sentinelle éléments à la fin.
En réalité, la réponse à cette question est de 100% dépendante de la plate-forme de l'écriture du code pour. Par exemple:
Dans l'un des commentaires que vous avez dit que la longueur du tableau est de 64.
Eh bien, si vous doit le faire de façon linéaire, vous pouvez le faire:
Cependant, je doute sérieusement que si c'est plus rapide que ce binaires de recherche: *
*Grâce à Jon Bentley for qui un.
Ajouté: puisque vous avez dit que ce tableau est établi une fois pour un grand nombre de recherches, et vous voulez rapide, vous pouvez allouer de l'espace quelque part et de générer du code machine avec les valeurs câblé en elle. Il pourrait être soit linéaire ou binaire de recherche. Si binaire, le code machine ressemblerait à ce que le compilateur pourrait générer à partir de ce:
Alors que vous venez de copier dans un endroit où vous pouvez l'appeler.
OU vous pouvez imprimer le code ci-dessus, de compiler et de le lier à la volée dans une dll, et de charger la dll.
Eh bien, vous pourriez utiliser des pointeurs...