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.