Discussion :

[Benoit_T]

Bonjour,

Je cherche une implémentation delphi qui me permette l'accès à un entier strictement positif à partir d'une clé représentant un entier strictement positif aussi.

En fait c'est pour coder un tableau "discontinu" par exemple:

[1, , , , 8 , , , , 11]

Le truc c'est que je veux que ça se comporte comme un tableau en terme de complexité big O. Par exemple un accès et une écriture en O(1) quelque soit l'indice.

Une solution ne serait t'elle pas les tables de hashage?
Quelle dégradation en terme de performance dois-je envisager entre un accès à la case 5 d'un tableau (en O(1) direct) et un accès à la valeur codé par la clé 5 d'une hashmap?

Ne peut-on pas tirer parti des priorité mathématiques des objets de la table (en l'occurence les clés comme les valeurs sont entières, positives et bornées)

Cordialement,

[Benoit_T]

Oui bon je me suis replongé dans quelques documents et la table de hashage (hashmap) me semble être la bonne solution. Seulement, j'aimerais minimiser les collisions... Le fait que je travaille sur des nombres entiers bornés (par 20000) implique qu'il doit exister des fonctions de hashage adaptées à ce cas particulier...

Connaissez-vous une implémentation avec des type primitifs de la hashmap ?

cordialement,

[ShaiLeTroll]

tu peux aussi voir ton entier comme ce qu'il est un tableau de bit, et faire un arbre binaire ... c'est extrément rapide !

j'ai écrit pour l'exemple la classe TTreeHashingObjectList qui associe une chaine avec un objet

Regarde ce sujet "Suppresioon liste non triée" sur Phidels, regarde la fonction FindCardinal que j'ai écrite ... ça doit pouvoir t'interesser, faudrait que j'en fasse un objet, j'ai pondu cela pour la discussion, c'est codé à l'arrache ...

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
type
  PCardinalBitTreeNode = ^TCardinalBitTreeNode;
  TCardinalBitTreeNode = record
    Childs: array[Boolean] of PCardinalBitTreeNode;
  end;
  TCardinalBitTreePath = array[0..31] of ByteBool;
 
function PathCardinal(Value: Cardinal): TCardinalBitTreePath;
const
  BIT_MASK : array[0..31] of Cardinal =
    (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536,
    131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216,
    33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648);
var
  I: Byte;
begin
  for I := 0 to 31 do
    Result[I] := (Value and BIT_MASK[I]) = BIT_MASK[I];
end;
 
function FindCardinal(Root: PCardinalBitTreeNode; Value: Cardinal): Boolean;
var
  Path: TCardinalBitTreePath;
  I: Byte;
  Node: PCardinalBitTreeNode;
begin
  Result := False;
 
  Path := PathCardinal(Value);
 
  Node := Root;
  for I := 0 to 31 do
  begin
    if not Assigned(Node) then
      Exit;
 
    Node := Node.Childs[Path[I]];
  end;
 
  Result := True;
end;
 
procedure SetCardinal(var Root: PCardinalBitTreeNode; Value: Cardinal);
var
  Path: TCardinalBitTreePath;
  I: Byte;
  Parent: PCardinalBitTreeNode;
  Node: PCardinalBitTreeNode;
begin
  Path := PathCardinal(Value);
 
  Parent := nil;
  Node := Root;
  for I := 0 to 31 do
  begin
    if not Assigned(Node) then
    begin
      New(Node);
      ZeroMemory(Node, SizeOf(Node^));
      if I > 0 then
        Parent.Childs[Path[I - 1]] := Node
      else
        Root := Node
    end;
 
    // Next
    Parent := Node;
    Node := Node^.Childs[Path[I]];
  end;
end;
 
procedure FreeTree(var Root: PCardinalBitTreeNode);
begin
  if Assigned(Root) then
  begin
    FreeTree(Root.Childs[False]);
    FreeTree(Root.Childs[True]);
 
    Dispose(Root);
    Root := nil;
  end;
end;

pour tester

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
  Tree: PCardinalBitTreeNode;
begin
  Tree := nil;
  SetCardinal(Tree, 1);
  SetCardinal(Tree, 8);
  SetCardinal(Tree, 11); 
  if FindCardinal(Tree, 1) then
    ShowMessage("1");
  if FindCardinal(Tree, 8) then
    ShowMessage("8");
  if FindCardinal(Tree, 11) then
    ShowMessage("11");
  if FindCardinal(Tree, 4) then
    ShowMessage("4");
 
  FreeTree(Tree);
end;

Pour ton besoin, tu dois modifier comme ceci, je pense, je n'ai pas 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
type
  PWordBitTreeNode = ^TWordBitTreeNode;
  TWordBitTreeNode = record
    Childs: array[Boolean] of PWordBitTreeNode;
    AssociateValue: Word;
  end;
  TWordBitTreePath = array[0..31] of ByteBool;
 
function PathWord(Value: Word): TWordBitTreePath;
const
  BIT_MASK : array[0..15] of Word =
    (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768);
var
  I: Byte;
begin
  for I := 0 to 31 do
    Result[I] := (Value and BIT_MASK[I]) = BIT_MASK[I];
end;
 
function FindWord(Root: PWordBitTreeNode; Value: Word; out AssociateValue: Word): Boolean;
var
  Path: TWordBitTreePath;
  I: Byte;
  Node: PWordBitTreeNode;
  Parent: PWordBitTreeNode;
begin
  Result := False;
 
  Path := PathWord(Value);
 
  Parent := nil;
  Node := Root;
  for I := 0 to 31 do
  begin
    if not Assigned(Node) then
      Exit;
 
    Parent:= Node;
    Node := Node.Childs[Path[I]];
  end;
 
  AssociateValue := Parent.AssociateValue;
  Result := True;
end;
 
procedure SetWord(var Root: PWordBitTreeNode; Value: Word; AssociateValue: Word);
var
  Path: TWordBitTreePath;
  I: Byte;
  Parent: PWordBitTreeNode;
  Node: PWordBitTreeNode;
begin
  Path := PathWord(Value);
 
  Parent := nil;
  Node := Root;
  for I := 0 to 31 do
  begin
    if not Assigned(Node) then
    begin
      New(Node);
      ZeroMemory(Node, SizeOf(Node^));
      if I > 0 then
        Parent.Childs[Path[I - 1]] := Node
      else
        Root := Node
    end;
 
    // Next
    Parent := Node;
    Node := Node^.Childs[Path[I]];
  end;
 
  Parent.AssociateValue := AssociateValue;
end;
 
procedure FreeTree(var Root: PWordBitTreeNode);
begin
  if Assigned(Root) then
  begin
    FreeTree(Root.Childs[False]);
    FreeTree(Root.Childs[True]);
 
    Dispose(Root);
    Root := nil;
  end;
end;

pour tester

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
var
  Tree: PWordBitTreeNode;
  V: Word;
begin
  Tree := nil;
  SetWord(Tree, 1, 17);
  SetWord(Tree, 8, 49);
  SetWord(Tree, 11, 314); 
  if FindWord(Tree, 1, V) then
    ShowMessage("1 : " + IntToStr(V));
  if FindWord(Tree, 8, V) then
    ShowMessage("8 : " + IntToStr(V));
  if FindWord(Tree, 11, V) then
    ShowMessage("11 : " + IntToStr(V));
  if FindWord(Tree, 4, V) then
    ShowMessage("4 : " + IntToStr(V));
 
  FreeTree(Tree);
end;