Optimiser L'Algorithme De Recherche Binaire

Dans un système binaire de recherche, nous avons deux comparaisons pour plus que, et d'autres moins
que, sinon, la valeur moyenne. Comment voulez-vous optimiser de sorte que nous avons besoin de vérifier qu'une seule fois?

bool binSearch(int array[], int key, int left, int right)
{

    mid = left + (right-left)/2;
    if (key < array[mid])
        return binSearch(array, key, left, mid-1);
    else if (key > array[mid])
        return binSearch(array, key, mid+1, right);
    else if (key == array[mid])
        return TRUE; //Found

    return FALSE; //Not Found
}

Est-il une raison de ne pas utiliser brecherche()?

OriginalL'auteur Ganesh M | 2009-03-23

algorithm binary c micro-optimization

17

Je voudrais essayer le brecherche() standard fonction première. Les Chances sont bonnes qu'il peut mieux que votre approche.

la glibc mise en œuvre de brecherche() recherche unoptimized (http://ftp.gnu.org/gnu/glibc)
cela ressemble tout à fait décent pour moi, comme un processus itératif de mise en œuvre de sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/...
comment feriez-vous pour l'optimiser?
un bon livre de décrire le processus d'optimisation cs.bell-labs.com/cm/cs/pearls
désolé, je n'ai pas le livre, et je ne vais pas l'acheter juste pour voir comment il est la mise en œuvre d'une recherche binaire.

OriginalL'auteur quinmars
8

Il n'est pas conseillé d'essayer et d'optimiser dans la façon dont vous décrivez. À partir de la Binaire de l'Algorithme de Recherche d'article sur Wikipédia:

Environ la moitié du temps, le premier test sera vrai de sorte qu'il n'y aura qu'une comparaison de a et b, mais l'autre moitié du temps, il sera faux, et une deuxième comparaison forcé. C'est tellement pénible que certaines versions sont de refonte afin de ne pas faire un deuxième essai à tous donc pas de déterminer l'égalité jusqu'à ce que la durée a été réduite à zéro, et donc qui précède, la possibilité de résiliation anticipée – rappelez-vous que près de la moitié du temps de la recherche vont arriver sur une valeur correspondante une itération courte de la limite.

Il est assez facile de rendre le problème encore pire (comme dans les Trois) à l'aide d'une commande comme
```
if a = b then action3
 else if a > b then action2
  else action1;
```
Plutôt que de les détecter l'égalité début (comme il pourrait sembler), cela forcera les deux comparaisons être effectué pour tous, mais la dernière itération de la recherche.

Certaines langues, comme le Fortran, trois de comparaison qui permet à cette étape avec une comparaison que les branches de trois sections différentes (voir la dixième ligne de la Comparaison à trois exemple). Si votre langue n'est pas en faveur d'une triple test (la plupart des langues ne le font pas), puis deux comparaisons est le meilleur que vous pouvez faire.

Je serait vous conseillons de vérifier les itératif de mise en œuvre à partir du même article, si.

J'ai fait le test d'égalité de la première et il était plus rapide que le test d'égalité dernier (probablement moderne superscalar processeur étrangeté). Vous voudrez peut-être vérifier Knuth ex 6.2.1 23, où il écrit à la manière d'une comparaison est seulement plus rapide pour N> 2**36

OriginalL'auteur Bill the Lizard

J'ai essayé de reconstituer l'optimisation des étapes de l'algorithme recherche binaire. Je commence avec cette version itérative:

int binsearch_1( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  int found=0;
  while( size > 0 ){
    size_t w=size/2;
         if( p[w] <  key  ){ p+=w+1; size-=w+1; }
    else if( p[w] >  key  ){         size =w;   }
    else  /* p[w] == key */{ p+=w; found=1; break; }
  }
  *index=p-array; return found;
}

L'élimination des comparaisons à partir de la boucle:

int binsearch_2( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  while( size > 0 ){
    size_t w=size/2;
    if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else size =w;
  }
  *index=p-array; return p[0]==key;
}

Déroulage de la petite taille de la boucle:

int binsearch_3( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
while( size > 8 ){
size_t w=size/2;
if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else  size =w;
}
if( size==8 ){ if( p[5] <=  key ){ p+=5; size=3; } else size=4; }
if( size==7 ){ if( p[4] <=  key ){ p+=4; size=3; } else size=3; }
if( size==6 ){ if( p[4] <=  key ){ p+=4; size=2; } else size=3; }
if( size==5 ){ if( p[3] <=  key ){ p+=3; size=2; } else size=2; }
if( size==4 ){ if( p[3] <=  key ){ p+=3; size=1; } else size=2; }
if( size==3 ){ if( p[2] <=  key ){ p+=2; size=1; } else size=1; }
if( size==2 ){ if( p[2] <=  key ){ p+=2; size=0; } else size=1; }
if( size==1 ){ if( p[1] <=  key ){ p+=1;         }              }
*index=p-array; return p[0]==key;
}

Réordonnancement des instructions if, le déplacement des cas particuliers [taille==pow(2,N)-1] à la fin:

int binsearch_4( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
while( size > 8 ){
size_t w=size/2;
if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else  size =w;
}
if( size==8 ){ if( p[5] <=  key ){ p+=5; size=3; } else size=4; }
if( size==6 ){ if( p[4] <=  key ){ p+=4; size=2; } else size=3; }
if( size==5 ){ if( p[3] <=  key ){ p+=3; size=2; } else size=2; }
if( size==4 ){ if( p[3] <=  key ){ p+=3; size=1; } else size=2; }
if( size==2 ){ if( p[2] <=  key ){ p+=2; size=0; } else size=1; }
if( size==7 ){ if( p[4] <=  key ){ p+=4; size=3; } else size=3; }
if( size==3 ){ if( p[2] <=  key ){ p+=2; size=1; } else size=1; }
if( size==1 ){ if( p[1] <=  key ){ p+=1;         }              }
*index=p-array; return p[0]==key;
}

Changer si les déclarations d'une instruction switch:

int binsearch_5( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
while( size > 8 ){
size_t w=size/2;
if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else  size =w;
}
if( size==8 ){ if( p[5] <=  key ){ p+=5; size=3; } else size=4; }
if( size==6 ){ if( p[4] <=  key ){ p+=4; size=2; } else size=3; }
if( size==5 ){ if( p[3] <=  key ){ p+=3; size=2; } else size=2; }
if( size==4 ){ if( p[3] <=  key ){ p+=3; size=1; } else size=2; }
if( size==2 ){ if( p[2] <=  key ){ p+=2; size=0; } else size=1; }
switch(size){
case 7: if( p[4] <= key ) p+=4;
case 3: if( p[2] <= key ) p+=2;
case 1: if( p[1] <= key ) p+=1;
}
*index=p-array; return p[0]==key;
}

L'extension de l'instruction switch pour gérer tous les cas particuliers:

int binsearch_6( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
switch( size ){
#define C(n) case ((size_t)1<<n)-1: if( p[1<<(n-1)]<=key ) p+=1<<(n-1); 
#if SIZE_MAX == UINT64_MAX 
C(63) C(62) C(61)
C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51)
C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41)
C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32)
#endif 
C(31)
C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21)
C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11)
C(10) C( 9) C( 8) C( 7) C( 6) C( 5) C( 4) C( 3) C( 2) C( 1)
#undef C 
break;
default:
while( size > 0 ){
size_t w=size/2;
if( p[w] < key ){ p+=w+1; size-=w+1; } else size=w;
}
}
*index=p-array; return p[0]==key;
}

