Tris binary search

Version imprimable

Tris binary search

Hi
Y’a-t-il un moyen ou une autre approche algorithmique implémenté en C qui serait utilisé pour optimiser ou accélérer un binary search existant (exemple le code ci-dessous à optimiser)? Avez-vous des pistes, propositions ou des solutions ?
Merci d'avance.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
#include <stdio.h>
#include <stdlib.h>
 
#define SIZE	1024
 
int binary_search( int tab_valeur[], int l, int r, int x )
{
	while( l <= r )
	{
		int mem = l + (r-l) / 2;
		if( tab_valeur[mem] == x )
		{
			return mem;
		}
		else if( tab_valeur[mem] < x )
		{
			l = mem + 1;
		}
		else
		{
			r = mem -1;
		}
	}
	return -1;
}
 
int main( int argc, char *argv[] ){
 
	int i;
	int tab_valeurs[SIZE];
 
	for( i = 0; i < SIZE; i++ )
	{
		tab_valeurs[i] = i;
	}
 
	for( i = 0; i < SIZE; i++ )
	{
			printf("%d\n", tab_valeurs[i]);
	}
 
	int resultat = binary_search(tab_valeurs, 0, SIZE - 1, 666 );
	if( resultat == -1 ){
		printf("Aucune valeur trouvée\n");
	}
	else
	{
		printf("Valeur trouver à l'index %d = %d\n", resultat, tab_valeurs[resultat] );
	}
 
	return 0;
}

Mis à part utiliser bsearch* qui pourrait être plus rapide, pas vraiment. Dans une collection ordonnée à accès direct, il n'y a pas meilleure complexité algorithmique qu'une recherche dichotomique, et on ne peut pas l'implémenter de manière radicalement plus performante que tel que tu l'as fait tout en restant portable.

Si ce n'est pas suffisant pour ton cas d'utilisation c'est probablement, au choix :

qu'il existe des défauts dans la conception analytique de ton programme ;
que la structure de données (tableau trié) n'est pas adaptée à l'usage qui en est fait. Il existe un seuil de quantité de données où une table de hachage devient pratiquement toujours le meilleur choix, par exemple.

Peux-tu nous en dire plus à propos du problème sous-jacent ?

Soit dit en passant il s'avère souvent nécessaire de récupérer le rang de l'élément même si aucun équivalent n'est présent dans la collection, afin de pouvoir l'y insérer. Et ce de manière stable : en maintenant l'ordre des éléments équivalents.

Voici une fonction que j'emploie à cet usage (plus l'insertion de l'élément est ancienne, plus son rang est élevé) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 int find_rank(size_t *rank, const void *key, const void *buf, size_t count, size_t size, int (*comp)(const void *, const void *)) { size_t start = 0, end = count; while (start < end) { const size_t mid = start + (end - start) / 2; const int order = comp((const unsigned char *)buf + mid * size, key); if (order < 0) start = mid + 1; else if (order > 0) end = mid; else { *rank = mid; return 1; } } *rank = start; return 0; }
On obtient ainsi deux informations distinctes : la confirmation de la présence ou de l'absence d'un élément équivalent dans la collection et le rang que l'élément recherché devrait occuper afin de maintenir la cohérence de la structure de données.

(* Certes la norme n'impose pas de contrainte sur la complexité de bsearch mais je ne vois pas comment elle pourrait être autre chose que logarithmique, sur n'importe quoi d'autre qu'une obscure et très limitée plateforme embarquée.)

19/09/2018, 10h19
Médinoc
Citation:

On obtient ainsi deux informations distinctes : la confirmation de la présence ou de l'absence d'un élément équivalent dans la collection et le rang que l'élément recherché devrait occuper afin de maintenir la cohérence de la structure de données.

Merci pour cette fonction, ça devient rapidement indispensable en effet.

.Net fait la même chose, mais retourne ces deux informations dans un seul résultat (dont le type en C devrait probablement être ptrdiff_t vu que ssize_t n'est pas standard):
- Non-négatif, strictement inférieur à count (donc un index valide) si trouvé
- -index-1 (ce qui en complément à 2, correspond aussi à ~index) si non-trouvé (donc, -1 si la valeur recherchée est inférieure au premier élément, -count-1 si elle est supérieure au dernier))
19/09/2018, 21h43
Didier.va

