Tester si une valeur est dans tableauRésolu

Question

Bonjour à tous,

J'ai un tableau d'entiers (dynamique ou statique)
et je voudrais tester si une valeur est comprise dans mon tableau
sans passer par une boucle.
j'aimerais bien un truc comme if Numb in [ qlqchose  ] then..

est-ce possible ?

merci par avance

cantador

JulioDelphi · Accepted Answer

Moi je veux idem que cantador mais avec des chars :]
S := 'Q';
if S in ['A'..'Z'] then showmessage('ok');

Caribensila · Answer

Salut Cantador,

J'ai une proposition assez performante avec MatchesMask().
Mais il te faudra écrire ton tableau sous forme de chaîne.

1 exemple :
procedure TForm1.Button1Click(Sender: TObject);
  var   Tablo : String;
begin
  Tablo := '12,34,56,78,90,100';
  if MatchesMask(Tablo,'*90*') then ShowMessage('90 est ds la chaîne') else ShowMessage('90 n''est pas ds la chaîne');
  if MatchesMask(Tablo,'*95*') then ShowMessage('95 est ds la chaîne') else ShowMessage('95 n''est pas ds la chaîne');
end;

Francky23012301 · Answer

Salut,

Pour rechercher une valeur dans un tableau tu n'as pas d'autres choix que de le parcourir. Après il existe des fonctions/expressions ou tu n'écris par de boucle mais en réalité il y en a quand meme une qui a lieu :

1)La méthode de Julio ne fait pas intervenir de boucle dans son écriture mais la recherche induite en fait inévitablement appel.

2)La méthode de Cari aussi : elle utilise la dichotomie ce qui induit une recherche plus rapide. Mais il y a quand meme une boucle en interne.

Désolé Cantador mais cela me semble impossible : c'est comme chercher une clé dans 25 vases. La seule facon de savoir quel vase contient la clé est de tous les parcourir jusqu'a la recherche du trophée.

Je te conseil la méthode de Cari car elle est beaucoup plus rapide qu'une boucle classique ou la technique proposée par Julio. Cependant tu dois utiliser des strings (Sachant qu'un transtypage pour chaque valeur va faire chuter les performances de facon vertigineuse)

florenth · Answer

Salut !

La technique utilisée par Julio ne fait pas appel à des boucles, mais elle est limitée à des types de 8 bits (Byte ou Char).
De plus, si tu fais "if S in ['A', 'C', 'F'..'I', 'O', 'Q', 'X'..'Z'] then", tu perds pas mal en perfs.
Cependant, ça reste quand même le plus rapide.

La méthode de Cari me semble la plus lente si le test est à effectuer avec des Integer.
Dans le cas de nombres, le mieux reste :
- de les trier une fois pour toutes (voir ma source sur QuickSort pour pas s'embêter avec le tri)
- d'utiliser ensuite une méthode dichotomique pour rechercher si le nombre est dans la liste ou pas.

Mais cette technique a aussi un désavantage si tu modifies souvent ton tableau.

En fait, tout dépend de tes structures de données !
Tu peux aussi utiliser un arbre (binaire ou non) si l'occasion s'y prête. Tu auras alors les coûts de ré-alignements mais suivant ce que tu fais, c'est plus rapide.

cs_cantador · Answer

Merci à tous les trois 
C'est vraiment sympa..
Je croyais qu'il existait du "prêt à cuire"..
Tant pis..

En fait, c'est de ma faute j'aurais du préciser que je souhaitais faire ce test de manière répétitive..

J'ai donc codé une petite fonction et voilà ce que çà donne :

procedure TForm1.cxButton8Click(Sender: TObject);
var
i, adf: integer;
TSelectF : array of integer;
TabATester : array[1..100] of integer;
 
 function Numela(param: integer; var TAB: array of integer): boolean;
  var
    i: integer;
  begin
    Result := false;
    for i := 0 to high(TAB) do
      if param = TAB[i] then
        Result := true;
  end;
begin

adf := 0;
 Initialize(TSelectF );
 SetLength(TSelectF , 100);

        for i := 0 to high(TabATester ) do
          if not Numela(TabATester [i], TSelectF ) then
          begin
            TSelectF [adf] := TabATester [i];
            inc(adf);
          end;
 SetLength(TSELECTF, adf);

// etc etc etc..
end;

Si vous avez mieux..

cantador

JulioDelphi · Answer

Quelle taille fait le tableau ? Est il si grand pour ne pas vouloir faire une boucle dessus ?

Francky23012301 · Answer

Salut

1)Je quote le code de Julio :

