[TStringList] Optimisation du IndexOf ?

Version imprimable

06/07/2007, 03h53
Bruno13

[TStringList] Optimisation du IndexOf ?

Bonjour à tous,

Je cherche un moyen d'aller plus vite dans la recherche d'une chaine dans une TStringList ?

Possible ou pas ?

Amicalement,
Bruno
06/07/2007, 08h28
Rayek

Ta liste est triée ?

Si oui -> Voir le forum algorythme pour trouver un algorythme de recherche, je sais que la recherche dycotomique (pas sur de l'écriture) est assez rapide.

Si non -> Tu ne feras surement pas mieux, mais rien ne t'empeche d'aller sur le forum algo ^^
06/07/2007, 10h05
Clorish

Dans le cas de liste non triees, on peut deja creer une serie de tableaux contenant les Index des chaines de la StringList, regrouppés par taille de la chaine.

Lors de l'ajout d'une chaine dans la StringList, on recupere son Index et on l'ajoute dans la liste des chaines de Length(s) caracteres soit List[Length(s)]

Apres il suffit de parcourir list[i] pour recuperer les index (list[i][j]) et donc comparer uniquement les chaines qui ont la meme taille.

On peut aussi se baser sur un code unique (md5, crc32) qui lui sera dans une liste triée, dont la recherche se fera par dichotomie ou tout autre alogos de recherche sur tableaux triés.
[Edit] : Autant trier directement le tableau de base :(

Quoi qu'il en soit, toute solution necessitera je pense au moins une initialisation : Tri, generation de matrices/tableaux de recherche, etc....
06/07/2007, 10h47
TicTacToe

Bonjour,

Tu peux jeter également un coup d'oeil à THashedStringList qui est fait pour une recherche plus rapide sur des listes triées.

Oh ! Des shadocks ! :mrgreen:

Juste pour information : une TStringList triée utilise déjà la recherche dichotomique.

Extrait de la VCL :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function TStringList.Find(const S: string; var Index: Integer): Boolean;
var
  L, H, I, C: Integer;
begin
  Result := False;
  L := 0;
  H := FCount - 1;
  while L <= H do
  begin
    I := (L + H) shr 1;
    C := CompareStrings(FList^[I].FString, S);
    if C < 0 then L := I + 1 else
    begin
      H := I - 1;
      if C = 0 then
      begin
        Result := True;
        if Duplicates <> dupAccept then L := I;
      end;
    end;
  end;
  Index := L;
end;
 
//...
 
function TStringList.IndexOf(const S: string): Integer;
begin
  if not Sorted then Result := inherited IndexOf(S) else
    if not Find(S, Result) then Result := -1;
end;

06/07/2007, 12h15
Clorish

Citation:

Envoyé par CapJack

Juste pour information : une TStringList triée utilise déjà la recherche dichotomique.

Mais etais-ce la methode la plus rapide possible ? ;)
06/07/2007, 14h15
CapJack

D'un point de vue algorithmique, oui : c'est en O(log n), il n'y a pas plus rapide.

Maintenant, il est vrai qu'on peut multiplier la vitesse du traitement par un coefficient constant, en effectuant le traitement plutôt sur des valeurs entières que sur les chaînes elle-même, mais celà devient très compliqué car il faut alors que ce soient les valeurs de hash elle-même qui soient triées.

Pourquoi pas, mais le jeu en vaut-il la chandelle ?
06/07/2007, 14h20
Bruno13

Bonjour à tous,

tout d'abord merci pour vos réponses, ensuite en recherchant sur le forum j'ai trouvé un post qui parle de remplacer la TStringList par un TClientDataSet mais j'avoue que je n'ai pas encore regardé comment faire. (Ici)

Au final je crois que cela va être dur de faire mieux, donc peut etre revoir plus en amont dans mon traitement.

Amitiés,
Bruno
06/07/2007, 15h22
Gilbert Geyer
Bonjour,

Voiçi un fonction qui renvoie le nombre d'occurences, d'un mot ou d'un sous-mot (préfixe, suffixe, ou médiane), présentes dans une StringList elle opère donc en plein-texte et ne nécessite donc pas de Splitter le texte au préalable (tenir compte de cet aspect pour apprécier les différences dans les temps d'exécution). Elle n'est pas basée sur le principe de ne comparer que les chaines qui ont la même taille mais sur le fait qu'il est intutile de comparer lorsque dans l'avancement on recontre un caractère de texte différent du 1er caractère du mot-cherché et pour accélérer la manip les recherches s'effectuent dans un MemoryStream.
Code:

