Discussion :

[smarties]

Bonjour,

J'ai besoin de faire de nombreuses recherche dans une liste d'�l�ments uniques (plusieurs millions) de type mpz_t (bigint de la biblioth�que mpir).

Quelles impl�mentations de set performante existe-t-il en C ?

Dois-je m'orienter sur un hashset ou un treeset pour avoir les meilleures performances en recherche ?

Merci d'avance.

[dinobogan]

Tu ne donnes pas assez de d�tails, alors je vais faire des suppositions.
Supposons que tous tes mpz_t tiennent en RAM dans un seul tableau. Supposons que tu puisses y appliquer une relation d'ordre total (je ne connais pas la structure mpz_t). Supposons enfin que l'ensemble des mpz_t ne change pas.
Alors pour une premi�re approche, tu vas trier le tableau. Puis, pour toutes tes recherches, tu feras une recherche dichotomique.
Si tu as 16 millions d'�l�ments, ta recherche dichotomique ne demandera que 24 tests pour trouver l'�l�ment cherch�.
L'avantage de cette approche est que le code est simple et court. Tu vas tr�s vite avoir un chronom�trage sur les temps de recherches et tu pourras revenir ici s'il faut am�liorer les temps de recherches.

[smarties]

Bonjour,

Tous les mpz_t sont en RAM (�a fait en tableau de 2 � 4 Go) et il ne change pas sauf si le programme red�marre.

[smarties]

Bonjour,

J'ai pu chang� les mpz_t par des unsigned long long et j'ai aliment� un tableau de taille fixe (actuellement 26 898 867 �l�ments) avec les nombres tri�s.

J'ai essay� une recherche dichotomique mais je ne trouve pas �a rapide, avez-vous une meilleure alternative ?
Sachant que :

• le nombre d'�l�ments est fixe et aucun �l�ment n'est ajout�/supprim� apr�s initialisation du tableau
• l'ordre n'a pas d'importance

PS : je peux �ventuellement switcher vers du C++
si c'est une librairie externe, elle doit �tre utilisable sur Windows ET Linux

[Bousk]

- pas rapide : C'est a dire ? Tu as quel r�sultat et esp�res quel r�sultat ?
- ordre pas important : Tes �l�ments ne sont pas tri�s ? Comment effectues donc ta recherche alors ?
- changement de langage : C++ a une structure set et unordered_set (hashset) en standard, aucune id�e des performance par contre

Plus rapide que du dichotomique sur structure tri�e euh.. On se rapproche de la science fiction. Tes �l�ments se suivent-ils ? Y'a-t-il aucun trous ? Peux-tu cr�er un index unique dans [1-X] depuis chacun d'eux ? Si oui a une de ces question, un tableau pourrait �tre envisag�, et la recherche devient juste le calcul de l'index et un d�calage de pointeur.

[Matt_Houston]

Une recherche dichotomique sur un tableau de cette taille, c'est cache miss garanti � chaque acc�s. Autrement dit, le processeur va passer deux pour cent de ses cycles � ex�cuter ton code et le reste � attendre les informations.

Pas mieux que Bousk : quel est ton cas d'utilisation ? Qu'esp�res-tu ? Quels sont tes points de comparaison ?

[fenkys]

- ordre pas important : Tes �l�ments ne sont pas tri�s ?

Il n'a pas dit que sa liste n'�tait pas tri�, mais que l'ordre n'�tait pas important. En clair, si on lui propose un ordre qui permet d'am�liorer les performances, il n'aura aucun probl�me � l'adopter.
Enfin, c'est comme �a que je l'ai compris.