Éliminer le général de gestion des cas dans le code: [ w est le plus petit nombre: w==pow(2,N)-1; taille<=2*(l+1) ]

int binsearch_7( arr_t array[], size_t size, arr_t key, size_t *index ){
if( !array || !size ) return 0;
arr_t *p=array;
size_t w=(size-1)>>1; w|=w>>1; w|=w>>2; w|=w>>4; w|=w>>8; w|=w>>16;
#if SIZE_MAX == UINT64_MAX
w|=w>>32;
#endif
if( p[w]<key ) p+=size-w-1;
switch( w ){
#define C(n) case ((size_t)1<<n)-1: if( p[1<<(n-1)]<=key ) p+=1<<(n-1);
#if SIZE_MAX == UINT64_MAX
C(63) C(62) C(61)
C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51)
C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41)
C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32)
#endif
C(31)
C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21)
C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11)
C(10) C( 9) C( 8) C( 7) C( 6) C( 5) C( 4) C( 3) C( 2) C( 1)
#undef C
}
*index=p-array; return p[0]==key;
}

La dernière étape ce que j'ai fait était la simplification de l'affaire des étiquettes [à partir de: '((size_t)1<<n)-1': 'n'] mais j'ai trouvé que le code modifié a été plus lente sur mon vieux PC que la version précédente.

OriginalL'auteur

4

Si vous souhaitez optimiser votre binaire de l'algorithme de recherche, vous devez remplacer la récursivité à l'itération. Voir des exemples sur wikipédia.

Laissez-moi savoir si vous avez besoin de plus de détails.

OriginalL'auteur mgamer
4

Dans le code que vous avez posté, vous pouvez supprimer le dernier de comparaison. C'est, si key n'est pas moins de array[mid] ou supérieure à array[mid], alors c'est par définition égale. Ainsi, votre code devient:
```
mid = left + (right-left)/2;
if (key < array[mid])
return binSearch(array, key, left, mid-1);
else if (key > array[mid])
return binSearch(array, key, mid+1, right);
else 
return TRUE; //Found
```
Notez également que j'ai supprimé la dernière ligne. Dans votre code, il est impossible pour le return FALSE; jamais être exécutée. Je suppose que vous avez un chèque au début de votre binSearch qui vérifie si left <= right.

En C, il n'y a aucun moyen de faire une comparaison à trois ou à la direction basée sur moins que, égal à, supérieur à, de sorte que vous avez à faire deux comparaisons pour sélectionner parmi trois possibilités.

OriginalL'auteur Jim Mischel
2

Pour les entiers, il n'a pas d'importance, ne le faites pas.

Pour le plus cher des comparaisons utilisez -1, 0, 1 <=, >, comme dans la bibliothèque C de la fonction strcmp ou de Java compareTo().

en fait, je pense qu'il est intéressant pour les nombres entiers comme potentiellement supprime les deux accès à des tableaux. Vous avez le profil pour être sûr, bien sûr.
Si le tableau ont été consulté plus d'une fois que serait vraiment moche compilateur.

OriginalL'auteur starblue

//Optimized Binary Search Implementation
int binsearch(int* data, int size, int val)
{
int result = -1;
int start, mid, end;
start = 0;
end = size - 1;
mid = (start + end) >> 1;
while (start <= end && data[mid] != val)
{
if (data[mid] > val)
end = mid - 1;
else
start = mid + 1;
mid = (start + end) >> 1;
}
if (val == data[mid])
result = mid;
return result;
}

OriginalL'auteur Rajendra Uppal

1

Ganesh M - Si la clé n'existe pas dans le tableau, alors votre fonction sera coincé à l'intérieur d'une boucle sans fin. Il ne peut jamais retourner FALSE.

Quel est le meilleur moyen de trouver le point d'insertion, si la clé n'existe pas?

Conditionnelle "si en cascade" de la comptabilité pour les <, = = et > ne retourne TRUE, ou de continuer à calculer pour toujours.

J'ai besoin de la condition optimale pour déterminer si une touche a été isolé comme n'existant pas.

