IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Delphi Discussion :

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


Sujet :

Langage Delphi

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    149
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 149
    Points : 65
    Points
    65
    Par défaut 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.
    Une belle fonction contient au plus 7 lignes de code,
    Une belle procédure appelle au plus 7 fonctions,
    Un beau programme est lisible et compréhensible,
    Dans tous les autres cas, une optimisation s'impose.

  2. #2
    Membre expert
    Avatar de Charly910
    Homme Profil pro
    Ingénieur TP
    Inscrit en
    Décembre 2006
    Messages
    2 339
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur TP
    Secteur : Bâtiment Travaux Publics

    Informations forums :
    Inscription : Décembre 2006
    Messages : 2 339
    Points : 3 107
    Points
    3 107
    Par défaut
    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

  3. #3
    Rédacteur/Modérateur

    Avatar de SergioMaster
    Homme Profil pro
    Développeur informatique retraité
    Inscrit en
    Janvier 2007
    Messages
    15 021
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 67
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur informatique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Janvier 2007
    Messages : 15 021
    Points : 40 935
    Points
    40 935
    Billets dans le blog
    62
    Par défaut
    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 : 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
     
    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é
    MVP Embarcadero
    Delphi installés : D3,D7,D2010,XE4,XE7,D10 (Rio, Sidney), D11 (Alexandria), D12 (Athènes)
    SGBD : Firebird 2.5, 3, SQLite
    générateurs États : FastReport, Rave, QuickReport
    OS : Window Vista, Windows 10, Windows 11, Ubuntu, Androïd

  4. #4
    Expert éminent sénior
    Avatar de Paul TOTH
    Homme Profil pro
    Freelance
    Inscrit en
    Novembre 2002
    Messages
    8 964
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Freelance
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2002
    Messages : 8 964
    Points : 28 430
    Points
    28 430
    Par défaut
    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 : 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
     
    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;
    Developpez.com: Mes articles, forum FlashPascal
    Entreprise: Execute SARL
    Le Store Excute Store

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    149
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 149
    Points : 65
    Points
    65
    Par défaut
    @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 : 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
     
    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;
    Une belle fonction contient au plus 7 lignes de code,
    Une belle procédure appelle au plus 7 fonctions,
    Un beau programme est lisible et compréhensible,
    Dans tous les autres cas, une optimisation s'impose.

  6. #6
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    149
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 149
    Points : 65
    Points
    65
    Par défaut
    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
     
      // 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
    Une belle fonction contient au plus 7 lignes de code,
    Une belle procédure appelle au plus 7 fonctions,
    Un beau programme est lisible et compréhensible,
    Dans tous les autres cas, une optimisation s'impose.

  7. #7
    Rédacteur/Modérateur
    Avatar de Andnotor
    Inscrit en
    Septembre 2008
    Messages
    5 671
    Détails du profil
    Informations personnelles :
    Localisation : Autre

    Informations forums :
    Inscription : Septembre 2008
    Messages : 5 671
    Points : 13 065
    Points
    13 065
    Par défaut
    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 ).

    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.

  8. #8
    Expert éminent sénior
    Avatar de Paul TOTH
    Homme Profil pro
    Freelance
    Inscrit en
    Novembre 2002
    Messages
    8 964
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Freelance
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2002
    Messages : 8 964
    Points : 28 430
    Points
    28 430
    Par défaut
    alors en effet, il y a plusieurs approches...le lookup dans un tableau est le plus rapide...

    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
    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
    Developpez.com: Mes articles, forum FlashPascal
    Entreprise: Execute SARL
    Le Store Excute Store

  9. #9
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    149
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 149
    Points : 65
    Points
    65
    Par défaut
    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.
    Une belle fonction contient au plus 7 lignes de code,
    Une belle procédure appelle au plus 7 fonctions,
    Un beau programme est lisible et compréhensible,
    Dans tous les autres cas, une optimisation s'impose.

  10. #10
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    149
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 149
    Points : 65
    Points
    65
    Par défaut
    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 : 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
     
      // 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');
    Une belle fonction contient au plus 7 lignes de code,
    Une belle procédure appelle au plus 7 fonctions,
    Un beau programme est lisible et compréhensible,
    Dans tous les autres cas, une optimisation s'impose.

  11. #11
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    149
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 149
    Points : 65
    Points
    65
    Par défaut
    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
    Une belle fonction contient au plus 7 lignes de code,
    Une belle procédure appelle au plus 7 fonctions,
    Un beau programme est lisible et compréhensible,
    Dans tous les autres cas, une optimisation s'impose.

  12. #12
    Expert éminent sénior
    Avatar de Paul TOTH
    Homme Profil pro
    Freelance
    Inscrit en
    Novembre 2002
    Messages
    8 964
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Freelance
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2002
    Messages : 8 964
    Points : 28 430
    Points
    28 430
    Par défaut
    note qu'avec des temps de réponse aussi bas, Now() n'est pas suffisant, il faut passer par QueryPerformanceCounter

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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;
    Developpez.com: Mes articles, forum FlashPascal
    Entreprise: Execute SARL
    Le Store Excute Store

  13. #13
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    149
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 149
    Points : 65
    Points
    65
    Par défaut
    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.
    Une belle fonction contient au plus 7 lignes de code,
    Une belle procédure appelle au plus 7 fonctions,
    Un beau programme est lisible et compréhensible,
    Dans tous les autres cas, une optimisation s'impose.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 2
    Dernier message: 09/02/2017, 11h01
  2. Réponses: 0
    Dernier message: 30/03/2011, 16h11
  3. Réponses: 4
    Dernier message: 24/03/2005, 20h20
  4. [TreeView] Test de la présence ou non d'un noeud
    Par TheDarkLewis dans le forum Composants VCL
    Réponses: 2
    Dernier message: 24/07/2004, 04h20
  5. Comment optimiser une jointure ?
    Par seb_asm dans le forum Administration
    Réponses: 21
    Dernier message: 25/06/2004, 17h42

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo