Discussion :

[gregb34]

Bonjour,

Je possède une liste chainée comportant des enregistrements. Il y a plus de 100 000 enregistrements.

Je souhaiterais sortir une liste avec les enregistrement qui revienne le plus souvent, que me conseillez vous ?

On crée une 2eme liste.
Tant que la liste principale n'est pas vide alors
- Si l'enregistrement en cours n'est pas dans la 2eme liste, on l'ajoute.
- Sinon on incremente le compteur de la cellule concernée dans la 2eme liste.
Fin Tant que

Suivant comment j'organise mes traitements, je pensais detruire au fur et a mesure la liste chainée principale avec d'economiser de la mémoire.

Que pensez vous. Il y a t'il une autre solution ?

MERCI a vous

[Graffito]

Bonjour,

La technique à utiliser dépend du rapport entre le nombre N d'enregistrement à retenir et du nombre total T d'enregistrements au départ.

Si N/T est faible, on peut faire N recherche de maximum en éliminant à chaque fois de la recherche les max obtenus précédement.

Sinon, il commencer par faire un premier tri en fonction des valeurs de la liste chainée.
Supposons par exemple la liste suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
GAMMA
ALPHA
ALPHA
BETA
ALPHA
GAMMA

Après tri:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
ALPHA
ALPHA
ALPHA
BETA
GAMMA
GAMMA

Puis totaliser le nombre d'occurence pour chaque valeur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
ALPHA (3)
BETA  (1)
GAMMA (2)

GAMMAPuis faire un tri final, fonction décroissante du compte :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
3 - ALPHA
2 - GAMMA
1 - BETA

et garder les N premieres valeurs.

[gregb34]

Il y aura un nombre "infini" d'enregistrement, je ne peux pas controler. Je fais mes tests avec plus de 100 000 enregistrement ce qui est pas mal deja meme s'il est possible qu'il y en ai plus.

En faite ma liste chainée principale comporte des enregistrements de ce type

- ip : String[15];
- date_heure : TDateTime;
- page : String[100];

C'est dans le cadre d'un parseur de fichier LOG d'apache.

Et je souhaite recuperer les 10 pages les plus consuler. Alors certes, il y a pas autant d'enregistrement dans le fichier LOG que de page que comporte le site... mais il peut y en avoir beaucoup...

Donc le rapport que tu proposes est faible mais j'ai bien peur que faire un MAX a chaque fois, soit assez long...

Ta 2eme idée me plait. Il faudrait alors que je garde tous le temps ma 2eme liste triée selon les pages. L'ajout des pages pas encore referenciés et la mise a jour des compteurs se ferait plus facilement si j'ai bien compris ?

MERCI

C'est ca ?

[Graffito]

Bonjour,

La liste initiale étant triée suivant les pages, il suffit, à chaque fois qu'on fait une insertion de page, de compter le nombre d'occurence de cette page et de mettre à jour la liste des 10 meilleures si nécessaire.

Pour optimiser, on peut actualiser une info "count" en plus de ip, time et page sur la première ou la dernière occurence de la page.

Simple remarque : pour cette application, j'aurais créé à la base un index par nom de page et utilisé une liste chainée juste pour les date-time de consultation.
Pour le choix du type d'index, y'a plein de solution.
Mais j'aime bien celle dans laquelle on fait une arborescence de mots avec un noeud par lettre du mot.

[gregb34]

La liste chainée principale de 100 000 enregistrement n'est pas triée.

[Graffito]

Bonjour,

Si la liste des 100 000 initiaux n'est pas triée, la première méthode qui consiste à trouver succesivement les 10 maximum donnera la meilleure performance (Pour moi, y'a pas photo).

Si il y a de réels problèmes de performance, une liste indexée serait vraiment une meilleure solution tant à la construction que pour l'exploitation (sutrtout, si on désire vérifier si une page est déjà dans la liste).

[rvzip64]

Je ne sais pas quel est le but exatc de ton application. Mes peut etre que une base de données pourrait te servir...

[gregb34]

Le but :

Recuperer les 10 pages les plus demandées issues d'un log d'apache.

[Graffito]

Bonjour,

Aucune autre fonctionalité sur la liste des URL ?


Si c'est le cas, j'opererais de la façon suivante :
- utiliser une fonction de hashcode (en pratique un checksum 16bits) pour associer un entier de 16 bits à chaque URL,
- créer un tableau de 2**16 valeurs pour "indexer" les URL via le hashcode (chaque élément du tableau pointant sur une liste de noms d'URL avec leur compte),
- parcourir le log et pour chaque URL rencontrée : [list]. calculer le hashcode,

• . vérifier si l'URL est dans la liste correspondant à ce hashcode,
  . si ce n'est pas le cas l'ajouter,
  . incrémenter le nombre d'occurence pour cet URL
  . suivant la valeur du compte

- initialiser la liste des 10 + utilisés
- parcourir la liste des hash codes pour traiter chaque URL différente afin de mettre à jour si nécessaire la liste des 10 URL les plus utilisées:

• . comparer le compte de l'URL traitée à celui du n°10,
  . si plus petit ou égalité, rien à faire
  . si plus grand, insérer la nouvelle URL dans la liste (supprimer l'ancien n°10)