Dichotomie [Résolu]

aroslide 24 Messages postés vendredi 3 janvier 2003Date d'inscription 27 juin 2011 Dernière intervention - 2 mars 2007 à 23:34 - Dernière réponse :  Utilisateur anonyme
- 4 mars 2007 à 12:05
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 !!!!!
Afficher la suite 

Votre réponse

17 réponses

Meilleure réponse
cs_Delphiprog 4580 Messages postés samedi 19 janvier 2002Date d'inscription 9 janvier 2013 Dernière intervention - 3 mars 2007 à 18:02
3
Merci
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/

Merci cs_Delphiprog 3

codes-sources a aidé 87955 internautes ce mois-ci

Commenter la réponse de cs_Delphiprog
Meilleure réponse
cs_Delphiprog 4580 Messages postés samedi 19 janvier 2002Date d'inscription 9 janvier 2013 Dernière intervention - 4 mars 2007 à 10:01
3
Merci
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/

Merci cs_Delphiprog 3

codes-sources a aidé 87955 internautes ce mois-ci

Commenter la réponse de cs_Delphiprog
Meilleure réponse
cs_Delphiprog 4580 Messages postés samedi 19 janvier 2002Date d'inscription 9 janvier 2013 Dernière intervention - 4 mars 2007 à 11:04
3
Merci
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/

Merci cs_Delphiprog 3

codes-sources a aidé 87955 internautes ce mois-ci

Commenter la réponse de cs_Delphiprog
Utilisateur anonyme - 3 mars 2007 à 00:07
0
Merci
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
Commenter la réponse de Utilisateur anonyme
Cirec 4221 Messages postés vendredi 23 juillet 2004Date d'inscription 11 mai 2018 Dernière intervention - 3 mars 2007 à 00:52
0
Merci
Salut,

Alors là vraiment ... tu ne peux par dire que tu as chercher
en 1 seconde je trouve ceci sur DelphiFr :
ELIMINATION DES DOUBLONS DANS LES TSTRINGS ET LES LISTBOX PAR DICHOTOMIE

 
@+
Cirec

<hr size="2" />
Commenter la réponse de Cirec
Cirec 4221 Messages postés vendredi 23 juillet 2004Date d'inscription 11 mai 2018 Dernière intervention - 3 mars 2007 à 00:56
0
Merci
j'ai oublié ...surtout n'oublis pas de regarder les commentaires
et d'en tirer les conclusions

 
@+
Cirec

<hr size="2" />
Commenter la réponse de Cirec
aroslide 24 Messages postés vendredi 3 janvier 2003Date d'inscription 27 juin 2011 Dernière intervention - 3 mars 2007 à 01:24
0
Merci
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
Commenter la réponse de aroslide
japee 1792 Messages postés vendredi 27 décembre 2002Date d'inscription 12 novembre 2016 Dernière intervention - 3 mars 2007 à 01:39
0
Merci
Tu avais oublié de dire bonjour... et tu nous réveilles pour ça ?


Mais t'as vu l'heure ?
Commenter la réponse de japee
Utilisateur anonyme - 3 mars 2007 à 01:46
0
Merci
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 ?? 
Commenter la réponse de Utilisateur anonyme
Nicolas___ 1039 Messages postés jeudi 2 novembre 2000Date d'inscription 24 avril 2013 Dernière intervention - 3 mars 2007 à 12:10
0
Merci
Salut aroslide , bon j'ai pensé a toi et tt ceux qui ne comprenne pas trop la recherche dichotomique ...
http://www.delphifr.com/code.aspx?ID=41721
En esperant que tu comprene cette fois !

Ciao
Commenter la réponse de Nicolas___
aroslide 24 Messages postés vendredi 3 janvier 2003Date d'inscription 27 juin 2011 Dernière intervention - 3 mars 2007 à 13:16
0
Merci
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
Commenter la réponse de aroslide
Utilisateur anonyme - 3 mars 2007 à 14:42
0
Merci
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')
Commenter la réponse de Utilisateur anonyme
cs_Delphiprog 4580 Messages postés samedi 19 janvier 2002Date d'inscription 9 janvier 2013 Dernière intervention - 3 mars 2007 à 15:40
0
Merci
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/
Commenter la réponse de cs_Delphiprog
aroslide 24 Messages postés vendredi 3 janvier 2003Date d'inscription 27 juin 2011 Dernière intervention - 3 mars 2007 à 17:16
0
Merci
Ben voila !!! tout va pour le mieux dans le meilleur des mondes !!!! Merci à Delphiprog et à toute l'equipe
Commenter la réponse de aroslide
Utilisateur anonyme - 4 mars 2007 à 11:27
0
Merci
Salut,

Oui Philippe il ya plus simple : le composant indy TIdUserManager qui est fait spécialement pour çà.
Commenter la réponse de Utilisateur anonyme
cs_Delphiprog 4580 Messages postés samedi 19 janvier 2002Date d'inscription 9 janvier 2013 Dernière intervention - 4 mars 2007 à 11:37
0
Merci
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/
Commenter la réponse de cs_Delphiprog
Utilisateur anonyme - 4 mars 2007 à 12:05
0
Merci
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 ?

@+
Commenter la réponse de Utilisateur anonyme

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.