Alternative à un Set Of

**Cl@udius** · 27/09/2007, 18h13

Salut

Envoyé par Gilbert Geyer

... mais j'ai le message "Erreur E/S 103." ? Et là aussi je suis sec.

Remplace les WriteLn par des ShowMessage.

@+ Claudius

**sjrd** · 27/09/2007, 18h19

Envoyé par Cl@udius

Remplace les WriteLn par des ShowMessage.

Effectivement, ce genre de tests, je les fais en console. Donc avec des WriteLn. Mais ceux-ci ne fonctionnent pas dans une application GUI.

**tourlourou** · 27/09/2007, 19h06

bin moi, c'était plus grave

pour faire astucieux, j'avais fait faux...

donc :

Code :

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

1
2
3
4
5
6
7
8
9
10
function CardToBitsArray(AValue: Cardinal): TCardBitsBoolArray;
var
  c, mask: Cardinal;
begin
  for c:=0 to 31
  do begin
    mask:=1 shl c;
    Result[c]:=(AValue and mask)=mask;
  end;
end;

je n'exclus pas d'autres bugs !!!

**tourlourou** · 27/09/2007, 19h32

je n'exclus pas d'autres bugs !!!

chose promise, chose due...

**tourlourou** · 27/09/2007, 19h56

avec ce code de test:

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
procedure TForm1.Button1Click(Sender: TObject);
var
  i,j: integer;
  g: cardinal;
begin
  MyTree:=TMyCardBinTree.Create;
  g:=GetTickCount;
  for i:=0 to 100000
  do begin
    MyTree.Add(i);
  end;
  Memo1.Text:=Memo1.Text+' '+IntToStr(GetTickCount-g);
  g:=GetTickCount;
  for i:=0 to 100000
  do MyTree.IsInTheTree(i);
  Memo1.Text:=Memo1.Text+' '+IntToStr(GetTickCount-g);
  g:=GetTickCount;
  for i:=g+0 to g+100000
  do MyTree.IsInTheTree(i);
  Memo1.Text:=Memo1.Text+' '+IntToStr(GetTickCount-g);
end;

j'obtiens localement :
1,9 à 2,0 secondes pour les 100 000 ajouts, un peu plus de 400 ms pour les 100 000 recherches positives, et autour de 290 ms pour les 100 000 recherches négatives

**Gilbert Geyer** · 28/09/2007, 13h52

Bonjour,

Suite des tests :

1) Pour l'instant j'ai pu avancer. Rien qu'avec le test comparatif entre le Set logé dans un BitMap et le Set logé dans l'arbre je peux mettre mon BitMap dans la rubrique des curiosités car voiçi les résultats :

CardinalTree : N=100000 éléments
N Add : 800 ms
N recherches d'un absent : 45 ms

N recherches des présents : 164 ms

BigSetBmp : N=100000 éléments
N Add : 281 ms
N recherches d'un absent : 456 ms
N recherches des présents : 254 ms

(Avec Delphi-5, Win98 et Pentium III à 1.13 GHz)

... les résultats que j'avais annoncés précédemment pour le Set logé dans un BitMap étaient faussés du fait d'une erreur de logique, mais de toute façons le Bmp est cuit même avec les résultats annoncés les autres jours.

... pour CardinalTree je pense qu'on pourrait réduire les 800 ms en modifiant la routine TMyCardBinTree.Create dans le genre TMyCardBinTree.Create(NombrePrévisibleDElements) de manière à réserver de la mémoire prévisionnellement d'un seul coup : cela équivaut à placer le SetLength d'un array dynamique devant une boucle d'appel au lieu d'incrémenter la taille de l'array à l'intérieur de la boucle.
J'ai utilisé la même astuce dans ma version BitMap qui donne les résultas suivants lorsque je déclare BigSet.Create(0) au lieu de BigSet.Create(100001) le temps mis pour ajouter les 100000 éléments monte à 1058 ms au lieu de 281 ms. Le prédimensionnement m'a donc multiplé la vitesse des ajouts par un facteur de 3.77.
En sus d'un TMyCardBinTree.Create(NombrePrévisibleDElements) cela vaudrait le coup de prévoir un TMyCardBinTree.Grow qui serait appelé en interne lors de la tentative d'ajouts excédant le NombrePrévisibleDElements déclarés lors du Create.

