À 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 dans B, qui sont plus petits que a. Nous nous déplaçons à l'intégralité de la séquence de sortie, suivie par a. Puis nous le répétons: prendre l'élément suivant a de A... 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 de A, faire une recherche binaire dans B, déplacer le début de la séquence de B à la sortie, déplacer a à 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.

InformationsquelleAutor Mark Probst | 2010-04-30