Bonjour,

Lors d'une recherche binaire (dichotomique), par exemple dans un vecteur d'1 million d'éléments (~=2^20), il y a jusqu'à 20 itérations. La probabilité pour que l'élément à trouver le soit dans les 10 premières itérations est de 0,001 (un sur mille, ~1000=2^10). Autant dire que ces 10 premières itérations sont (presque) toujours réalisées.

La proposition d'optimization consiste à créer un tableau ne contenant que le sous-ensemble des éléments nécessaires à ces 10 premières itérations. Le but est que les infos de ce tableau, pour lesquelles l'accès est très fréquent, soient regroupées afin qu'elles tiennent dans un block du cache data de niveau 1 du processeur. Qu'en pensez-vous, y aurait-il un gain de performance ?

On peut déplacer le problème en plaçant le tableau sur disque et en laissant le millième du tableau sur lequel l'accès est le plus fréquent en mémoire vive. Intuitivement le gain me parait évident: les dix premières itérations se font en mémoire, puis les 10 suivantes aussi après une seule lecture sur disque d'un block d'un millième de la taille du tableau complet.

D'une manière plus générale, de tout tableau, en fonction du nombre et de la taille de ses éléments, on pourrait extraire récursivement le sous-tableau des éléments fréquemment accédés lors d'une recherche binaire.
Par exemple, sur un tableau d'un milliard d'éléments, on extrait les mille éléments susceptibles d'être atteint par les 10 premères itérations. Chacun de ces mille éléments sont à la tête d'un tableau d'un million d'éléments duquel on peut à nouveau extraire mille éléments. Lors d'un recherche binaire, l'élément à trouver le serait en ne lisant, au plus, que 3 blocks de mille éléments (sur 1 milliard).

Merci.