Comment optimiser le test de la présence d'un nombre dans "une liste" ?

Version imprimable

26/03/2022, 09h51
sbadecoder

Comment optimiser le test de la présence d'un nombre dans "une liste" ?

Description :
Je dispose d'une "liste" fixe de 50 à 15000 nombres différents, chacun compris entre 1 et 300000,
et d'une variable entière L, non connue à l'avance "et changeante", que je dois tester - disons 1 million de tests - pour savoir si elle est dans ma liste.

Solution envisagée :
1) Préparer mes données de manière optimisée : array of integer, array of boolean, list, collection, autre ?
2) Effectuer la boucle j de 1 million de tests sur la variable L définie par exemple par L := random(300000)+1;
3) Mesurer les temps mis par l'algorithme retenu (1 et 2) pour évaluer son efficience.
26/03/2022, 10h31
Charly910

Bonjour,

tu pourrais placer ta liste de nombres dans un TStringList avec Sorted à true, puis faire une recherche par dichotomie qui serait surement assez rapide.

Le problème, c'est que le tri des chaines diffère du tri des nombres.

A+
Charly

Si mes souvenirs sont corrects vous utilisez D10 donc vous devoir avoir accès aux tableaux dynamiques

un Array peut être facilement trié (pour répondre @Charly910)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 uses System.Generics.Collections, { TArray } System.Generics.Defaults; { TComparer<T> } var meschiffres : TArray<string>; ... { Sorts the array case insensitive } TArray.Sort<string>(meschiffres, TComparer<string>.Construct( function (const A, B: string): Integer begin result:=0; // égal if StrToIntDef(A,0)<StrToIntDef(B,0) then result:=-1 else if StrToIntDef(A,0)>StrToIntDef(B,0) then result:=1; end ));
ensuite une recherche dichotomique sera nickel sur un ensemble trié

il faut en effet faire une recherche dichotomique, mais pas sur une TStringList s'il te plait !

System.Generics.Collections possède déjà tout ce qu'il faut

Code:

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
 
uses
  System.Generics.Collections;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
// je crée une liste de 100 (pour le test) valeurs aléatoires
  var List: TArray<Integer>;
  SetLength(List,  100);
  for var I := 0 to Length(List) - 1 do
      List[I] := Random(300000) + 1;
 
// je garde la valeur du premier élément
  var N := List[0];
 
// je trie la liste 
  TArray.Sort<Integer>(List);
 
// recherche dichotomique de la valeur 12
  var Found: Integer;
  if TArray.BinarySearch<Integer>(List, 12, Found) then
    ShowMessage('12 est à l''index ' + Found.ToString)
  else
    ShowMessage('12 n''est pas dans la liste');
 
// recherche dichotomique de la valeur qui était à l'index 0
  if TArray.BinarySearch<Integer>(List, N, Found) then
    ShowMessage(N.ToString + ' est à l''index ' + Found.ToString)
  else
    ShowMessage('ça c''est pas normal !');
 
// juste pour le fun, j'affiche la liste
  for var I := 0 to Length(List) - 1 do
    ListBox1.Items.Add(List[I].ToString);
  ListBox1.ItemIndex := Found;
end;

@Charly910, merci pour la réponse.
Précision, je ne souhaite pas une solution qui soit "assez rapide" car toutes le seront
mais "la ou les plus rapides" éventuellement en fonction de la taille de la liste ?

Pour la StringList, pas fan quand on peut faire avec des nombres et que l'on recherche la rapidité.
Pour le moment, je partirai plutôt sur ce code, mais il y a peut être mieux ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 tab : array[0..300000]of boolean; c,j, L : integer; // part 1 for j:=1 to 300000 do tab[j]:=false; j := 1; while(true) do begin j := j + random(3000); if j > 300000 then break; tab[j] := true; end; ... // part 2 c := 0; for j:=1 to 1000000 do begin L := random(300000) +1; if tab[L] then inc(c); end;

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
  // Collection
  // part 1
  SetLength(List,  15000);  // taille non connue à l'avance
 
  k := 0;
  j := 1;
  while(true) do
  begin
    j := j + random(3000);
    if j > 300000 then break;
    //tab[j] := true;
    List[k] := j;
    inc(k);
  end;
 
  // part 2
  c := 0;
  for j:=1 to 1000000 do
  begin
    k := random(300000) +1;
    //if tab[k] then inc(c);
    if TArray.BinarySearch<Integer>(List, k, i) then inc(c);
  end;

Quelques mesures en ms :

- solution collection integer :
part 1= 0,2069
part 2= 69,5747

- solution array boolean :
part 1= 1,2932
part 2= 3,7374

26/03/2022, 12h36
Andnotor

Pourquoi faire systématiquement une recherche sur une liste fixe d'entiers ?

On génère simplement un tableau de 300'000 booléens et on travaille sur l'index (je ne comprends pas pourquoi sbadecoder c'est pris un :moinsser:).

Et pour limiter l'utilisation mémoire (même si 293k n'est pas impressionnant), passer par un TBits.

Utiliser une TStringList n'est pas adapté ici mais si on voulait vraiment utiliser ce principe, une THashedStringList serait bien plus rapide.

alors en effet, il y a plusieurs approches...le lookup dans un tableau est le plus rapide...

Code:

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
88
89
90
91
 
uses
  System.Generics.Collections,
  System.DateUtils;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  var List: TArray<Integer>;
  SetLength(List,  15000);
  for var I := 0 to Length(List) - 1 do
      List[I] := Random(300000) + 1;
 
  var bits : TArray<Cardinal>;
  SetLength(bits, 300000 div 32);
  for var I := 0 to Length(List) - 1 do
  begin
    var N := List[I] - 1;
    var O := N div 32;
    bits[O] := bits[O] or (1 shl (N mod 32));
  end;
 
  var bools: TArray<Boolean>;
  SetLength(bools, 300000);
  for var I := 0 to Length(List) - 1 do
  begin
    bools[List[I] - 1] := True;
  end;
 
  var N := List[0];
 
  TArray.Sort<Integer>(List);
 
  var Found: Integer;
  if TArray.BinarySearch<Integer>(List, 12, Found) then
    ShowMessage('12 est à l''index ' + Found.ToString)
  else
    ShowMessage('12 n''est pas dans la liste');
 
  if TArray.BinarySearch<Integer>(List, N, Found) then
    ShowMessage(N.ToString + ' est à l''index ' + Found.ToString)
  else
    ShowMessage('ça c''est pas normal !');
 
  // vérification
  for var I := 0 to 300000 - 1 do
  begin
    var O := I div 32;
    var B := bits[O] and (1 shl (I mod 32));
    if ((B <> 0) <> TArray.BinarySearch<Integer>(List, I + 1, Found))
    or ((B <> 0) <> bools[I]) then
      raise Exception.Create('Erreur !');
  end;
 
//  for var I := 0 to Length(List) - 1 do
//    ListBox1.Items.Add(List[I].ToString);
//  ListBox1.ItemIndex := Found;
 
  // test1
  var T1 := Now;
  var Count := 0;
  for var I := 1 to 300000 do
  begin
    if TArray.BinarySearch<Integer>(List, I, Found) then
      Inc(Count);
  end;
  var T2 := Now;
  ListBox1.Items.Add('TArray.BinarySearch = ' + Count.ToString + ' in ' + MillisecondsBetween(T1, T2).ToString + 'ms');
 
  // test2
  T1 := Now;
  Count := 0;
  for var I := 0 to 300000 - 1 do
  begin
    if bits[I div 32] and (1 shl (I mod 32)) <> 0 then
      Inc(Count);
  end;
  T2 := Now;
  ListBox1.Items.Add('bits[] = ' + Count.ToString + ' in ' + MillisecondsBetween(T1, T2).ToString + 'ms');
 
  // test3
  T1 := Now;
  Count := 0;
  for var I := 0 to 300000 - 1 do
  begin
    if bools[I] then
      Inc(Count);
  end;
  T2 := Now;
  ListBox1.Items.Add('bools[] = ' + Count.ToString + ' in ' + MillisecondsBetween(T1, T2).ToString + 'ms');
 
end;

14ms pour le TArray.BinarySearch
0ms pour bits[]
et 1ms pour bools[]

j'ai testé avec 150000 entrées et ça donne 20, 1 et 2 ms

même avec 10 entrées, 5, 0 et 1 ms :)

et je ne compte pas le temps d'initialisation

26/03/2022, 13h46
sbadecoder

avec un array of boolean:
part 2= 3,73 ms par boucle (mesuré sur 10000 itérations).

avec un TBits:
part 2= 3,92 ms par boucle (mesuré sur 10000 mêmes itérations), ce qui peut en effet être un bon compromis mémoire/vitesse.

J'avais testé directement avec un TBits dans mon test précédent.
Ci-dessous le code modifié selon ma procédure de test.
Je vais tester tout ça...

Code:

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
 
  // test1
  var T1 := Now;
  var Count := 0;
  for z:=1 to 100 // 100 itérations
  for var I := 1 to 1000000 do
  begin
    L := random(300000) +1;
    if TArray.BinarySearch<Integer>(List, L, Found) then
      Inc(Count);
  end;
  var T2 := Now;
  ListBox1.Items.Add('TArray.BinarySearch = ' + Count.ToString + ' in ' + MillisecondsBetween(T1, T2).ToString + 'ms');
 
  // test2
  T1 := Now;
  Count := 0;
  for z:=1 to 100 // 100 itérations
  for var I := 1 to 1000000 do
  begin
    L := random(300000);
    if bits[L div 32] and (1 shl (L mod 32)) <> 0 then
      Inc(Count);
  end;
  T2 := Now;
  ListBox1.Items.Add('bits[] = ' + Count.ToString + ' in ' + MillisecondsBetween(T1, T2).ToString + 'ms');
 
  // test3
  T1 := Now;
  Count := 0;
  for z:=1 to 100 // 100 itérations
  for var I := 1 to 1000000 do
  begin
    L := random(300000);
    if bools[L] then
      Inc(Count);
  end;
  T2 := Now;
  ListBox1.Items.Add('bools[] = ' + Count.ToString + ' in ' + MillisecondsBetween(T1, T2).ToString + 'ms');

26/03/2022, 15h09
sbadecoder

Après quelques essais avec boucle de 1 million de tests et 10000 itérations (identiques pour chaque algorithme):

Array of boolean, part 2= 3,3917 ms par boucle
Collection of boolean (bools), part 2= 3,4282 ms
Collection of cardinal (bits), part 2= 3,4839 ms
TBits, part 2= 3,8497 ms

note qu'avec des temps de réponse aussi bas, Now() n'est pas suffisant, il faut passer par QueryPerformanceCounter
Code:

1 2 3 4 5 6 7 8 9 10 11 12 begin QueryPerformanceFrequency(F); ... QueryPerformanceCounter(N); Time1 := N / F; .. QueryPerformanceCounter(N); Time2 := N / F; end;

27/03/2022, 00h20
sbadecoder

C'est ce que j'utilise en effet.
Les valeurs ci-dessous sont divisées par le nombre d'itérations donc calculées en réalité selon env. 34 sec.