1 2 3 J'ai supprimé ce bout de code car il était plombé par une lourdeur. Une autre version répondant grosso-modo au même descriptif est en cours de cogitation.
... bien entendu cette fonction a ses limites car si on cherche le mot entier 'ami' et qu'elle rencontre 'les amibes' ou 'un beau camion' elle en tient compte dans le comptage, par contre on peut la modifier pour ne repérer que des mots complets suivis d'un espace ou d'un caractère de fin-de-ligne, ou encore pour gommer le problème des Majuscules/minuscules si on cherche 'ami' et que le texte inclut 'Ami' vu notamment que dans les textes allemands les germains mettent des majuscules même en plein milieu de leurs phrases ... à discuter car on peut également mettre tout en majuscules ou en minuscules dès la phase de capture des textes ou juste après.
07/07/2007, 11h14
Graffito

Bonjour,

De mémoire, il arrive qu'on doive remplacer le IndexOf par une fonction maison pour améliorer les performances de l'IndexOf standard qui sont en pratique dégradées par l'utilisation de l'instruction CompareStrings(FList^[i].FString, S) au lieu dune simple comparaison de chaine FList^[i].FString>S
08/07/2007, 18h22
Gilbert Geyer

Bonjour,

L'astuce de Graffito est bonne en transformant les méthodes Find et IndexOf en fonctions "maison" : dans le cas d'une StringList avec Sorted:=true la vitesse d'exécution est multipliée par un facteur de 3,28.:D

Par contre, pour Sorted:=false, comme pour ma fonction maison IndexOfSL qui remplace IndexOf
j'ai simplement remplacé la ligne d'origine d'IndexOf "if not Sorted then Result := inherited IndexOf(S) else", comme suit :

Citation:

function IndexOfSL(SL : TStringList; const S: string): Integer;
begin with SL do
if not Sorted then Result := SL.IndexOf(S) else
if not FindSL(SL,S, Result) then Result := -1;
end;

... en conséquence de ceci, dans le cas de Sorted:=false ma fonction utilise le IndexOf de la version standard avec laquelle, dans les mêmes conditions d'essais de vitesse, le temps d'exécution est multiplié par 216 !!.
... mais il y a peut être une autre manière de faire cette fonction maison en traduisant autrement la ligne "if not Sorted then Result := inherited IndexOf(S) else" pour éviter d'hériter des lenteurs de la version standard ?...;)

P.S : temps d'éxécution comparatifs :
IndexOf version standard : 146 ms avec Sorted:=false et 2,20 ms avec Sorted:=true.
IndexOfSL version maison : 145 ms avec Sorted:=false et 0,67 avec Sorted:=true. (avec Pentium III à 1,13 Ghz)
Tests effectués en cherchant 500 fois l'index du mot 'ZFin' situé à la fin d'une StringList de 500 lignes égales à S:='texte bidon pour tests' avec bien entendu Duplicates:=DupAccept.
09/07/2007, 09h56
ShaiLeTroll

Sinon, il y a une façon élégante, faire un objet qui surcharge la classe TStringList et redéfinie la méthode virtuelle CompareStrings pour l'implémenter en > au lieu des API win/Linux ...
09/07/2007, 12h04
CapJack

Vous allez dire que je pinaille, mais c'est une question de principe.

Citation:

Envoyé par Gilbert Geyer

L'astuce de Graffito est bonne en transformant les méthodes Find et IndexOf en fonctions "maison" : dans le cas d'une StringList avec Sorted:=true la vitesse d'exécution est multipliée par un facteur de 3,28.:D

Les vitesses des deux algorithmes sont effectivement proportionnelles : on peut donc bien dire que l'une est n fois plus rapide que l'autre. Attention cependant : contrairement à CompareString, la comparaison directe ne traitera pas correctement les caractères accentués ! Par exemple, "Chêne" se retrouve après "Cher"... alors qu'avec CompareStrings, le résultat est correct : ce n'est pas pour rien qu'elle met plus de temps.

Même observation pour les bons conseils menant à un remplacement des fonctions API par des fonctions maisons... en outre, les règles de comparaison changent suivant les langues européennes. C'est à la charge de l'OS de détecter les bons paramètres et les bonnes méthodes.

Citation:

Envoyé par Gilbert Geyer

... en conséquence de ceci, dans le cas de Sorted:=false ma fonction utilise le IndexOf de la version standard avec laquelle, dans les mêmes conditions d'essais de vitesse, le temps d'exécution est multiplié par 216 !!.

Alors là par contre, ça me fait bondir, car tu compare un algorithme en O(log n) avec un algorithme en O(n) : il n'y a donc pas poportionnalité !
09/07/2007, 13h04
Gilbert Geyer

Bonjour,

Citation:

CapJack a écrit :
Vous allez dire que je pinaille,

... absolument pas, car peut-on faire de la micro sans avoir à pinailler et où le moindre grain de sable peut bloquer le shmilblik ?

