Discussion :

[Montor]

Bonjour

J'ai déclaré ce nouveau type pour extraire les mots un fichier texte leurs positions le problème c'est le tri
comment je peux les triés

Code :

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

1
2
3
4
5
6
7
8
9
 
  type
  TListDesMots = record
    LeMot : string;
    Sapos : cardinal;
  end;
 
Var
 ListDesMots:array[0..131071]of TListDesMots ;

j'ai cette fonction

Code :

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

1
2
3
 
       SortArray(ListDesMots, 0, SizeOf(ListDesMots[Low(ListDesMots)]),
  0,wcunt-1  , ComparePersons);

mais lorsque il s'agi de 80000 mots elle devient un peu lente et il y a ce message "Stack Overflow..."

[Aka Guymelef]

Bonjour,

Pourquoi ne pas essayer de faire en sorte d'ajouter le mot à sa bonne place dans le tableau ?

Dans la logique on récupère le mot, on détermine l'indice où il devrait être avec une recherche dichotomique puis on insère le mot à l'indice prévu.

[Montor]

Bonjour
Cette recherche dichotomique peut trier les mot si le nombre et inconnu ?

[Aka Guymelef]

Je ne suis pas sûr d'avoir bien compris la question mais la recherche dichotomique est une fonction de recherche pas de tri. Cependant dans mon idée on va utiliser cette recherche pour positionner "just in time" les enregistrement à leur bonne place dans le tableau au moment où l'on veut ajouter un nouvel enregistrement au tableau.

Peut-être que c'est la notion de recherche dichotomique que tu ne visualises pas, c'est en fait une autre méthode de recherche que celle linéaire mais qui nécessite de travailler sur un tableau trié au préalable. Fais une recherche dans google pour plus de détail sur son algorithme.

[Montor]

Merci je vais essayer le B-TREE

[Gilbert Geyer]

Salut,

Pour la recherche dichotomique suggérée par Aka Guymelef tu peux par exemple t'inspirer du code de la function IndexOfSL3(SL : TStringList; const S: string): Integer; qui se trouve ici (dans la 2ième moité du message du 21/07/2007, 15h15 ) : http://www.developpez.net/forums/sho...exofSL3&page=2
... il s'agit du code qu'on a trafficoté pour remplacer la function standard IndexOf pour gains de vitesse.
... mais attention il faudrait la remodeler :
- d'une part pour effectuer la recherche dans ta ListDesMots : array[0..131071]of TListDesMots (relativement simple);
- et d'autre part de sorte qu'elle renvoie l'Index de la bonne position d'un mot qui n'y figure pas encore (faut trouver une astuce)(*) car la fonction en son état actuel renvoie seulement l'index d'un mot qui y figure déjà.

A+

EDIT du 8 mai : (*) : Comme l'idée d'Aka Guymelef consiste, me semble-t-il, à placer chaque nouveau mot à ajouter dans le tableau à l'index correspondant à sa bonne place lors et au fur et à mesure de la création du tableau de sorte que le tableau soit d'entrée de jeu toujours dans l'état trié, les modifications à apporter à IndexOfSL3 consistent :
- en une simplification : suppression de la partie if Not Sorted then ...
- et pour qu'elle renvoie l'Index de la bonne position d'un mot qui n'y figure pas encore il faudrait à première vue ajouter une variable Cprec: Integer qui mémorise la valeur prise lors du tour de boucle précédent par la variable C lors des comparaisons if SL[i] < S then C:=-1 else if SL[i] > S then C:=+1 else C:=0; et de détecter le moment où C change de signe (if C<>Cprec) et qui correspond à +/- 1 unité à la valeur de l'Index de la bonne position recherchée, puis pour savoir si cet index est égal à i, i+1 ou i-1 suffit de faire un test sur une liste d'une dizaine de mots pour effectuer le calibrage.

A+