Recherche dans un TObjectListRésolu

Question

Yo dudes,

Me pose une question moi, j'ai TobjectList, remplit de TmyBidule qui ont cette tete là :

  type TareaColor = class
  Color: TColor;
  Rect : TRect;
  end;

et quand j'ai besoin de savoir si une couleur a déja été vue j'ai cette petite fonction:

//--------------------------------------------------------
function DejaVu(aColor:TColor;var aIndex:integer):boolean;
var i:integer;
begin
  Result:=False;

  with AreaColorList do
  if Count > 0 then
  for i:=Count-1 downto 0 do
  if TareaColor(items[i]).Color = aColor
  then
  begin
    Result:=True;
    aIndex:=i;
    break; {Pour pas me taper toute la liste si j'ai déja trouvé}
  end;
end;

Convenez que ca ressemble fortement à IndexOf, non ? Et c'est ca qui me turpine : J'ai beau me creuser la tete je ne vois pas comment faire pour utiliser IndexOF avec pour seul argument de recherche une valeur de Color ?

Je pourrai aussi trier cette liste sur la valeur de Color, regarder si la couleur que je recherche est plus proche du début que de la fin, et selon le cas utiliser un compteur incrémenté ou décrémenté dans ma fonction DejaVu (ce qui me diviserait par 2 le temps de recherche) mais au prix d'un tri.

Ou alors c'est de tétracapelloctomie, car ca n'irai pas plus vite, et je ferai mieux d'aller courrir 10 bornes au lieu de poser des questions à la "mord-moi le TObject" ?

florenth · Accepted Answer

Ah, oui, avec 120, tu es bon pour mille bornes ! Déjà moi, avec plus d'un milier de chaines (mais de seulement 4 caractères), j'ai essayé d'accélérer la recherche.

Bilan final : bof bof !
Evidemment c'est plus rapide une fois trié mais il faut en plus compter le temps du tri et à la fin, j'ai gagné quelque millisecondes (genre au lieu de 25 ms ça me faisait 22,23). C'est pour ça qu'il faut réserver ça au grandes listes.

++

Si tu ne te plantes pas ......
tu ne pousseras jamais

florenth · Answer

Je pense que tu es bien parti pour tes dix bornes  (génial le redimentionnement de smiley !)

La méthode de tri pour rechercher s'applique seulement aux chaînes (d'après ce que je sais) car leur comparaison est plus longue.
On établit un hash (sur un nombre très restreint de bits, c-à-d 16 ou 32), puis on trie selon la valeur de ce hash et quand on cherche, on cherche d'abord le hash de la chaine demandée et on effectue une recherche dichotomique.
Je ne sais pas trop si tu as compris. Va voir dans l'aide su sujet de la classe THashedStringList de l'unité IniFiles.
En tout cas, même pour les chaines, cette méthode ne fait pas gagner énormément de temps, sauf si on a une liste énorme.
Alors pour des simpes TColor, je ne pense pas que ce soit une bonne idée.

Après, ça dépend du nombre de TAreaColor que tu as dans ta liste. Si tu en a par exemple plus d'un milier, ça vaut peut-être la peine de chercher une optimisation ...

++

Si tu ne te plantes pas ......
tu ne pousseras jamais

florenth · Answer

Correction: pardon pour le terme "dichotomie" qui est aussi une méthode de recherche rapide mais qui n'est pas celle que je te décris.
Je commence à tout confondre moi, j'ai besoin de vacances (mais je suis déjà en vacances lol) => au dodo.

DeltaFX · Answer

J'ai 120 objets au max dans ma liste, donc je suis bon pour allez courrir, je crois

DeltaFX · Answer

Je continue ce topic, ca concerne toujours les TobjectList :

Ailleurs dans mon prog, j'ai un autre bestiau sur le meme principe, qui lui charge des :
type Tpoi = class
  Nature:string;
  GPS : TGps;
  Dist: Extended;
end;

Avant de découvrirle tobjectlist, j'utilisais un tableau dynamique redimensionné sans arret, donc j'ai regarder de plus pres le Tobjectlist, et là, pouf, le choc, je découvre dans la doc qu'il est plus sage de modifier capacity avant de charger la bete, pour eviter un morcellement mémoire et une tripotée de re-réservation mémoire si count=capacity. Ce TobjectList charge une quantité variable d'entitées depuis un fichier, mais globalement ca se situe aux alentours de 1500 (POI : Point Of Interest, et c'est une liste des radars routiers, oui, j'avoue !) Comme cette môdite liste ne va sans doute qu'augmenter, je me suis retrouvé à écrire ca:

Dans le formCreate:
PoiList:=TObjectList.Create(True);

Avant la lecture du fichier,
PoiList.Capacity:=2000; // En gros

Avant l'ajout d'un nouvel objet
PoiList.Expand;
au cas ou je dépasse 2000 entrées... mais qui ne fait rien si count < capacity;

Une fois le fichier lu entierement, si trop de place réservée au début :
with PoiList do
begin
  Pack;
  Capacity:=Count;
end;

Et dans le close de ma form
PoiList.Free;

J'ai rien oublié ????

florenth · Answer

Euh, normalement tu n'est pas obligé d'appeler Expand() avant d'ajouter un objet.
En tout cas, même si ta liste augmente (ben oui, en ce moment, c'est la floraison des radars lol),  tu n'es pas obligé de changer Capacity. c'est fait tout seul par la méthode Grow().

Le fait de ramener Capacity à Count est interessant (je n'y avais jamais pensé) mais ce n'est pas la peine d'appeler Pack() sauf si certains items que tu ajoutes sont "nil"

++

Si tu ne te plantes pas ......
tu ne pousseras jamais

DeltaFX · Answer

Expand d'apres la doc : La méthode Expand permet d'ajouter de l'espace afin d'ajouter des éléments àla liste.Expand ne fait rien si la capacitéde la liste (Capacity)n'est pas entièrement utilisée.

Si Count =Capacity, Expand augmente la valeur de Capacity de la manière suivante. Si la valeur de Capacity est supérieure à 8, Capacity augmente de 16. Si la valeur de la capacitéest supérieure à 4 et inférieure à 9, Capacity augmente de 8. Si la valeur de la capacitéest inférieure à4, Capacity augmente de 4.
La méthode renvoie l'objet liste agrandi.

(perso le choix des valeurs la dedans me laisse dubitatif quant à la qualité de la moquette consommée, hein ;) ) 
donc si j'ai bien compris la doc, appeler expand permet d'augmenter capacity de plusieurs cran d'un coup, ce qui allège d'autant les n chargements ultérieurs.

Pack, la doc me dit ca :La méthode Pack déplace tous les éléments non-nil (Delphi)ou non-NULL (C++)au début du tableau Items,puis réduit la propriétéCount au nombre d'éléments réellement utilisés.Pack ne libère pas la mémoire utilisée pour stocker les pointeurs nil (Delphi)ou NULL (C++).Pour libérer la mémoire allouée aux entrées inutilisées qui sont supprimées par Pack,affectez la nouvelle valeur de Count àla propriétéCapacity.

Alors je me suis dit, vu que j'ai initialisé capacity a 2000,et lu juste 1500 poi, y  a 500 objet réservés qui sont à nil. Donc par sécurité, je pack,( pour etre sur, bien que normalement les 500 à nil sont en bout de list) et je retaille, histoire de récupérer de la Ram.

Recherche dans un TObjectList

7 réponses

Votre réponse

Discussions similaires