Quelle est la méthode de recherche la plus rapide pour un tableau trié?
Répondant à une autre question , j'ai écrit le programme ci-dessous pour comparer différentes méthodes de recherche dans un tableau trié. Fondamentalement, j'ai comparé deux implémentations de recherche D'Interpolation et une de recherche binaire. J'ai comparé les performances en comptant les cycles dépensés (avec le même ensemble de données) par les différentes variantes.
Cependant, je suis sûr qu'il existe des moyens d'optimiser ces fonctions pour les rendre encore plus rapides. Est-ce que quelqu'un a des idées sur Comment puis-je rendre cette fonction de recherche plus rapide? Un la solution en C ou c++ est acceptable, mais j'en ai besoin pour traiter un tableau avec 100000 éléments.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <assert.h>
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
return x;
}
int interpolationSearch(int sortedArray[], int toFind, int len) {
// Returns index of toFind in sortedArray, or -1 if not found
int64_t low = 0;
int64_t high = len - 1;
int64_t mid;
int l = sortedArray[low];
int h = sortedArray[high];
while (l <= toFind && h >= toFind) {
mid = low + (int64_t)((int64_t)(high - low)*(int64_t)(toFind - l))/((int64_t)(h-l));
int m = sortedArray[mid];
if (m < toFind) {
l = sortedArray[low = mid + 1];
} else if (m > toFind) {
h = sortedArray[high = mid - 1];
} else {
return mid;
}
}
if (sortedArray[low] == toFind)
return low;
else
return -1; // Not found
}
int interpolationSearch2(int sortedArray[], int toFind, int len) {
// Returns index of toFind in sortedArray, or -1 if not found
int low = 0;
int high = len - 1;
int mid;
int l = sortedArray[low];
int h = sortedArray[high];
while (l <= toFind && h >= toFind) {
mid = low + ((float)(high - low)*(float)(toFind - l))/(1+(float)(h-l));
int m = sortedArray[mid];
if (m < toFind) {
l = sortedArray[low = mid + 1];
} else if (m > toFind) {
h = sortedArray[high = mid - 1];
} else {
return mid;
}
}
if (sortedArray[low] == toFind)
return low;
else
return -1; // Not found
}
int binarySearch(int sortedArray[], int toFind, int len)
{
// Returns index of toFind in sortedArray, or -1 if not found
int low = 0;
int high = len - 1;
int mid;
int l = sortedArray[low];
int h = sortedArray[high];
while (l <= toFind && h >= toFind) {
mid = (low + high)/2;
int m = sortedArray[mid];
if (m < toFind) {
l = sortedArray[low = mid + 1];
} else if (m > toFind) {
h = sortedArray[high = mid - 1];
} else {
return mid;
}
}
if (sortedArray[low] == toFind)
return low;
else
return -1; // Not found
}
int order(const void *p1, const void *p2) { return *(int*)p1-*(int*)p2; }
int main(void) {
int i = 0, j = 0, size = 100000, trials = 10000;
int searched[trials];
srand(-time(0));
for (j=0; j<trials; j++) { searched[j] = rand()%size; }
while (size > 10){
int arr[size];
for (i=0; i<size; i++) { arr[i] = rand()%size; }
qsort(arr,size,sizeof(int),order);
unsigned long long totalcycles_bs = 0;
unsigned long long totalcycles_is_64 = 0;
unsigned long long totalcycles_is_float = 0;
unsigned long long totalcycles_new = 0;
int res_bs, res_is_64, res_is_float, res_new;
for (j=0; j<trials; j++) {
unsigned long long tmp, cycles = rdtsc();
res_bs = binarySearch(arr,searched[j],size);
tmp = rdtsc(); totalcycles_bs += tmp - cycles; cycles = tmp;
res_is_64 = interpolationSearch(arr,searched[j],size);
assert(res_is_64 == res_bs || arr[res_is_64] == searched[j]);
tmp = rdtsc(); totalcycles_is_64 += tmp - cycles; cycles = tmp;
res_is_float = interpolationSearch2(arr,searched[j],size);
assert(res_is_float == res_bs || arr[res_is_float] == searched[j]);
tmp = rdtsc(); totalcycles_is_float += tmp - cycles; cycles = tmp;
}
printf("----------------- size = %10dn", size);
printf("binary search = %10llun", totalcycles_bs);
printf("interpolation uint64_t = %10llun", totalcycles_is_64);
printf("interpolation float = %10llun", totalcycles_is_float);
printf("new = %10llun", totalcycles_new);
printf("n");
size >>= 1;
}
}
8 réponses
Si vous avez un certain contrôle sur la disposition en mémoire des données, vous pouvez regarder les tableaux Judy.
Ou pour mettre une idée plus simple là-bas: une recherche binaire Coupe toujours l'espace de recherche en deux. Un point de coupure optimal peut être trouvé avec l'interpolation (le point de coupure ne doit pas être l'endroit où la clé est attendue, mais le point qui minimise l'attente statistique de l'espace de recherche pour l'étape suivante). Cela réduit le nombre d'étapes, mais... pas toutes les étapes ont à coût égal. Les mémoires hiérarchiques permettent d'exécuter un certain nombre de tests en même temps qu'un seul test, si la localité peut être maintenue. Étant donné que les m premières étapes d'une recherche binaire ne touchent qu'un maximum de 2**m éléments uniques, les stocker ensemble peut produire une bien meilleure réduction de l'espace de recherche par extraction cacheline (pas par comparaison), ce qui est plus performant dans le monde réel.
Les arbres n-ary fonctionnent sur cette base, puis les tableaux Judy en ajoutent quelques-uns moins importants optimisation.
Bottom line: même la" mémoire vive " (RAM) est plus rapide lorsqu'on y accède séquentiellement qu'au hasard. Un algorithme de recherche devrait utiliser ce fait à son avantage.
Benchmarked sur Win32 Core2 Quad Q6600, gcc v4. 3 msys. Compiler avec G++ - O3, rien de fantaisie.
Observation-les assertions, le timing et la surcharge de boucle sont d'environ 40%, donc tous les gains énumérés ci-dessous devraient être divisés par 0,6 pour obtenir l'amélioration réelle des algorithmes testés.
Réponses Simples:
Sur ma machine, remplacer int64_t par int pour "low", "high" et "mid" dans interpolationSearch donne une vitesse de 20% à 40%. C'est la méthode la plus rapide et facile I pu trouver. Cela prend environ 150 cycles par recherche sur ma machine (pour la taille du tableau de 100000). C'est à peu près le même nombre de cycles qu'un manque de cache. Donc, dans les applications réelles, prendre soin de votre cache va probablement être le plus grand facteur.
Remplacer "/2 "de binarySearch par un" > > 1 " donne une vitesse de 4%.
L'utilisation de l'algorithme binary_search de STL, sur un vecteur contenant les mêmes données que "arr", est à peu près à la même vitesse que le BinarySearch codé à la main. Bien que sur la plus petite"taille" S STL est beaucoup plus lent-environ 40%.
J'ai une solution excessivement compliquée, qui nécessite une fonction de tri spécialisée. Le tri est légèrement plus lent qu'un bon quicksort, mais tous mes tests montrent que la fonction de recherche est beaucoup plus rapide qu'une recherche binaire ou par interpolation. Je l'ai appelé une sorte de régression avant de découvrir que le nom était déjà pris, mais je n'ai pas pris la peine de penser à un nouveau nom (idées?).
Il y a trois fichiers à démontrer.
Le tri/Recherche de régression code:
#include <sstream>
#include <math.h>
#include <ctime>
#include "limits.h"
void insertionSort(int array[], int length) {
int key, j;
for(int i = 1; i < length; i++) {
key = array[i];
j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
--j;
}
array[j + 1] = key;
}
}
class RegressionTable {
public:
RegressionTable(int arr[], int s, int lower, int upper, double mult, int divs);
RegressionTable(int arr[], int s);
void sort(void);
int find(int key);
void printTable(void);
void showSize(void);
private:
void createTable(void);
inline unsigned int resolve(int n);
int * array;
int * table;
int * tableSize;
int size;
int lowerBound;
int upperBound;
int divisions;
int divisionSize;
int newSize;
double multiplier;
};
RegressionTable::RegressionTable(int arr[], int s) {
array = arr;
size = s;
multiplier = 1.35;
divisions = sqrt(size);
upperBound = INT_MIN;
lowerBound = INT_MAX;
for (int i = 0; i < size; ++i) {
if (array[i] > upperBound)
upperBound = array[i];
if (array[i] < lowerBound)
lowerBound = array[i];
}
createTable();
}
RegressionTable::RegressionTable(int arr[], int s, int lower, int upper, double mult, int divs) {
array = arr;
size = s;
lowerBound = lower;
upperBound = upper;
multiplier = mult;
divisions = divs;
createTable();
}
void RegressionTable::showSize(void) {
int bytes = sizeof(*this);
bytes = bytes + sizeof(int) * 2 * (divisions + 1);
}
void RegressionTable::createTable(void) {
divisionSize = size / divisions;
newSize = multiplier * double(size);
table = new int[divisions + 1];
tableSize = new int[divisions + 1];
for (int i = 0; i < divisions; ++i) {
table[i] = 0;
tableSize[i] = 0;
}
for (int i = 0; i < size; ++i) {
++table[((array[i] - lowerBound) / divisionSize) + 1];
}
for (int i = 1; i <= divisions; ++i) {
table[i] += table[i - 1];
}
table[0] = 0;
for (int i = 0; i < divisions; ++i) {
tableSize[i] = table[i + 1] - table[i];
}
}
int RegressionTable::find(int key) {
double temp = multiplier;
multiplier = 1;
int minIndex = table[(key - lowerBound) / divisionSize];
int maxIndex = minIndex + tableSize[key / divisionSize];
int guess = resolve(key);
double t;
while (array[guess] != key) {
// uncomment this line if you want to see where it is searching.
//cout << "Regression Guessing " << guess << ", not there." << endl;
if (array[guess] < key) {
minIndex = guess + 1;
}
if (array[guess] > key) {
maxIndex = guess - 1;
}
if (array[minIndex] > key || array[maxIndex] < key) {
return -1;
}
t = ((double)key - array[minIndex]) / ((double)array[maxIndex] - array[minIndex]);
guess = minIndex + t * (maxIndex - minIndex);
}
multiplier = temp;
return guess;
}
inline unsigned int RegressionTable::resolve(int n) {
float temp;
int subDomain = (n - lowerBound) / divisionSize;
temp = n % divisionSize;
temp /= divisionSize;
temp *= tableSize[subDomain];
temp += table[subDomain];
temp *= multiplier;
return (unsigned int)temp;
}
void RegressionTable::sort(void) {
int * out = new int[int(size * multiplier)];
bool * used = new bool[int(size * multiplier)];
int higher, lower;
bool placed;
for (int i = 0; i < size; ++i) {
/* Figure out where to put the darn thing */
higher = resolve(array[i]);
lower = higher - 1;
if (higher > newSize) {
higher = size;
lower = size - 1;
} else if (lower < 0) {
higher = 0;
lower = 0;
}
placed = false;
while (!placed) {
if (higher < size && !used[higher]) {
out[higher] = array[i];
used[higher] = true;
placed = true;
} else if (lower >= 0 && !used[lower]) {
out[lower] = array[i];
used[lower] = true;
placed = true;
}
--lower;
++higher;
}
}
int index = 0;
for (int i = 0; i < size * multiplier; ++i) {
if (used[i]) {
array[index] = out[i];
++index;
}
}
insertionSort(array, size);
}
Et puis il y a les fonctions de recherche régulières:
#include <iostream>
using namespace std;
int binarySearch(int array[], int start, int end, int key) {
// Determine the search point.
int searchPos = (start + end) / 2;
// If we crossed over our bounds or met in the middle, then it is not here.
if (start >= end)
return -1;
// Search the bottom half of the array if the query is smaller.
if (array[searchPos] > key)
return binarySearch (array, start, searchPos - 1, key);
// Search the top half of the array if the query is larger.
if (array[searchPos] < key)
return binarySearch (array, searchPos + 1, end, key);
// If we found it then we are done.
if (array[searchPos] == key)
return searchPos;
}
int binarySearch(int array[], int size, int key) {
return binarySearch(array, 0, size - 1, key);
}
int interpolationSearch(int array[], int size, int key) {
int guess = 0;
double t;
int minIndex = 0;
int maxIndex = size - 1;
while (array[guess] != key) {
t = ((double)key - array[minIndex]) / ((double)array[maxIndex] - array[minIndex]);
guess = minIndex + t * (maxIndex - minIndex);
if (array[guess] < key) {
minIndex = guess + 1;
}
if (array[guess] > key) {
maxIndex = guess - 1;
}
if (array[minIndex] > key || array[maxIndex] < key) {
return -1;
}
}
return guess;
}
Et puis j'ai écrit un simple main pour tester les différentes sortes.
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include "regression.h"
#include "search.h"
using namespace std;
void randomizeArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
array[i] = rand() % size;
}
}
int main(int argc, char * argv[]) {
int size = 100000;
string arg;
if (argc > 1) {
arg = argv[1];
size = atoi(arg.c_str());
}
srand(time(NULL));
int * array;
cout << "Creating Array Of Size " << size << "...\n";
array = new int[size];
randomizeArray(array, size);
cout << "Sorting Array...\n";
RegressionTable t(array, size, 0, size*2.5, 1.5, size);
//RegressionTable t(array, size);
t.sort();
int trials = 10000000;
int start;
cout << "Binary Search...\n";
start = clock();
for (int i = 0; i < trials; ++i) {
binarySearch(array, size, i % size);
}
cout << clock() - start << endl;
cout << "Interpolation Search...\n";
start = clock();
for (int i = 0; i < trials; ++i) {
interpolationSearch(array, size, i % size);
}
cout << clock() - start << endl;
cout << "Regression Search...\n";
start = clock();
for (int i = 0; i < trials; ++i) {
t.find(i % size);
}
cout << clock() - start << endl;
return 0;
}
Essayez-le et dites-moi si c'est plus rapide pour vous. C'est super compliqué, donc c'est vraiment facile de le casser si vous ne savez pas ce que vous faites. Faites attention à le modifier.
J'ai compilé le principal avec g++ sur ubuntu.
À moins que vos données ne soient connues pour avoir des propriétés spéciales, la recherche par interpolation pure risque de prendre du temps linéaire. Si vous vous attendez à ce que l'interpolation aide avec la plupart des données mais que vous ne voulez pas que cela fasse mal dans le cas de données pathologiques, j'utiliserais une moyenne (éventuellement pondérée) de la supposition interpolée et du point médian, assurant une limite logarithmique sur le temps d'exécution.
Une façon d'aborder cela est d'utiliser un compromis espace-temps. Il y a un certain nombre de façons qui pourraient être faites. La manière extrême serait de simplement faire un tableau avec la taille maximale étant la valeur maximale du tableau trié. Initialisez chaque position avec l'index dans sortedArray. Ensuite, la recherche serait simplement O (1).
La version suivante, cependant, pourrait être un peu plus réaliste et peut-être utile dans le monde réel. Il utilise une structure "helper" qui est initialisé lors du premier appel. Il mappe l'espace de recherche à un espace plus petit en divisant par un nombre que j'ai sorti de l'air sans beaucoup de tests. Il stocke l'index de la limite inférieure pour un groupe de valeurs dans sortedArray dans la carte d'aide. La recherche réelle divise le nombre toFind par le diviseur choisi et extrait les limites réduites de sortedArray pour une recherche binaire normale.
Par exemple, si les valeurs triées vont de 1 à 1000 et que le diviseur est 100, alors la recherche tableau peut contenir 10 "sections". Pour rechercher la valeur 250, Il la diviserait par 100 pour donner la position d'index entier 250/100=2. map[2] contiendra l'index sortedArray pour les valeurs 200 et plus. {[6] } aurait la position d'index des valeurs 300 et plus grandes, fournissant ainsi une position de délimitation plus petite pour une recherche binaire normale. Le reste de la fonction est alors une copie exacte de votre binaire fonction de recherche.
L'initialisation de la carte d'assistance pourrait être plus efficace en utilisant un recherche binaire pour remplir les positions plutôt qu'une simple analyse, mais c'est un coût unique, donc je n'ai pas pris la peine de tester cela. Ce mécanisme fonctionne bien pour les numéros de test donnés qui sont répartis uniformément. Comme écrit, il ne serait pas aussi bon si la distribution était même pas. Je pense que cette méthode pourrait également être utilisée avec des valeurs de recherche à virgule flottante. Cependant, l'extrapoler aux clés de recherche génériques pourrait être plus difficile. Par exemple, Je ne sais pas quelle serait la méthode pour les clés de données de caractères. Il aurait besoin d'une sorte de O(1) lookup/hash qui mappé à une position de tableau spécifique pour trouver les limites d'index. Je ne sais pas pour le moment quelle serait cette fonction ou si elle existe.
Je kluged la configuration de la carte d'assistance dans l'implémentation suivante assez rapidement. Ce n'est pas joli et je ne suis pas sûr à 100% que c'est correct dans tous les cas, mais cela montre l'idée. Je l'ai couru avec un test de débogage pour comparer les résultats avec votre fonction BinarySearch existante pour être un peu sûr fonctionne correctement.
Voici des exemples de numéros:
100000 * 10000 : cycles binary search = 10197811
100000 * 10000 : cycles interpolation uint64_t = 9007939
100000 * 10000 : cycles interpolation float = 8386879
100000 * 10000 : cycles binary w/helper = 6462534
Voici L'implémentation rapide et sale:
#define REDUCTION 100 // pulled out of the air
typedef struct {
int init; // have we initialized it?
int numSections;
int *map;
int divisor;
} binhelp;
int binarySearchHelp( binhelp *phelp, int sortedArray[], int toFind, int len)
{
// Returns index of toFind in sortedArray, or -1 if not found
int low;
int high;
int mid;
if ( !phelp->init && len > REDUCTION ) {
int i;
int numSections = len / REDUCTION;
int divisor = (( sortedArray[len-1] - 1 ) / numSections ) + 1;
int threshold;
int arrayPos;
phelp->init = 1;
phelp->divisor = divisor;
phelp->numSections = numSections;
phelp->map = (int*)malloc((numSections+2) * sizeof(int));
phelp->map[0] = 0;
phelp->map[numSections+1] = len-1;
arrayPos = 0;
// Scan through the array and set up the mapping positions. Simple linear
// scan but it is a one-time cost.
for ( i = 1; i <= numSections; i++ ) {
threshold = i * divisor;
while ( arrayPos < len && sortedArray[arrayPos] < threshold )
arrayPos++;
if ( arrayPos < len )
phelp->map[i] = arrayPos;
else
// kludge to take care of aliasing
phelp->map[i] = len - 1;
}
}
if ( phelp->init ) {
int section = toFind / phelp->divisor;
if ( section > phelp->numSections )
// it is bigger than all values
return -1;
low = phelp->map[section];
if ( section == phelp->numSections )
high = len - 1;
else
high = phelp->map[section+1];
} else {
// use normal start points
low = 0;
high = len - 1;
}
// the following is a direct copy of the Kriss' binarySearch
int l = sortedArray[low];
int h = sortedArray[high];
while (l <= toFind && h >= toFind) {
mid = (low + high)/2;
int m = sortedArray[mid];
if (m < toFind) {
l = sortedArray[low = mid + 1];
} else if (m > toFind) {
h = sortedArray[high = mid - 1];
} else {
return mid;
}
}
if (sortedArray[low] == toFind)
return low;
else
return -1; // Not found
}
La structure d'aide doit être initialisée (et la mémoire libérée):
help.init = 0;
unsigned long long totalcycles4 = 0;
... make the calls same as for the other ones but pass the structure ...
binarySearchHelp(&help, arr,searched[j],length);
if ( help.init )
free( help.map );
help.init = 0;
Regardez d'abord les données et si un gros gain peut être obtenu par une méthode spécifique aux données sur une méthode générale.
Pour les grands ensembles de données triés statiques, vous pouvez créer un index supplémentaire pour fournir un pigeon holing partiel, en fonction de la quantité de mémoire que vous êtes prêt à utiliser. par exemple, disons que nous créons un tableau bidimensionnel 256x256 de plages, que nous remplissons avec les positions de début et de fin dans le tableau de recherche d'éléments avec des octets d'ordre Élevé correspondants. Lorsque nous venons de chercher, nous utilisons ensuite les octets d'ordre élevé sur la clé pour trouver la plage / sous-ensemble du tableau que nous devons rechercher. Si nous avions ~ 20 comparaisons sur notre recherche binaire de 100 000 éléments O(log2 (n)), Nous sommes maintenant à ~4 comarisons pour 16 éléments, ou O (log2 (n / 15)). Le coût de la mémoire ici est d'environ 512k
Une autre méthode, encore une fois adaptée aux données qui ne changent pas beaucoup, consiste à diviser les données en tableaux d'éléments couramment recherchés et d'éléments rarement recherchés. Par exemple, si vous laissez votre recherche existante en place en exécutant un grand nombre de cas réels sur une période de test prolongée, et en consignant les détails de l'élément recherché, vous pourriez bien constater que la distribution est très inégale, c'est-à-dire que certaines valeurs sont recherchées beaucoup plus régulièrement que d'autres. Si tel est le cas, divisez votre tableau en un tableau beaucoup plus petit de valeurs couramment recherchées et un tableau restant plus grand, et recherchez d'abord le tableau plus petit. Si les données sont correctes (big if!), vous pouvez souvent obtenir des améliorations largement similaires à la première solution sans le coût de la mémoire.
Il existe de nombreuses autres optimisations spécifiques aux données qui obtiennent de bien meilleurs résultats que d'essayer d'améliorer des solutions générales éprouvées, testées et beaucoup plus largement utilisées.
Poster ma version actuelle avant la fermeture de la question (j'espère que je pourrai ainsi la gérer plus tard). Pour l'instant, c'est pire que toutes les autres versions (si quelqu'un comprend pourquoi mes modifications à la fin de la boucle ont cet effet, les commentaires sont les bienvenus).
int newSearch(int sortedArray[], int toFind, int len)
{
// Returns index of toFind in sortedArray, or -1 if not found
int low = 0;
int high = len - 1;
int mid;
int l = sortedArray[low];
int h = sortedArray[high];
while (l < toFind && h > toFind) {
mid = low + ((float)(high - low)*(float)(toFind - l))/(1+(float)(h-l));
int m = sortedArray[mid];
if (m < toFind) {
l = sortedArray[low = mid + 1];
} else if (m > toFind) {
h = sortedArray[high = mid - 1];
} else {
return mid;
}
}
if (l == toFind)
return low;
else if (h == toFind)
return high;
else
return -1; // Not found
}
L'implémentation de la recherche binaire utilisée pour les comparaisons peut être améliorée. L'idée clé est de "normaliser" la plage initialement afin que la cible soit toujours > un minimum et
int binarySearch(int * &array, int target, int min, int max)
{ // binarySearch
// normalize min and max so that we know the target is > min and < max
if (target <= array[min]) // if min not normalized
{ // target <= array[min]
if (target == array[min]) return min;
return -1;
} // end target <= array[min]
// min is now normalized
if (target >= array[max]) // if max not normalized
{ // target >= array[max]
if (target == array[max]) return max;
return -1;
} // end target >= array[max]
// max is now normalized
while (min + 1 < max)
{ // delta >=2
int tempi = min + ((max - min) >> 1); // point to index approximately in the middle between min and max
int atempi = array[tempi]; // just in case the compiler does not optimize this
if (atempi > target)max = tempi; // if the target is smaller, we can decrease max and it is still normalized
else if (atempi < target)min = tempi; // the target is bigger, so we can increase min and it is still normalized
else return tempi; // if we found the target, return with the index
// Note that it is important that this test for equality is last because it rarely occurs.
} // end delta >=2
return -1; // nothing in between normalized min and max
} // end binarySearch