S := 'Q';
if S in ['A'..'Z'] then showmessage('ok');

Si je lis mot à mot ce code
S correspond à 'Q'
Si S est dans le tableau ['A'..'Z'] alors

Soit il y a pas de boucles d'écrits (Comme je le disais), Mais Flo va falloir m'expliquer comment ca fonctionne, s'il y a pas une boucle qui a lieu au niveau du ['A'..'Z'] d'une facon ou d'une autre (Par exemple elle pourrait apparaitre lors de la transformation du code en ASM).

2)"La méthode de Cari me semble la plus lente si le test est à effectuer avec des Integer".  D'accord mais là on parle de chaines caractères. Une fois trouvée non pas l'integer mais la chaine voulue, on transtype. Dans ces conditions la méthode de Julio risque d'etre lente comparée à celle de Cari dans ces conditions, en particulier si la taille du tableau est importante non ? 

Je sens que cela va se terminer par un test de perfs

JulioDelphi · Answer

Nan mais j'ai fait dériver le sujet là :p
A la base on parle bien d'un tableau d'entier ^^ Moi j'ai mis mon grain de sel avec ça XD

Caribensila · Answer

... Question perfs, je ne sais pas encore   

Mais l'utilisation d'un ensemble présente au moins deux inconvénients, à mon avis :
- le type de base ne peut avoir plus de 256 valeurs
- une même valeur ne peut pas apparaître deux fois.

Francky23012301 · Answer

C'est pas toi le coupable Julio, C'est Cari 

Mais la double question m'interesse :
1)Flo affirme que ca fonctionne sans boucle meme au niveau du code compilé. Mon coté rationnel titille ma curiosité : comment on peut chercher sur le planc conceptuel une valeur dans un tableau sans parcourir d'une facon ou d'une autre ce dernier .
2)Si si on va faire des tests de perfs . Je vais me chercher des clopes et je me penche sur le sujet.

Caribensila · Answer

« sans parcourir d'une facon ou d'une autre ce dernier »

Ce qui est sûr, c'est que si la valeur cherchée s'y trouve, ça ira plus vite.

Surtout si elle est en 1ère position.   lol

JulioDelphi · Answer

Peut etre Delphi compare une valeur hexa de mon caractère Q (valant 51) qui est donc compris entre 41 (le A) et 5A (le Z) ?

Cirec · Answer

Juste pour info : ['A'..'Z'] n'est pas un tableau mais un ensemble Extrait de l'aide de Delphi: Constructeurs d'ensembles Un constructeur d'ensemble désigne une valeur de type ensemble. Par exemple,[5, 6, 7, 8] désigne l'ensemble dont les membres sont 5, 6, 7 et 8. Le constructeur d'ensemble :[ 5..8 ] désigne le même ensemble.La syntaxe d'un constructeur d'ensemble est :[ élément1, ..., élémentn ]où chaque élément est soit une expression désignant un scalaire ayant le type de base de l'ensemble ou une paire de telles expressions avec deux points (..) entre. Quand un élément est de la forme x..y, c'est un abrégé pour tous les scalaires compris dans l'intervalle allant de x à y, bornes incluses ; mais si x est supérieur à y, alors x..y ne désigne rien et [x..y] est l'ensemble vide. Le constructeur d'ensemble [ ] désigne l'ensemble vide alors que [x] désigne l'ensemble dont le seul membre est la valeur de x.Voici des exemples de constructeurs d'ensembles :[red, green, MyColor] [1, 5, 10..K mod 12, 23] ['A'..'Z', 'a'..'z', Chr(Digit + 48)] Pour plus d'informations sur les ensembles, voir Ensembles. @+ Cirec

