Dichotomie

[Résolu]
Signaler
Messages postés
23
Date d'inscription
vendredi 3 janvier 2003
Statut
Membre
Dernière intervention
27 juin 2011
-
 Utilisateur anonyme -
j'ai un probleme dans une application que je réalise je me souviens plus comment marche une recherche par dichotomie

j'ai un tlistview sur une fiche avec un indice a 0 et un indice maximum (le nombre d'items dans la liste) et je verifie si un item est deja dans la liste avant d'en inserer un autre si il n'existe pas je l'insere si il existe  je l'insere.

comme j'ai beaucoup d'enregistrement il n'y a que la recherche par dichotomie qui puisse m'aider.

Au Secour !!!!

exemple de la fonction

fonction getindexofuser(username:string):integer;
var min,max,milieu:integer;
begin
max:=0;
min:=0;
milieu:=0;
if username='' then exit;
while (username<>listview1.items(milieu).caption) and (min<max) do begin
milieu:=min+max div 2;
end;
... me souviens plus là ...
if username=listview1.items(milieu).caption then result:=milieu else result:=-1; 
end;

si vous avez une idée merci !!!!!

15 réponses

Messages postés
4297
Date d'inscription
samedi 19 janvier 2002
Statut
Modérateur
Dernière intervention
9 janvier 2013
31
Oups !!!! Achtung !!!!
Y a un gros bug.
Voici la bonne formule et complète en prime :
<hr />
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, ComCtrls, StdCtrls;

type
  TViewProc =   procedure (Iter, LowIndex, HighIndex: integer) ofobject;

  TForm1  = class(TForm)
    ListView1: TListView;
    Edit1: TEdit;
    btnSearch: TButton;
    Label1: TLabel;
    Memo1: TMemo;
    procedure btnSearchClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    function GetIndexOfUser(lv: TListView; username: string; LowIndex,
      HighIndex: integer; var nbIter: integer; ViewProc: TViewProc =   nil ): integer;
    procedure InitListView;
    procedure DummyProc(Iter, LowIndex, HighIndex: integer);
    procedure ViewDetails(Iter, LowIndex, HighIndex: integer);
    { Déclarations privées }
  public
    { Déclarations publiques }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}
const
  //nombre de positions d'affichage
  nbDigits  = 5;
  //nombre de valeurs différents dans la liste
  nbValues =  5000;

var
  //Chaine pour le formatage des nombres
  fmtstr:  string ;

procedure TForm1.InitListView();
var
  i: integer;
  li: TListItem;  
begin
  ListView1.Items.BeginUpdate;
  for i : = 0to nbValues do
  begin
    li :=  ListView1.Items.Add;
    li.Caption := Format(fmtStr, [i]);
   end ;
  ListView1.Items.EndUpdate;
end;

function TForm1.GetIndexOfUser(lv: TListView; UserName: string; LowIndex,
  HighIndex: integer; var nbIter: integer; ViewProc: TViewProc  = nil): integer;
var
  Mediane: integer;
  SwapIndex: integer;
begin
  Result :=  -1;
  
   if  LowIndex > HighIndex then
  begin
    SwapIndex : = LowIndex;
    LowIndex :=  HighIndex;
    HighIndex := SwapIndex;
   end ;

  inc(NbIter);

  Mediane : = (LowIndex + HighIndex) div2;

  if Assigned(ViewProc) then
    ViewProc(NbIter, LowIndex, HighIndex)
  else
    ViewProc :=  DummyProc;

  //On commence par regarder si l'élément médian correspond
   if  lv.Items[Mediane].Caption  = UserName then
    Result :=  Mediane
  else
     if  LowIndex  = HighIndex then
      //pas de solution !
      Exit
    else
      if (lv.Items[Mediane].Caption > Username) then
      begin
          //recherche dans la moitié inférieure de la liste
          dec(Mediane);
          Result :=  GetIndexOfUser(lv, UserName, LowIndex, Mediane, NbIter, ViewProc);
      end
      else
         if  (lv.Items[Mediane].Caption < UserName) then
        begin
          inc(Mediane);
          //Recherche dans la moitié supérieure de la liste
          Result : = GetIndexOfUser(lv, UserName, Mediane, HighIndex, NbIter, ViewProc);
        end;