2) Avancement des tests avec BigSetD7Older : Effectivement en remplacant WriteLn par des ShowMessage ça marche, merci les gars.
Par contre pour faire les tests comparatifs de vitesse dans les mèmes conditions que pour CardinalTree c'est à dire pour un ajout de 100000 éléments j'ai dû remplacer TBigValue = 0..450 par TBigValue = 0..100002 mais là cela a coincé : En conservant TBigValue = 0..100002 et en faisant seulement 11 fois BigSetInclude(BigValues, i) l'appel à BigValueSetToString(BigValues)) me renvoie la string [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 65536, 65537, 65538, 65539, 65540, 65541, 65542, 65543, 65544, 65545, 65546] c'est à dire un ensemble de plus de 11 éléments ??? A toutes fins utiles voiçi le code de test utilisé.

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
 
procedure TfrmSetOf.bTestVitesseBigSetD7OlderClick(Sender: TObject);
var       BigValues : TBigValueSet; i, N : integer;
begin     N:=10; //0000;
          Trace(#13#10+'BigSetD7Older : '+intToStr(N)+' éléments');
 
          // Expansion de l'ensemble :
          TopChrono:=GetTickCount;
          BigSetClear(BigValues);
          BigValues := BigSetCreate([0]); // avec TBigValue = 0..100002 au lieu de TBigValue = 0..450;
          //BigValues := BigSetCreate([0,N]);
 
          asm
                    MOV     EDX,$00010000
          end;
 
          for i:=0 to N do BigSetInclude(BigValues, i);
          Trace('Add : '+ChronoMis);
          Trace(BigValueSetToString(BigValues));
          //renvoie [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 65536, 65537, 65538, 65539, 65540, 65541, 65542, 65543, 65544, 65545, 65546]
 
          // Recherches dans l'ensemble de l'élément 100002 absent :
         { TopChrono:=GetTickCount;
          for i:=0 to N do if BigSetExists(BigValues,100002) then Trace('100002 présent ?'); // avec N=100000 répond N fois présent
          Trace('Recherches absent : '+ChronoMis); }
 
          { Vérifications de présence dans l'ensemble des éléments présents :
          TopChrono:=GetTickCount;
          for i:=0 to N do if Not BigSetExists(BigValues,i) then Trace(intToStr(i)+' absent?');
          Trace('Recherches présents : '+ChronoMis); }
end;

... et j'obtiens la même anomalie en initialisant avec BigValues := BigSetCreate([0,N]) au lieu de BigValues := BigSetCreate([0]); ?????

Y'a certainement un remède, mais lequel ?

A+

**sjrd** · 28/09/2007, 14h22

Envoyé par Gilbert Geyer

Y'a certainement un remède, mais lequel ?

Supprimer les 3 lignes commençant MOVZX, car tu travailles avec des valeurs stockées sur 4 octets.

**sjrd** · 28/09/2007, 15h12

Je te préviens, mon BigSetD7Older va faire des chronos records ! Mais sa place en mémoire est plus importante, enfin jusqu'à ce que l'ensemble contienne 1/32 de tous les éléments possibles.
En fait l'utilisation mémoire/temps de TBigValueSet est toujours constante (#valeurs possibles / 8 octets en mémoire, et quelques cycles du processeur en temps).

Si tu veux qqch de comparable, j'ai joint le "back-port" de TBasicIntSet pour D7 et antérieur. Attention, cette fois c'est une classe. C'est plus difficile à manipuler que les record (faut surveiller les allocations et désallocations). Voici son code de test :

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
procedure TestBigSets;
var
  BigValues, BigValues2: TBasicIntSet;
begin
  BigValues := nil;
  BigValues2 := nil;
  try
    BigValues := TBasicIntSet.Create([34, 300]);
    WriteLn(IntegerSetToString(BigValues));
 
    BigValues2 := TBasicIntSet.Create([430, 63, 54]);
    BigValues2.Union(BigValues);
    WriteLn(IntegerSetToString(BigValues2));
 
    BigValues.Include(30);
    BigValues2.Intersect(BigValues);
    WriteLn(IntegerSetToString(BigValues2));
 
    BigValues2.Clear;
    BigValues2.Include(54);
    BigValues2.Include(300);
    BigValues.Subtract(BigValues2);
    WriteLn(IntegerSetToString(BigValues));
  finally
    BigValues2.Free;
    BigValues.Free;
  end;
end;

**tourlourou** · 28/09/2007, 15h39

@ Gilbert Geyer : merci pour ton travail ! je ne suis pas sûr que ma "solution" soit si performante en terme de place mémoire : chaque noeud de l'arbre occupe 16 octets, et l'arbre est binaire => on parcourt 32 noeuds (pour les 32 bits du Cardinal) avant d'atteindre la feuille correspondant au Cardinal stocké.

cad que pour stocker MaxCardinal, il faudra 17 fois l'espace qu'ils occupent (sans compter une 18° fois pour le "garbage collector" des noeuds)

c'est tout de même énorme par rapport au tableau dynamique !

pour éviter les allocations successives, tu as tout à fait raison de proposer de réserver un bloc (sous forme d'un tableau de noeuds, pê)

au final, je suis certain que chaque solution a son domaine de prédilection, selon l'objectif : taille, rapidité, étendue de l'ensemble, opérations à mener dessus...

**Gilbert Geyer** · 28/09/2007, 15h56

Re-Bonjour,

1) Tests avec BigSetD7Older :

Sjrd : Je te préviens, mon BigSetD7Older va faire des chronos records !

... Effectivement (après suppression des 3 MOVZX) ça décoiffe!!! Voiçi ce que me dit le mémo :

BigSetD7Older : N=100000 éléments
N Add : 0 ms
N Recherches absent : 6 ms
N Recherches présents : 4 ms

... parfois il m'affiche même 0 ms dans les trois cas, j'ai même dû inverser les conditions d'affichage pour me rendre compte qu'il parcourait bien l'ensemble.
Et je me demande même si les 6 ms et les 4 ms ne sont pas en fait du temps pris par Windows qui a piqué la main au même moment.

Au fait il sert à quoi le MOV EDX,$00010000 qu'on place juste après le BigValues:= BigSetCreate([0,N]) ???
Ne pourrait on pas le loger dans la fonction BigSetCreate comme dernière ligne ?

2) Tests avec TBasicIntSet : Comme je viens de le découvrir en revenant sur le forum je ne l'ai pas encore essayé mais je m'attends à obtenir des résultats similaires.