Citation:

CapJack a écrit :
la comparaison directe ne traitera pas correctement les caractères accentués

... exact, reste à savoir si Bruno13 a besoin de conserver les caractères accentués ou s'il n'aurait pas intérêt à convertir tous ses textes dès leur capture entièrement en majuscules non accentuées ce qui pourrait par la même occase éviter des problèmes de différences entre deux mêmes mots dont l'un figure en début de phrase avec une majuscule et le même qu'on retrouve au milieu d'une phrase tout en minuscules car l'objectif de Bruno est davantage de dégager les concepts dominants développés dans texte que les particularismes du graphisme des caractères. Mais il revient à Bruno de nous clarifier son cahier de charge à ce sujet.

Citation:

En écho à mon "le temps d'exécution est multiplié par 216 !!", CapJack a écrit :
Alors là par contre, ça me fait bondir, car tu compare un algorithme en O(log n) avec un algorithme en O(n) : il n'y a donc pas poportionnalité !

... moi ça ne me fait pas bondir ... car 145/0,67 ça fait bien 216 et je compare deux temps obtenus pour un même résultat avec deux techniques qui sont forcément différentes, bigre, sinon il n'y aurait aucune raison de comparer des temps obtenus dans les mêmes conditions d'essai par la même technique.
A+:D
09/07/2007, 13h18
CapJack

Citation:

Envoyé par Gilbert Geyer

... moi ça ne me fait pas bondir ... car 145/0,67 ça fait bien 216 et je compare deux temps obtenus pour un même résultat avec deux techniques qui sont forcément différentes, bigre, sinon il n'y aurait aucune raison de comparer des temps obtenus dans les mêmes conditions d'essai par la même technique.

J'ai dû mal m'expliquer : quand on dit "le temps d'exécution est multiplié par n" sans préciser les conditions de l'expérience, c'est-à-dire ici le nombre d'éléments comparés, celà signifie implicitement et sans ambiguïté qu'on considère ce rapport de proportionnalité comme toujours valable : or, c'est faux : le rapport trouvé, 216, n'est pas constant, et dépend du nombre d'éléments. En effet, l'une des fonctions IndexOf parcourt tous les éléments, O(n) donc, tandis que l'autre est en O(log n). Essaie, et tu verras.

Si tu avais précisé le nombre d'éléments utilisé pour l'expérimentation, je n'aurais alors effectivement pas relevé, car le contexte eût été différent.

Pour ce qui est de la conclusion ironique, c'est très amusant, mais tu constateras que personnellement, je m'abstiens de ce genre de style sur ce forum, car il est parfois difficile de comprendre ce que l'autre veut dire, et souvent facile de le prendre pour un idiot parce qu'on a soit-même raté quelque chose. :)
09/07/2007, 14h35
Gilbert Geyer

Citation:

CapJack a écrit :
quand on dit "le temps d'exécution est multiplié par n" sans préciser les conditions de l'expérience, c'est-à-dire ici le nombre d'éléments comparés, ...

... le P.S. de la fin de mon message d'hier 18h22 précise bien les conditions des tests, en voici un copier-coller :

Citation:

Tests effectués en cherchant 500 fois l'index du mot 'ZFin' situé à la fin d'une StringList de 500 lignes égales à S:='texte bidon pour tests' avec bien entendu Duplicates:=DupAccept.

... et j'ai ajouté ce P.S avant d'envoyer le post sinon il y aurait une date de dernière modification.

Citation:

CapJack a écrit : Pour ce qui est de la conclusion ironique, c'est très amusant, mais tu constateras ...

... là t'as absolument raison il faut tenir compte de la sensibililté des interlocuteurs, car la fin de ma phrase après le bigre qui marque l'étonnement peut effectivement paraître ironique ... mais cela me donne une idée : pour conserver une touche d'humour suffit que je le dirige explicitement vers moi-même.

A propos de :

Citation:

En effet, l'une des fonctions IndexOf parcourt tous les éléments, O(n) donc, tandis que l'autre est en O(log n).

... en transformant la fonction Find standard je me suis rendu compte en plus qu'elle ne parcourt jamais plus que la moitié des éléments vu qu'elle n'est appelée par IndexOf que pour des listes triées et que dans ce cas en attaquant les comparaisons par le milieu de liste il lui suffit suite à la première comparaison d'incrémenter soit en direction du début soit en direction de la fin... ce qui donne même du O(log n) divisé par deux ... Par contre c'est astucieux car si on cherche un mot situé pile au milieu de la liste la réponse doit être quasi-instantanée. Ouf! Heureusement que dans mes tests j'aie utilisé pour les recherches le mot 'ZFin' situé systématiquement en fin de liste.
A+:D