end;

procedure TForm1.btnSearchClick(Sender: TObject);
var
  NbIter: integer;
  T1, T2: TTime;
  Value: integer;

begin
  {Pour que la recherche dichotomique puisse fonctionner,
  les données doivent être triées avant de procéder}
  NbIter :=  0;
  Memo1.Clear;
  Value := StrToIntDef(Edit1.Text, 0);
  Edit1.Text := Format(fmtStr, [Value]);
  
  T1 := Time;
  //Exemple de sélection de l'élément recherché s'il est trouvé
  ListView1.ItemIndex := GetIndexOfUser(ListView1, Edit1.Text, 0,
    ListView1.Items.Count - 1, NbIter, ViewDetails);

  T2 := Time;

   if  ListView1.ItemIndex > -1then
    Label1.Caption : = 'Trouvé avec '
      + IntToStr(NbIter) + ' itérations en '
      + FormatDateTime('hh:nn:ss.zzz' , T2-T1)
      + ' pour ' + IntToStr(ListView1.Items.Count) + ' éléments'
  else
    Label1.Caption :=  'Non trouvé au bout de ' + IntToStr(NbIter) + ' itérations'
 end ;

procedure TForm1.FormCreate(Sender: TObject);
begin
  fmtStr : = '%.' + IntToStr(nbDigits) + 'd';
  ListView1.Clear;
  InitListView;
end;

procedure TForm1.ViewDetails(Iter, LowIndex, HighIndex: integer);
begin  Memo1.Lines.Append(Format('Itération : %.5d, Low %.6d, High %.6d', [Iter, LowIndex, HighIndex]));
 end ;

procedure TForm1.DummyProc(Iter, LowIndex, HighIndex: integer);
begin
//ne fait rien mais le fait bien :o)
end;

end.
<hr />Voilà, j'espère que tu sauras faire le distingo car pour alimenter le TListView avec des valeurs entières, j'ai dû ajouter des zéros devant chaque nombre. 

Pour 5000 nombres, on trouve en un maximum de 13 itérations.

Avec mes excuses pour le bug non vu au départ

May Delphi be with you !
<hr color ="#008000" />
Pensez à cliquer sur Réponse acceptée lorsque la réponse vous convient.
http://www.afipa.net/
Messages postés
4297
Date d'inscription
samedi 19 janvier 2002
Statut
Modérateur
Dernière intervention
9 janvier 2013
31
Je repose ici la question de Aroslide qu'il m'a envoyée par MP :
bonsoir voila ce que je veux faire en realité ....
lorsque un utilisateur rentre sur mon serveur , celui ci doit tester si le nom est deja pris ou non

par cette fontion qui me renvoit un indice -1 si le pseudo n'est pas pris et autre chose si le pseudo est pris pourquoi la dichotomie ? parceque c 'est la metode la plus rapide pour recuperer les informations des utilisateurs et modifier les informations de ceux ci. c'est pour ça que j'en ai besoin ....
je precise que ma listview est automatiquement triee.

function tmain.getindexofuser(username : string): longint;
var milieu,min,max:longint;
    trouve:boolean;
begin
//result:= -1;
frame21.ListView1.SortType:=sttext;
trouve:=false;
min:=0;
max:=frame21.ListView1.Items.count-1;
milieu:=0;
try
milieu:=(max+min) div 2;
except
result:=-1;
end;
while ((max>min) and (trouve<>true))  do
begin
try
milieu:=(max+min) div 2;
except
result:=-1;
end;

if  username=(frame21.ListView1.items[milieu].caption ) then trouve:=true
  else

if  (frame21.ListView1.items[milieu].caption)>username then
begin
max:=(milieu)-1;
trouve:=false;
end else
if  (frame21.ListView1.items[milieu].caption)
Voici la solution que je lui donne (pas de récursivité) :

<code> function  TMain.GetIndexOfUser(lv: TListView; const UserName: string): integer;
var
  milieu, min, max: longint;
  trouve: boolean;