florenth · Answer

Exact Julio !
Delphi effectue deux additions pour déterminer si la valeur se trouve dans le bon intervalle.
Dans le cas ou tu précises plusieurs intervalles comme [1..25, 50..99] alors il y a quatre additions, et ainsi de suite !
Mais finalement, pas de tableau ! Et c'est là l'avantage !

Bien sur, ce genre de code n'es optimisé qu'a la compilation, donc si ton ensemble E est inconnu à la compil, ça risque d'être plus dur pour Delphi d'optimiser, et il y a aura une boucle.

florenth · Answer

Groossse bétise de ma part !!
Dans tous les cas, il n'y a pas de boucles pour les ensembles, mais une opération bit-à-bit.

Dans le cas suivant, voici le code asm pour vérifier "if B in E then":
and ebx, $000000ff
bt [epb-$20],ebx
jnb +$0a

Ce qui est trèèès court et donc très rapide !
Pour info, voila le code de test :

type
  TByteSet = set of Byte;

function GetEns: TByteSet;
begin
  if Random > 0.5 then
    Result := [1..25, 50..99]
  else
    Result := [1, 8, 9, 12, 48, 51, 78];
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  E: TByteSet;
  B: Byte;
begin
  B := Trunc(Random * 256);
  E := GetEns;
  if B in E then
    ShowMessage('ok');
end;

Alors ? Scotché le francky hein ?
(la boule est en fait dans les instructions du processeur, mais comme il s'agit d'instructions "de base" ça va super vite, ndlr)

Francky23012301 · Answer

Alors ? Scotché le francky hein ? Non car comme tu l'a dis il y a bel et bien  une boucle qui a lieu . 

Plus honettement le ' if B in E then' utilise une technique de détermination plus performante (comme l'est la méthode par dichotomie) qu'un simple listage, mais cela n'enlève rien à l'obligation d'une boucle (Comme je te disais il fallait bien quelque soit quelque part . Il s'avère qu'elle est dans les instructions du processeur).

On pourrait aussi penser à une autre technique qui consiste à lister le tableau (ou constructeur d'ensembles dans notre cas) des deux extremités à la fois une sorte de For To - For DownTo. Il est fort à parier que coder correctement on obtient de bien meilleur résultat qu'un simple listage et peut etre meme que par la méthode dichotomique.

Par contre effectivement méa culpa, la méthode de Julio doit etre plus rapide .

Caribensila · Answer

Pour que ton idée For To + For DownTo fonctionne, il faudrait threader l'application et avoir au moins un dual-core je pense.

Francky23012301 · Answer

Dual Core je sais pas Cari mais threader l'application peut etre une bonne idée (Ca dépend du code  : je vais faire des tests tiens )

C'est pas possible il doit y avoir des mots qui sont bouffer par la TextBox

f0xi · Answer

si c'est pour des tableaux d'entiers :

function ValueInArray(const aValue: integer; const aArray: array of integer; var aValueIndex: integer): boolean;
var
  n, L, H: integer;
begin
  result := false;
  L := Low(aArray);
  H := high(aArray);
  aValueIndex := L-1;
  for n := L to H do
  begin    result :aValue aArray[n];
    if result then
    begin
      aValueIndex := n;
      exit;
    end;
  end;
end;

... 

en passant :

if N in [X] then

test si N est dans l'ENSEMBLE [X]

ensembles =/= tableaux

Francky23012301 · Answer

Oué mais pour tester si N est dans l'ENSEMBLE [X] faut bien qu'il regarde si chacun des éléments correspond à X ? Donc sans boucle pas possible.

Qui a dit que Francky il est tétu

Tester si une valeur est dans tableau

23 réponses

Votre réponse

Discussions similaires