Optimiser la recherche d’une aiguille dans une botte de foin

Problème

Vous devez rechercher une donnée dans un jeu de données et souhaitez l’optimiser afin d’obtenir le résultat au plus vite.

Solution

Lorsque les données ne se trouvent pas dans une structure de données de glib, vous pouvez soit parcourir la structure de données jusqu’à trouver l’aiguille, ou pré-trier la structure de données. Lorsque les données sont triées, effectuez une recherche dichotomique.

Avec une structure de données de glib, utilisez la fonction adéquate :

Fonctions de recherche d’aiguilles dans une botte de foin des structures de données de glib

Structure de données

Fonction

GArray

g_array_sort(), puis recherche dichotomique

GPtrArray

g_ptr_array_sort(), puis recherche dichotomique

GTree

g_tree_lookup()

GHashTable

g_hash_table_lookup()

Discussion

Certaines structures de données sont optimisées pour la recherche d’aiguilles dans une botte de foin. C’est le cas des tables de hachage et des arbres binaires balancés. Lorsque la recherche d’une donnée est souvent réalisée, placez-la dans une telle structure, en choisissant pour clé les données utilisées dans le critère de recherche.

Lorsque la recherche n’est pas primordiale, un simple parcours de la structure de données peut suffire. Cependant, dans certains cas, le coût du tri peut être...

Pour consulter la suite, découvrez le livre suivant :
couv_EI3CACT.png
60-signet.svg
En version papier
20-ecran_lettre.svg
En version numérique
41-logo_abonnement.svg
En illimité avec l'abonnement ENI
130-boutique.svg
Sur la boutique officielle ENI
Précédent
Choisir une structure pour un tableau dont l'index est un entier
Suivant
Trier une liste selon un critère donné