begin
  result : = -1;
  trouve :=  false;

  min := 0;
  max := lv.Items.count - 1;

   while  (max > = min) andnot trouve do
  begin
    milieu :=  (max + min)  div 2;
    if username  = (lv.items[milieu].caption) then
    begin
      trouve :=  true;
      Result := Milieu;
    end
    else
       if  (lv.items[milieu].caption) > username then
        max : = milieu - 1
      else
        if (lv.items[milieu].caption) < username then
          min :=  milieu + 1;
   end ;
  //   tsyncclass.update('indice de l''utilisateur : ' + username + ' : ' +
  //     inttostr(result));
end;

procedure TMain.Button1Click(Sender: TObject);
begin
  with ListView1 do
  begin
    SortType : = stText;
    ItemIndex :=  GetIndexOfUser(ListView1, Edit1.Text);
   end ;
end;

Comme on peut le constater, le code a subi une cure d'amaigrissement ! Mais au moins, il fonctionne.
</code>En prime, si tu dois rechercher dans plusieurs TListView, le code sera réutilisable.

May Delphi be with you !
<hr color ="#008000" />
Pensez à cliquer sur Réponse acceptée lorsque la réponse vous convient.
http://www.afipa.net/
Messages postés
4297
Date d'inscription
samedi 19 janvier 2002
Statut
Modérateur
Dernière intervention
9 janvier 2013
31
Tiens, voici une formule améliorée qui ne tient pas compte de la casse :

function TMain.GetIndexOfUser(lv: TListView; const UserName: string): integer;
var
  milieu, min, max: longint;
  trouve: boolean;
  Compare: integer;
begin
  result :=  -1;
  trouve := false;

  min := 0;
  max := lv.Items.count - 1;

   while  (max > = min) andnot trouve do
  begin
    milieu :=  (max + min)  div  2;
    Compare : = CompareText(lv.items[milieu].caption, UserName);
    if Compare =  0then
    begin
      trouve := true;
      Result := Milieu;
    end
    else
       if  Compare > 0then
        max : = milieu - 1
      else
        min :=  milieu + 1;
   end ;
  //   tsyncclass.update('indice de l''utilisateur : ' + username + ' : ' +
  //     inttostr(result));
end;

Quelqu'un a-t-il une solution plus concise à proposer ?

May Delphi be with you !
<hr color ="#008000" />
Pensez à cliquer sur Réponse acceptée lorsque la réponse vous convient.
http://www.afipa.net/

Un petit bonjour aurait été le bienvenu et une recherche préliminaire avant de poster aussi.

Méthode de la dichotomie : http://fr.wikipedia.org/wiki/Dichotomie
Messages postés
3826
Date d'inscription
vendredi 23 juillet 2004
Statut
Modérateur
Dernière intervention
10 mai 2021
46
j'ai oublié ...surtout n'oublis pas de regarder les commentaires
et d'en tirer les conclusions

 
@+
Cirec

<hr size="2" />
Messages postés
23
Date d'inscription
vendredi 3 janvier 2003
Statut
Membre
Dernière intervention
27 juin 2011

a oui j'ai oublié de bonjour !! xcusez

j'ai regardé l'exemple mais ça correspond pas tout a fait à ce que je recherche .... y avait une histoire de borne inferieur et borne superieur avec un pivot .... j'ai vu ça en premiere année de bts mais impossible de remettre la main sur la methode exacte
Messages postés
1725
Date d'inscription
vendredi 27 décembre 2002
Statut
Modérateur
Dernière intervention
11 avril 2021
8
Tu avais oublié de dire bonjour... et tu nous réveilles pour ça ?


Mais t'as vu l'heure ?

Heu ca ne serait pas un certain Japee qui a jour nous a révéillé pour dire qu'il était 01:02:03 hein ?? 
Messages postés
23
Date d'inscription
vendredi 3 janvier 2003
Statut
Membre
Dernière intervention
27 juin 2011

mouaip je demande un coup de main .... et voila ....

ma question portée sur un listview contenant des caracteres contenant des nickname d'utilisateurs.

je veux trouver l'index de l'utilisateur en utilisant la methode de recherche dichotomique avec une fontion du type

getindexofuser(username:string):integer; afin d'eviter de rajouter un doublon dans ma liste d'utilisateurs.