En tous cas merci et surtout "Chapeau".

A+

**sjrd** · 28/09/2007, 16h13

Envoyé par Gilbert Geyer

Au fait il sert à quoi le MOV EDX,$00010000 qu'on place juste après le BigValues:= BigSetCreate([0,N]) ???
Ne pourrait on pas le loger dans la fonction BigSetCreate comme dernière ligne ?

Il ne "sert" à rien. C'était uniquement pour le test du cas défavorable du Include - qui a été solutionné avec l'utilisation judicieuse de MOVZX justement (à mettre si 2 octets, à ne pas mettre si 4 octets). Tu peux le supprimer bien sûr. Jamais je n'obligerais l'utilisateur de mes classes à utiliser de l'assembleur !

**Laurent Dardenne** · 28/09/2007, 16h15

Avec un peu de retard,

Envoyé par sjrd

Mais le choix entre record ou class est un choix sémantique, pas technique. Une classe n'a pas la même utilisation qu'un record. Mais je serais totalement incapable d'expliquer les différences d'utilisation. C'est une histoire d'habitude et de filling.

Je suis un peu embarassé car je suis aussi d'accord sur ce point de vue

Ce serait vraiment intéressant d'avoir l'avis des concepteurs des dernières version de Delphi sur ce point.
La doc de Delphi parle de record avancé, je pourrais m'en contenter pour éviter de faire le grand écart, mais je n'en sais pas plus quant à la direction de cette avancée. Je n'ai rien d'autre à ajouter, provisoirement

