Existe-t-il une étude ou une théorie derrière la combinaison de la recherche binaire et de la recherche par interpolation?

Je viens de lire Cet algorithme peut-il encore être considéré comme un algorithme de recherche binaire? et j'ai rappelé qu'il y a quelques années, j'ai écrit un indexeur / recherche de fichiers journaux pour trouver des entrées de journal dans de gros fichiers texte brut par date / heure.

En faisant cela, j'ai décidé d'essayer la recherche par interpolation (je ne savais pas que c'était comme ça, je suis tombé sur l'idée par moi-même). Ensuite, pour une raison quelconque, j'ai continué à l'idée d'alterner les étapes d'interpolation avec les étapes de division binaire: à l'étape 0, j'interpolais pour décider du point de test, puis à l'étape 1, je prenais le milieu exact, etc.

J'ai ensuite testé le système en utilisant la recherche d'interpolation pure, la recherche binaire pure et ma tentative de combinaison. L'approche alternative a été clairement gagnante, à la fois en temps et en nombre de tests requis avant de trouver un ensemble de temps choisis au hasard.

Inspiré par la question liée, je viens de faire une recherche rapide pour "recherche d'interpolation alternée et recherche binaire" et je n'ai rien trouvé. J'ai également essayé la "recherche d'interpolation couverte" comme suggéré dans mon commentaire sur l'une des réponses.

Suis-je tombé sur une chose connue? Y a-t-il une justification théorique pour qu'il soit plus rapide pour certains types de données? Les fichiers journaux étaient généralement volumineux pour l'époque (par exemple, 1 à 2 Go de texte avec peut-être 10 millions de lignes à rechercher), et la répartition des dates / heures en eux était complexe avec de fortes périodes d'activité, des heures de pointe générales et des périodes de silence. Mes tests de référence échantillonnés à partir d'une distribution uniforme des temps cibles à trouver.

algorithms search-algorithms binary-search Neil Slater
la source

Réponses:

Suis-je tombé sur une chose connue?

$O(log\ log\ n)$ $O(log\ n)$

La recherche introspective est votre méthode (itération entre une recherche d'interpolation et une recherche binaire). Je n'ai pas plus de détails.
Recherche binaire par interpolation (IBS) par N. Santoro, JB Sidney (1985).

L'idée générale est que la recherche par interpolation n'est utile que lorsque le tableau recherché est supérieur à un seuil donné. Lorsque le segment de recherche considéré est plus petit qu'un seuil défini par l'utilisateur, la recherche binaire est appliquée sans condition. Inversement, au-delà de ce seuil, une étape de recherche d'interpolation est appliquée, suivie éventuellement d'une étape de recherche binaire.

Cela a de nombreux points communs avec votre approche.
Recherche adaptative (AS) par Biagio Bonasera, Emilio Ferrara, Giacomo Fiumara, Francesco Pagano, Alessandro Provetti

En utilisant les mots des auteurs:

[Interpolation-binary search] a conçu une solution similaire qui combine (mais ne mélange pas) l'interpolation et la recherche binaire. Bien que la complexité asymptotique soit la même, il existe quelques différences marquées.

[COUPER]

Par conséquent, il est possible de montrer que pour n'importe quelle entrée AS ne prendra pas plus d'opérations élémentaires qu'IBS.

L'algorithme peut passer jusqu'à deux fois le nombre d'opérations que la recherche d'interpolation "simple" pour trouver soigneusement la meilleure réduction de moitié du segment de recherche, ce qui signifie à son tour que moins d'itérations seront nécessaires pour terminer (mais vous avez un surcoût encore plus important) .

manlio
la source

L'entrelacement de deux algorithmes pour tirer le meilleur parti des deux mondes est une technique connue, bien qu'il soit généralement indiqué de les exécuter en "parallèle" et de renvoyer une réponse dès que l'un ou l'autre se termine.

Bien que théoriquement plus rapide, la recherche par interpolation présente deux inconvénients par rapport à la recherche binaire:

Il a des performances pires (linéaires) dans le pire des cas
La surcharge de calcul du point médian est assez grande; une itération de recherche binaire est des centaines de fois plus rapide qu'une recherche d'interpolation

Je m'attendrais à ce qu'une approche où vous effectuez une recherche d'interpolation alors que la plage est grande et passez à la recherche binaire lorsque la plage devient petite est la plus efficace. Ce serait bien si vous pouviez essayer cette expérience.

$\log n$ $\log \log n$ $\log n$ $\log \log n$

Je pense que vos résultats peuvent s'expliquer par deux phénomènes:

La combinaison avec la recherche binaire vous permet d'éviter le pire des cas
L'effet positif du passage à la recherche binaire sur un petit ensemble de données

Tom van der Zanden
la source

Vous avez écrit: "une itération de recherche binaire est des centaines de fois plus rapide qu'une recherche d'interpolation". Veuillez noter que dans le cas de OP, la différence entre le calcul du point médian dans ces deux méthodes est éclipsée par le temps d'E / S nécessaire pour récupérer la valeur du point médian.

liori

@liori: Les premières itérations de recherches binaires répétées sur les mêmes données pourraient être plus compatibles avec le cache, car les mêmes éléments sont utilisés. On peut donc s'attendre à ce que les trimestres et peut-être les huitièmes restent chauds dans le cache. Commencer par binaire et passer à interpolé après trois itérations peut avoir du sens si les plages sont suffisamment grandes. (Ou si vous pouvez effectuer des E / S asynchrones et utiliser le résultat qui arrive en premier).

Peter Cordes

De plus, même pour une recherche en mémoire, un échec de cache (plus de 200 cycles de latence) a deux fois la latence même d'une division entière de 64 bits (32-96 cycles), sur Intel Haswell par exemple . La division entière 32 bits est beaucoup plus rapide (22-29 cycles). La bande passante de la mémoire principale est une ressource partagée pour tous les cœurs, mais la division entière utilise uniquement des ressources dupliquées sur chaque cœur.

Peter Cordes

Cependant, la latence de la mémoire est bien pire que la bande passante de la mémoire, car même plusieurs accès dispersés vont plus vite s'ils sont en vol à la fois. C'est une victoire de pré-extraire (avec des prefetcht0instructions ) les deux possibilités pour l'itération NEXT avant de charger le point médian actuel, pour une recherche en mémoire sur du matériel x86 moderne. Vous ne pouvez pas faire cela si vous ne pouvez pas prévoir à l'avance les prochaines adresses de récupération. Les détails pratiques de mise en œuvre peuvent donc être importants, en dehors des considérations théoriques .

Peter Cordes

@liori: Les E / S par point médian ont certainement été le principal facteur lors de l'indexation d'un fichier journal, car il était lu à la demande afin de trouver des enregistrements. Il y avait probablement plus de deux ordres de grandeur entre le calcul du décalage dans le fichier et la lecture d'un bloc - par conséquent, le nombre de points médians calculés serait le facteur décisif. Je pense que si je réplique maintenant sans fichier journal à indexer - quelque chose que j'essaierai de publier ici - qu'il pourrait ne pas y avoir de différence de vitesse mesurable, mais il pourrait y avoir une différence mesurable de "nombre de points médians nécessaires".

Neil Slater