Je sais que cela va ralentir la recherche, mais je tiens à le ralentir en le moins.

jouer avec log(N)/log(2) semble être une bonne idée, mais quand ce N est pas une puissance de 2, les choses peuvent aller détraque.

Peut-être, je devrais choisir un tableau avec une taille de puissance de 2, et de l'utilisation d'une simple boucle while?

ne vérifiant si le milieu == soit lié augmenter le nombre de comparaisons trop?

+1 pour remarquer que flagrante problème avec l'algorithme

OriginalL'auteur JohnPaul

Ses une question de l'exercice en K&R deuxième édition.

While(low <= high && arr[mid]!=num)
{
if(arr[mid] > num)
{
low = mid+1;
}
else
{
high = mid-1;
}
mid = (low+high)/2;
}
if(arr[mid] == num)
{
printf("found the ugly number");
return mid;
}

OriginalL'auteur Sangeet

bool binSearch(int array[], int key, int len)
{
int mid, low, high;
low = 0;
right = len - 1;
mid = low + (high-low)/2;
while ((low <= high) && (array[mid] != key)) {
if (key < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
mid = low + (high-low)/2;
}
if (array[mid] == key) {
return TRUE;
}
return FALSE;
}

OriginalL'auteur pankaj

using System;
namespace BinarySearchFast
{
public class BinarySearchFast
{
//csharp version, assuming compiler removes the inner branch, there should be almost no branching impact    
//if index not found, returns ~(index of element to insert sorted) at.
public static int BinarySearchFast<T>(T[] array, T value) where T : IComparable<T>
{
if (array == null || array.Length == 0 || value == null)
{
return -1;
}
int start;
int mid;
int end;
int cmp = -1;
start = 0;
end = array.Length - 1;
mid = (start + end) / 2;
while (start <= end && (cmp = array[mid].CompareTo(value)) != 0)
{
//I *think* any good compiler will optimize this to avoid the branch by using a lerp based on cmp > 0 for end and start
//something like:
//end = lerp(end, mid - 1, cmp > 0);
//start = lerp(mid + 1, start, cmp > 0);
//but if not, the lerp could be inserted instead for C/C++, C# does not allow easy conversion of bool to int outside of System.Convert or an if statement.
if (cmp > 0)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
mid = (start + end) >> 1;
}
//could also replace with return lerp(~(++mid), mid, (cmp == 0));
return (cmp == 0 ? mid : ~(++mid));
}
}
}

Vous pourriez faire end = cmp>0 ? mid-1 : end pour le faire sans branches. Ce n'est pas toujours le meilleur, cependant, si les données sont froid dans le cache; spéculative de l'exécution peut effectivement déclencher prefetch et d'éviter une dépendance de données de la chaîne de défauts de cache. à Propos de l'dépourvu de branches de recherche binaire a plus, et montre une façon de l'écrire qui ne nécessite qu'un cmov / autres sans branches ALU sélectionner.
Fascinant, merci pour le partage!

OriginalL'auteur jjxtra

-1

BinarySearch = function (array, value)  
{  
var l = 0;  
var r = array.length;  
var mid;  
while (l!=r)  
{  
mid = Math.round( (r+l)/2 )-1;  
if(value > array[mid])  
l=mid+1;  
else  
r=mid;  
}  
if(array[mid]==value)  
return mid;  
else  
{  
if( (mid < (array.length-1)) && (array[mid+1]==value) )  
return mid+1;  
else  
return -1; //Not found  
}  
}

source: http://calcs.appspot.com/docview?id=agVjYWxjc3IPCxIIRG9jdW1lbnQY0w8M

Qu'est-ce que cette langue - regarde à peine comme si C à moi... copie 'n' pâte pas assez bon....
alors que faire si ses pas C ?
aucun de ces grands prblem qui n'est pas C, mais il ne montre pas quelque chose de nouveau?

OriginalL'auteur Hardbug

Vous devez vous connecter pour publier un commentaire.