, sur le sujet.

Sinon sur les termes Object, Class et Instance je vous invite à consulter un dictionnaire d'Anglais US récent, car on voit bien que l'usage des mots Anglais ne renvoient pas clairement vers le concept sous-jacent quand il est exprimé en Français, d'où l'incompréhension que leurs usage succitent.
Class =Genre,
Instance=cas,
Object=Chose.
On peut aussi ce faire des trous dans le cerveau avec les genres de genre, les fameuses meta-class...
Enfin ça c'est une autre discussion.

Envoyé par tourlourou

avec ce code de test:

Puisque vous en êtes aux tests de performances je me demandais si, dans ce cas, l'insertion des valeurs au sein d'une boucle n'allait pas créer un arbre déséquilibré, influant donc sur les résultats des tests.

En même temps il y pas mal de temps que je n'ai pas utilisé d'arbre dans mes développements, j'ai donc un doute quant à la pertinence de ma remarque.

**Gilbert Geyer** · 28/09/2007, 16h34

Re-Bonjour,

@Tourlourou : Nos posts se sont croisés (je suis assez lent lorsque je rédige).
Tu dis "je ne suis pas sûr que ma "solution" soit si performante en terme de place mémoire" j'aurais plutôt dit que si ta solution avait été plus rapide que celle de Sjrd je ne me serais pas trop inquiété au sujet de la place mémoire vu qu'on n'en est plus au debut de micro-informatique où il fallait économiser chaque octet sans oublier qu'on n'a pas tous les jours besoin de gérer un ensemble de 100000 éléments. Et comme l'objectif était de franchir la limite des 256 éléments d'un Set Of standard je pense que ce problème est réglé car c'est toujours gênant si on veut un ensemble de 257 éléments et d'être coincé à cause du 257ième qui ne rentre plus.

En tous cas c'était intéressant de comparer trois approches différentes.

Ce matin j'avais même testé ton code pour la recherche des occurences des couleurs présentes dans une image pour voir s'il n'y avait pas une idée qui aurait permis d'améliorer la rapidité de mon BigSetBmp, juste pour le Fun et pour voir les limites d'améliorabilité car avec les résultats obtenus avec BigSetD7Older de Sjrd ce n'est certainement pas dans l'espoir de faire encore plus speed.

A+

P.S : je viens de m'apercevoir que j'ai pas terminé ce post qu'il y en a déjà deux autres qui se sont ajoutés.

**Gilbert Geyer** · 28/09/2007, 16h38

Re-bonjour,

A Sjrd : Merci pour ta réponse à propos du MOV EDX,$00010000, je vais donc le supprimer.

A+

**Gilbert Geyer** · 28/09/2007, 17h24

Re-Bonjour,

