Discussion :

[sjrd]

Pour le TBigSet, c'est enfantin à écrire.

Code :

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

Stream.WriteBuffer(MonSet, SizeOf(TBigValueSet));

C'est un simple record sans type à initialisation, donc ça passe sans aucun problème.

Pour l'arbre, c'est plus compliqué...

Bah faut l'écrire quoi

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

Ca n'a rien à voir avec la taille des données. C'est juste que j'utilise une indexation simple pour agir sur l'ensemble.

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 :

C'est effectivement une solution, mais ça serait quand même mieux avec une variable de type Boolean Et de plus qui soit champ de l'ensemble.

Par contre, puisque de toutes façons ceci est impossible :

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

Ca ne sert à rien

L'idéal serait d'utiliser un template de record, ce que l'on pourra faire dans Delphi Tibúron. En attendant, il faudrait travailler avec Integer en général et faire un tableau dynamique de Contents. Mais ça retirerait pas mal de simplicité et notamment l'enregistrement/sauvegarde à coup de Write/ReadBuffer.

Je préfère donc recréer un record pour chaque grand ensemble à utiliser. En même temps, on n'utilise pas de type de données très souvent

[Gilbert Geyer]

Bonjour,

A Sjrd :

... mais ça serait quand même mieux avec une variable de type Boolean.

... Ok : c'est fait.

Et de plus qui soit champ de l'ensemble

... je suppose que tu veux dire champ du type BigValueSet = record ... ?

