[TStringList] Optimisation du IndexOf ?

**Bruno13** · 06/07/2007, 03h53

Bonjour à tous,

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

Possible ou pas ?

Amicalement,
Bruno

**Rayek** · 06/07/2007, 08h28

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 ^^

**Clorish** · 06/07/2007, 10h05

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....

**TicTacToe** · 06/07/2007, 10h47

Bonjour,

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

**CapJack** · 06/07/2007, 12h01

Oh ! Des shadocks !

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

Extrait de la VCL :

Code :

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

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;