sjrd (Aujourd'hui, 15h12) : Si tu veux qqch de comparable, j'ai joint le "back-port" de TBasicIntSet pour D7 et antérieur. Attention, cette fois c'est une classe.

... je viens de comparer le contenu du fichier attaché à celui de la version précédente de BigSetD7Older.pas je n'y ai pas trouvé ni de classe, ni de TBasicIntSet : c'est presque le même code sauf que dans l'un on trouve BigSetSubstract et dans l'autre BigSetSubtract sans le s ? Apparemment le fichier attaché n'est pas celui que tu voulais attacher. Oui/Non ?

A+

**sjrd** · 28/09/2007, 23h16

Envoyé par Gilbert Geyer

Apparemment le fichier attaché n'est pas celui que tu voulais attacher. Oui/Non ?

Euh ouais qué biess

Et en plus faudra attendre dimanche soir pour que j'ai de nouveau le code sous la main

Désolé

**tourlourou** · 29/09/2007, 09h22

Le gros avantage de la solution TBitmapSet est d'implémenter nativement les sauvegardes fichier !
Pour le TBigSet, c'est enfantin à écrire.
Pour l'arbre, c'est plus compliqué...

Pour les performances, le TBigSet étant tellement compact, je ne suis pas étonné des performances

**Gilbert Geyer** · 29/09/2007, 13h39

Bonjour,

A sjrd :

Et en plus faudra attendre dimanche soir pour que j'ai de nouveau le code sous la main

... Cool. Y'a pas le feu cela peut même attendre lundi.

A Tourlourou :

Le gros avantage de la solution TBitmapSet est d'implémenter nativement les sauvegardes fichier !

... Tiens je n'avais pas pensé à cet avantage. Par contre avec ses 456 ms contre les 6 ms de BigSetD7Older mon BitMap n'a même pas fini d'être créé que BigSetD7Older a déjà terminé !!!.
.... Mais si la solution du TBitmapSet t'intéresse pour l'avantage des sauvegardes fichier je peux te passer la dernière version du code vu que j'ai apporté plein de modifs à la version que j'ai postée au début. Tu trouveras peut-être une astuce qui permettrait d'en améliorer la rapidité d'exécution car il y a peut-être une loudeur de style dans mon code.
.... Par contre si la sauvegarde-fichier à partir du TBigSet est enfantine à écrire autant profiter de sa rapidité d'autant plus qu'il permet également de gérer des ensembles de TColor.

A+

**Gilbert Geyer** · 30/09/2007, 16h13

Bonjour,

A Sjrd :

En bidouillant dans BigSetD7Older j'ai pu le modifier de sorte que l'on puisse choisir de façon logicielle d'utiliser, en fonction des besoins, soit des valeurs stockées sur 4 octets soit sur 2 octets en modifiant les trois routines qui utilisent le MOVZX de la même façon que ce bout de code :

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
 
var   Sur4Octets : byte; // 4 = valeurs stockées sur 4 octets
                         // sinon valeurs stockées sur 2 octets
// la valeur de Sur4Octets étant initialisée pour les 3 routines concernées
// lors de l'appel à la function BigSetCreate(const iSur4Octets : byte; const Values: array of TBigValue): TBigValueSet;
 
function BigSetExists(const BigSet: TBigValueSet; Value: TBigValue): Boolean;
         // -> EAX        Address of the TBigValueSet record
         //    DX         Value to test
         // <- AL         Result
asm      MOV   CL,Sur4Octets
         CMP   CL,4
         JE   @@Saut
         MOVZX   EDX,DX
      @@Saut:
         BT      [EAX],EDX
         SETB    AL
end;

... cette modif marche
... par contre je voulais également choisir de façon logicielle en fonction du contexte d'utilisation la limite supérieure de TBigValue comme suit :

Code :

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

1
2
3
4
5
6
7
8
9
10

const   inMax = 100000;  // <-- ça marche évidemment
// var  inMax = Cardinal; // <-- et ça ne marche évidemment pas mais cela illustre ce que j'aurais voulu pouvoir faire
type
  // Un type trop grand pour être mis dans un ensemble
  //TBigValue = 0..450;
  //TBigValue = 0..2000000; ok //16777215; débordement de pile
  //TBigValue = 0..100000;
  TBigValue = 0..inMax;