Insertion rapide dans une liste chainée

Bonjour,

Pour mon stage je dois réaliser un code utilisant une liste chainée. Je met en œuvre et j'utilise cette liste sans problème.

Le seul inconvénient est que lorsque j’insère un élément (identifié par un ID), je dois le placer correctement dans la liste.

La liste globale représente environs 30 millions d'éléments (oui c'est gros mais c'est comme ça ...) et les éléments sont insérés les un après les autres quand ils arrivent (je lis un fichier txt).

Du coup si j’insère un élément en faisant une comparaison bête et méchante des éléments un à un en parcourant la liste cela est très très très long évidement ...

Je viens donc ici pour avoir votre avis sur comment optimiser l'insertion d'un nouvel élément dans cette liste chainée mais surtout si si vous avez du code à partager je suis preneur ...

Cordialement,

PlayBoy31

Bonjour

Citation:

---

je dois le placer correctement dans la liste

---

correctement, oui, certes, mais tu entends quoi par là ? Les éléments de ton fichier texte sont "en vrac" (dans un ordre quelconque) et tu construis ta liste en la maintenant ordonnée (relation d'ordre sur les ID des éléments) ? C'est le plus probable et je pars là dessus mais ce serait bien que tu confirmes (ou pas).

Déjà, il existe des gestionnaires de listes qui proposent des "insertions triées" d"éléments comme, par exemple, dans GLib, avec les GList et la fonction g-list-insert-sorted. Après, je ne sais pas ce qu'elle vaut niveau performances et si ça peut résoudre ton problème.

Sinon, si tu n'as pas le choix des listes (des types) à utiliser, il faut que tu réduises le nombre de comparaisons à faire à chaque insertion d'un nouvel élément.

Utilise plusieurs listes : un tableau ordonné de listes ordonnées ou même une liste ordonnée de listes ordonnées). A chaque insertion, tu détermines d'abord dans quelle liste tu vas insérer ton nouvel élément (tu parcours ton taleau (ou ta liste) de listes), ensuite tu appliques ce que tu fais actuellement mais sur une liste avec moins d'éléments.

Après le choix entre le tableau ou la liste de listes dépend beaucoup de ton contexte et si tu as une petite idée de la plage des ID présents dans ton fichier initial : est-ce que tu peux prévoir, initialement, des paquets de tailles à peu près homogènes ou pas.

Tu peux aussi envisager d'avoir un découpage à plusieurs niveaux : 30 millions = 1 x 30 000 000 (ce que tu fais) = 1 000 x 30 000 (2 niveaux) = 100 x 100 x 3000 (3 niveaux) = etc...

Une fois ton fichier complétement traité, tu concatènes les listes d'éléments pour obtenir LA liste résultat (la concaténation des listes, ce n'est pas bien méchant : tout le boulot se fait aux extrémités et dépend du nombre de listes, pas des éléments - pour les GList, c'est proposé)

Pas besoin de faire plusieurs listes, une seule suffit mais avec plusieurs pointeurs.

Ainsi plus besoin de concaténer les petites listes pour obtenir une liste final.

Tu peux aussi regarder le premier caractère et en fonction choisir le pointeur approprié.
Par contre il ne faudra pas pointeur sur l'élément de début de sous-liste souhaité mais sur celui d'avant pour les insertions.

Exemple : sous-liste a contient les mot commençant par a
sous-liste aa ceux commençant par aa
sous-liste ab ...
etc...

Citation:

---

Envoyé par Neckara

Pas besoin de faire plusieurs listes, une seule suffit mais avec plusieurs pointeurs.

---

Oui, tout à fait, tu as parfaitement raison.

A la lecture (peut-être trop rapide), j'avais compris que le "type" liste lui était fourni, avec les fonctions "qui vont bien" mais qu'il ne "maitrisait" pas le source et/ou l'implémentation. Et dans ce cas, des pointeurs pour pointer sur quoi ?

En passant par des sous-listes, ça permettait de rester simple utilisateur de la lib, sans avoir à connaître/utiliser l'implémentation. Tout dépend du contexte qu'il a peu détaillé.

Sinon, attention aux fameux ID : tu pars sur des caractères. Les entrées sont dans un fichier texte, certes. Mais les ID sont peut être autre chose que des chaines. Faudrait qu'on en sache un peu plus.

Pour choisir le pointeur de sous-liste, je pense avoir une méthode très rapide avec des tableau de pointeurs pour le 3ème octet.
Un tableau de pointeur de pointeur pour le 2ème et un tableau de pointeur de pointeur de pointeur pour le premier ce qui donne :

Code:

---

1 2 3

pointeur = tableau[*((char *)&identifiant+taille)][*((char *)&identifiant+taille - 1)][*((char *)&identifiant+taille - 2)];

---

Si l'identifiant est un char * , on enlève le '&'

Tout cela revient à faire une table de hashage contenant des pointeurs vers des éléments de la liste. La question en suspend est de bien choisir la fonction de hashage selon le critère de placement (la nature de ID) dans la liste.

Bonsoir et merci pour vos réponses!

Tout d'abord point que je n'ai pas mentionné désolé, le code doit être portable sous linux et windows, du coup c'est dommage pour les Glist ...

En fait, les ID représentent une donnée temps en secondes. Les données ne sont pas dans l'ordre dans le fichier txt et je parcours le fichier pour récupérer la donnée temps et d'autres champs que je modifie correspondant à cette donnée temps avant de l'insérer dans la liste.

j'avoue être un peu perdu avec les solutions évoqué comme pointeur de sous liste et table de hashage ...

par exemple :

si un elément de ta liste est :

typedef struct ELT ...

tu peux très bien stocker au fur et à mesure l'adresse de l'élement démarrant une lettre de l'alphabet :

Code:

---

1 2 3 4 5 6

struct ELT *list_elt, elt, *tab[26] ;   elt = ajoute_elt ( &list_elt); if ( elt->champ[0] == 'a' ) tab[0] = elt ; ...

---

et ensuite tu ne parcours que tab (donc 26) pour trouver entre quel et quel élément tu dois hercher à insérer..

Tu peux le faire aussi en temps :

Code:

---

1 2	if ( elt->heure == (lastheure+1) ) tab[lastheure+1] = elt ;

---

etc etc.. suivant ton meilleur critère..