Merci pour ton retour, mais il n’y a pas de problème sous-jacent. Il est juste question d’optimisation de la fonction actuelle pour la rendre "fast" et bien évidemment portable (si possible) par la même occasion. Ton exemple pourrait répondre à mes attentes, mais malheureusement, ce n’est pas ce que je recherche, quoiqu'il me semble qu’il existe dejà une fonction qui réalise la même chose.
20/09/2018, 09h23
Matt_Houston
Si l'on est à la recherche de pistes d'optimisation, c'est bien qu'il y a un problème : le traitement accapare trop de cycles processeur et/ou trop de mémoire en regard de l'objectif que l'on s'est fixé, pour un jeu de données identifié. Soit quelque chose te fait dire que la machine passe trop de temps à exécuter cette fonction, d'où le sens de ma réponse précédente ; soit non et dans ce cas il n'y a rien à dire et rien à faire.

Si tu constates effectivement un étranglement à cet endroit après avoir profilé le programme, alors - et seulement alors - on peut émettre et tester des hypothèses. Le comportement serait-il dû à :
1. la quantité d'opération effectuées ?
  - Une complexité excessive ? Probablement pas, il est difficile de faire plus simple.
  - Un nombre d'appels trop important ? -> Y'a-t-il une erreur d'implémentation dans le code appelant ?
    
    Oui, il faut la corriger.
    Non, voir point numéro 3.
2. des cache misses ? Plus probable, d'autant que la recherche dichotomique manifeste par essence une piètre localité de référence puisque - à moins d'utiliser un heuristique initial particulier - on est forcé de récupérer les extrémités de toute une moitié du buffer au minimum. Voir point numéro 3.
3. une organisation des données inadaptée à leur traitement ? Si tu fais peu d'insertion, très peu de suppression et beaucoup de lookup alors tu aurais peut-être intérêt à comparer la performance de ta structure avec celle d'une table de hachage, par exemple.

L'optimisation qu’on peut faire et surtout de tester if(tab_valeur[mem] < x ) en premier , après mettre -O3 , ensuite j'ai rajouter quelque truc au cas ou on a pas confiance au compilo ! :aie:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 int binary_search( int *tab_valeur, int l, int r, int x ) { while( l <= r ) { register int mem = l + ((r-l) >> 1); register int valeur = tab_valeur[mem]; if( valeur < x ) { l = mem + 1; } else { if( valeur == x ) return mem; r = mem -1; } } return -1; }
Je note que sans code concret de benchmark , il est difficile a évaluer ;)

Bonsoir,
Si les solutions proposées ne sont peut-être pas envisageables pour vous, il y a cependant une possibilité d’obtenir une légère optimisation, mais pas forcément au prix d’une application forcement portable. Il vous est possible à travers l’instruction __buildtin_prefetch de pouvoir précharger les informations en prévision d’une utilisation future. En d’autres termes, rendre les informations disponibles le plus tôt possible pour qu’elle soit disponible. __buildtin_prefetch va donc de manière asynchrone précharger les données associées à l’adresse que vous auriez préalablement fournie, exemple (sous Gcc et Clang) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 int binary_search_opti(const int dt_search, size_t size, int *ptr ){ size_t dt = 0; size_t dt_srch = 0; for( dt = 0, dt_srch = 0, size -=1; dt_srch <= size; ){ dt = ((dt_srch + size)/2); __buildtin_prefetch(&ptr[(dt + 1 + size)/2],0, 1); __buildtin_prefetch(&ptr[(dt_srch + dt -1)/2],0,1); if( dt_search > (*(ptr+dt)) ) dt_srch = (dt + 1); else if( dt_search == (*(ptr+dt))) return (dt); else if( dt_search < (*(ptr+dt))) size = dt - 1; } return (-1); }
Ceci dit, si vous êtes sous un environement windows, il faudra alors utiliser pour visual l'instruction _mm_prefetch.
à bientôt.