si je demande de l'aide c'est que j'ai un probleme de comprehension sur ce sujet.
 
merci pour tout

Salut,

Je trouve ca gentil de la part de Nicolas d'avoir pris du temps à lui poui faire un source non ?

Sinon tu n'as  pas besoin de faire appel à de la dichotomie pour faire ce que tu recherches ListBox1.Items.IndexOf('Mon String')
Messages postés
4297
Date d'inscription
samedi 19 janvier 2002
Statut
Modérateur
Dernière intervention
9 janvier 2013
31
Bon, on va s'y coller.
Je ne vais pas expliquer la recherche dichotomique, pour cela je te renvoie au lien donné par francky23012301.

Voici le code (suffisamment explicité à mon goût) :

function TForm1.GetIndexOfUser(lv: TListView; UserName:string; LowIndex, HighIndex: integer):integer;
var
  Mediane: integer;
begin
  Mediane :=  (LowIndex + HighIndex)  div  2;

  //On commence par regarder si l'élément médian correspond
  if lv.Items[Mediane].Caption  = UserName then
    Result :=  Mediane
  else
     if  lv.Items[mediane].Caption > Username then
    begin
      //recherche dans la moitié inférieure de la liste
      Result : = GetIndexOfUser(lv, UserName, LowIndex, Mediane div2);
    end
    else
      if lv.Items[Mediane].Caption < UserName then
        //Recherche dans la moitié supérieure de la liste
        Result :=  GetIndexOfUser(lv, UserName, Mediane, HighIndex)
      else
        //Valeur inexistante !
        Result := -1;
 end ;

et voici l'utilisation :

procedure TForm1.btnSearchClick(Sender: TObject);
begin
  {Pour qu ela recherche dichotomique puisse fonctionner,
  les données doivent être triées avant de procéder}
  ListView1.SortType : = stText;
  //Exemple de sélection de l'élément recherché s'il est trouvé
  ListView1.ItemIndex :=  GetIndexOfUser(ListView1, Edit1.Text, 0, ListView1.Items.Count);
 end ;

En espérant qu'avec ça tu t'en sortiras.
Comme la méthode GetIndexOfUser est récursive, fais gaffe si tu as des milliers de lignes dans ton TListView.




Dernier conseil
: si tu ne retrouves plus comment implémenter un algorithme, prends un feuille de papier et un crayon puis écris en langage naturel cet algorithme.
On réfléchis souvent bien mieux loin d'un clavier d'ordinateur...

May Delphi be with you !


<hr color ="#008000" />
Pensez à cliquer sur Réponse acceptée lorsque la réponse vous convient.
http://www.afipa.net/
Messages postés
23
Date d'inscription
vendredi 3 janvier 2003
Statut
Membre
Dernière intervention
27 juin 2011

Ben voila !!! tout va pour le mieux dans le meilleur des mondes !!!! Merci à Delphiprog et à toute l'equipe

Salut,

Oui Philippe il ya plus simple : le composant indy TIdUserManager qui est fait spécialement pour çà.
Messages postés
4297
Date d'inscription
samedi 19 janvier 2002
Statut
Modérateur
Dernière intervention
9 janvier 2013
31
Dear Francky,

Mais quel est alors le rapport avec un TListView ?
De plus, inclure toutes les librairies Indy juste pour rechercher un nom dans une liste, ça ne va pas alourdir démesurément l'exécutable pour peu de choses en définitive ?

May Delphi be with you !
<hr color="#008000" />
Pensez à cliquer sur Réponse acceptée lorsque la réponse vous convient.
http://www.afipa.net/

Dear Delphiprog

If you add 5000 users, it will better to use a SGBD like Paradox that a ListView, isn't it ? If i understand all, this man realize a server, isn' it ? Maybe, and it will better in reality, he's using Indy's components to do it. If it's the case, it's not stupid to add a little new component (i speak of IdUserManager) to control Users/Passwords ( it's better to use a password too : chutt it's a secret ).

This author speak just of the seek's function, the accepting'part is not present. With this component in six lines you have all : seek and accept.

Is it not beautiful, the life ?

@+