Pour la suite (choisir de façon logicielle en fonction du contexte d'utilisation la limite supérieure de TBigValue) : vu tes remarques je laisse tomber.
C'est vrai qu'on n'a pas tous les jours besoin d'un ensemble de 200000 éléments.

Au fait, est tu toujours d'accord pour nous passer le "back-port" de TBasicIntSet pour D7 et antérieur encapsulé dans une classe évoqué dans ton msg du 28/09/2007 15h12 ?

A+

[sjrd]

... je suppose que tu veux dire champ du type BigValueSet = record ... ?

Oui c'est bien ça.

Au fait, est tu toujours d'accord pour nous passer le "back-port" de TBasicIntSet pour D7 et antérieur encapsulé dans une classe évoqué dans ton msg du 28/09/2007 15h12 ?

J'ai déjà dit que j'avais mis à jour le message en question avec le bon fichier

[Gilbert Geyer]

Re-Bonjour,

A Sjrd : "champ supplémentaire du type BigValueSet = record"
... ok c'est fait.
... TBasicIntSet pour D7 et antérieur :

J'ai déjà dit que j'avais mis à jour le message en question avec le bon fichier

... mille excuses, cela m'avait passé sous le nez
... merci beaucoup, je vais le récupérer illico.

A+

[Gilbert Geyer]

Re-Bonjour,

A Sjrd : Pas de chance : Delphi-5 me répond :

[Erreur fatale] IntSetD7Older.pas(6): Fichier non trouvé : 'Types.dcu'

... cette unité n'existe pas sous Delphi-5.
... Et si je l'enlève du Uses c'est sur TIntegerDynArray que cela coince :

[Erreur] IntSetD7Older.pas(17): Identificateur non déclaré : 'TIntegerDynArray'

... dommage car comme IntSetD7Older n'utilise aucune ligne en Asm je pensais enfin pouvoir piger le fonctionnement.

A+

[sjrd]

Ah ! Je croyais que cette unité existait depuis la nuit des temps

Définis le type TIntegerDynArray comme ça :

Code :

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

1
2
type
  TIntegerDynArray = array of Integer;

[Gilbert Geyer]

Re-bonjour,

A Sjrd : Ok, ça marche à merveille :

IntSetD7Older : N=100000 éléments
N Add : 35 ms
N Recherches absent : 14 ms
N Recherches présents : 25 ms

... et en plus c'est presque aussi rapide qu'avec la variante en Asm.

Merci mille fois.

A+

[Gilbert Geyer]

Bonjour,

A Sjrd : Le hasard a voulu qu'en faisant du lèche-vitrine sur d'autres sites je suis tombé sur un bout de code simple qui permet de modifier de façon logicielle la valeur d'une "constante". Le voiçi à toutes fins utiles, il pourra servir dans d'autres contextes (testé ça marche) :

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
 
// change the value of Constants?	
// Author: Thomas Weidenmueller 
 
procedure ChangeConst(const Constant; var Value; Size: Integer);
begin
              Move((@Value)^, (@Constant)^, Size);
end;
 
// How to use ChangeConst: (Sample)
 
const
         TestStrConst: string = 'This is a text sample';
         TestInteger: Integer = 4367;
var
         NewString: string;
         NewInteger: Integer;
begin
         // String Demo:
         ShowMessage('Before ChangeStringConst (TestStrConst): ' + TestStrConst);
         NewString := 'New Value';
         ChangeConst(TestStrConst, NewString, SizeOf(string));
         ShowMessage('After ChangeStringConst (TestStrConst): ' + TestStrConst);
         // Integer Demo:
         ShowMessage('Before ChangeStringConst (TestInteger): ' + IntToStr(TestInteger));
         NewInteger := 93534;
         ChangeConst(TestInteger, NewInteger, SizeOf(Integer));
         ShowMessage('After ChangeStringConst (TestInteger): ' + IntToStr(TestInteger));
end;
// http://www.swissdelphicenter.ch/torry/showcode.php?id=1284

A+

[sjrd]

Oui mais là il s'agit d'une constante typée uniquement. Et ici la constante est non typée et surtout elle est utilisée pour définir la taille d'un tableau statique, ce qui se fait de toutes façons à la compilation. Donc ça ne marche certainement pas dans notre cas.

Autre chose, modifier une variable par Move de la sorte, c'est très dangereux dans le cas de types qui requièrent une initialisation, comme string. Une bonne façon de faire est d'utiliser la routine CopyData de l'unité ScTypInfo.pas.

[Gilbert Geyer]

Bonjour,

A Sjrd :

...Donc ça ne marche certainement pas dans notre cas.

... ok j'avais d'ailleurs dit que ça "pourra servir dans d'autres contextes" vu que t'avais déjà dit que ça ne servait à rien dans notre cas.
... moi je pensais que c'était carrément impossible de modifier des constantes.

modifier une variable par Move de la sorte, c'est très dangereux dans le cas de types qui requièrent une initialisation, comme string.

... merci pour cette info, donc à réserver pour le cas de constantes typées uniquement.
- Je vais me faire une copie de ScTypInfo.pas, merci pour ce tuyau.

A propos de IntSetD7Older : J'ai examiné le code pour repérer le "mystère" qui expliquerait sa rapidité d'exécution car je m'attendais à ce qu'il serait nettement plus lent que BigSetD7Older dont la rapidité s'explique en partie du fait de l'emploi de l'Asm : Y-a-t-il un truc qui expliquerait la rapidité de IntSetD7Older ?

A+

[sjrd]

Y-a-t-il un truc qui expliquerait la rapidité de IntSetD7Older ?

Uniquement des trucs d'algorithmique de base comme :

• Pré-allocation du tableau avec plus de cases que strictement nécessaire ;
• La liste est conservée triée, ce qui permet une recherche dichotomique, donc O(log n), beaucoup plus rapide qu'une recherche linéaire.

C'est à peu près tout

[Gilbert Geyer]

Bonjour,

A Sjrd : Merci pour ces infos. Je pensais qu'il y avait un sioux dans ce mécanisme d'horlogerie. Par contre c'est certain que le choix de la structure de base a également joué un rôle important dans la rapidité vu qu'avec mon BigSet logé dans un BitMap j'avais également usé de la Pré-allocation et pour éviter d'avoir à scanner toutes les ScanLines du BitMap j'avais fixé sa hauteur à 256 et affecté chaque ligne à l'intensité de Rouge correspondante ce qui a permis lors des recherches d'"élément présent ou absent" de ne scanner que la ScanLine correspondante mais malgré ceci c'est resté hyper-lent comparativement à IntSetD7Older.

A+

[tourlourou]

voici un ch'ti code, dérivé de l'exemple de sjrd, mais adapté en classe, avec une taille d'ensemble variable :

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const
  MaxCapacity     = $01000000; // arbitraire (stockage sur 2 Mo)
  DefaultCapacity = $00010000; // 65536 éléments (soit 8 Ko)
 
type
  Str30=string[30];
  TCardTab=array of Cardinal;
 
type
  TdyBigSet=class
  private
    PContents: array of Cardinal;       // ne rien modifier dans les déclarations,
    FCapa: Cardinal;                    // et ne surtout pas ajouter de champ avant
    FElements: Cardinal;                // pour ne pas décaler les offsets des champs
    FHighest: Cardinal;                 // par rapport à l'adresse de l'objet (EAX=self)
    FTabLen: Cardinal;
    FContentSize: Cardinal;
    FVarCap: Boolean;
    FHighMask: Cardinal;                // masque des bits non utilisés du dernier Cardinal
    FName: Str30;
    procedure FError(AType: Cardinal);
    function CompteElements: Cardinal;
    procedure SetCapa(AValue: Cardinal);
    function GetValues: TCardTab;
  public
    constructor Create(AName: Str30; ACapacity: Cardinal = DefaultCapacity); overload;
    constructor FileCreate(AFileName: string);
    destructor Destroy; override;
    procedure Clear;
    procedure Include(AValue: Cardinal);
    procedure Exclude(AValue: Cardinal);
    procedure SetValues(AValues: array of Cardinal);
    procedure AddValues(AValues: array of Cardinal);
    procedure SupprValues(AValues: array of Cardinal);
    function IsEmpty: Boolean;
    function IsFull: Boolean;
    function IsInSet(AValue: Cardinal): Boolean;
    function AreInSet(AValues: array of Cardinal): Boolean;
    function Equals(ABigSet: TdyBigSet; StrictEquality: Boolean = False): Boolean; // True pour tester l'identité
    procedure Union(ABigSet: TdyBigSet);                                           // des contenus et des capacités
    procedure Substract(ABigSet: TdyBigSet);
    procedure Intersect(ABigSet: TdyBigSet);
    procedure SaveToStream(AStream: TStream);
    procedure LoadFromStream(AStream: TStream);
    procedure SaveToFile(AFileName: string);
    procedure LoadFromFile(AFileName: string);
  property Name: Str30 read FName;
  property Elements: Cardinal read FElements;                       // nombre d'éléments présents dans l'ensemble
  property Capacity: Cardinal read FCapa write SetCapa;             // capacité de l'ensemble ( en nombre d'éléments)
  property VariableCapacity: Boolean read FVarCap write FVarCap;    // True si on peut modifier la taille de l'ensemble
  property Values: TCardTab read GetValues;                // renvoie les valeurs contenues dans l'ensemble
  end;