Discussion :

[djibril]

Salut,
petite question bête sur la dichotomie.
Le principe est de toujours coupé en deux afin d'arriver à ses fins.
Mais n'ayant plus de cervelle ce soir, si j'ai un tableau contenant 100 nom d'employés et que je recherche un employé en particulier, comment procéder par dichotomie pour le trouver le plus rapidement possible?
car généralement on utilise cet algo sur des tableaux d'entiers triés, et on fait des comparaisons, mais si ce sont des chaines de caractères, on fait comment?

Merci

[Jedai]

Ben exactement pareil... Sauf que la procédure de comparaison est un peu plus couteuse (cmp au lieu de <=>).

--
Jedaï

[djibril]

j'essaye de faire une procédure de recherche dans un tableau d'entiers déjà.
j'arrive plus à penser
Sauf si tu en as une sous la main, histoire de voir le code. ensuite, j'aimerais bien l'adapter à tout type de tableau, car y a pas de fonction perl pour tester l'existence d'une valeur dans un tableau. Y a surement un module pour (si tu le trouve, je veux bien), mais bon par curiosité, j'ai envie de me prendre le chou

[Jedai]

Tu parles bien d'une recherche dans un tableau trié ?
Pour généraliser il faut autoriser le programmeur à te fournir la fonction de comparaison utilisée pour trier le tableau en premier lieu.

En fait :

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
#!/usr/bin/perl
use strict; use warnings;
 
sub search {
  my ($compare, $elem, $arr) = @_;
  my ($start, $end) = (0, $#{$arr});
  while( $start <= $end ) {
    my $middle = int(($start + $end) / 2);
    my $cmp_result = do {
      local($a,$b) = ($elem,$arr->[$middle]);
      $compare->()
    };
    if( $cmp_result == 0 ) {
      return $middle;
    }
    elsif( $cmp_result < 0 ) {
      $end = $middle - 1;
    }
    else {
      $start = $middle + 1;
    }
  }
  return;
}
 
my @a = (1..20);
 
print search(sub {$a <=> $b}, 20, \@a), "\n";
 
__END__

--
Jedaï

[djibril]

pour l'instant je prends juste le tableau, à moi de le trier apres.
Ok je vais regarder ton code

[djibril]

je ne savais pas que
print $a <=> $b; renvoyer 0, 1 ou -1

Pas mal

[djibril]

bon jedai,
j'ai une autre question. supposons que je souhaite faire la recherche dans tout type de tableau (mélange d'entier et chaine).
Je sais pas si mon algo serait rapide, c'est à dire.
1- récupérer le tableau, scinder le tableau en 2 tableaux
2 - tableaux d'entiers puis sort + faire la recherche par dichotomie
3 - si rien, récupérer tableau de chaine + sort + dichotomie
qu'en penses tu?
est ce pas mieux de faire directement cmp ?

[Jedai]

Tout ce qui t'intéresse c'est de pouvoir faire des recherches rapides (par dichotomie) dans ton tableau, n'est-ce pas ? Tu te fous d'avoir un ordre particulier dans ton tableau ? Dans ce cas autant simplement trier alphabétiquement (avec un sort sans routine particulière) et utiliser search avec sub {$a cmp $b}. Ca marchera très bien.

Par ailleurs, pour faire une recherche d'élément dans un tableau non trié en Perl, on peut utiliser grep :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

print "$elem est dans le tableau\n" if grep {$elem eq $_} @array;

Ou mieux, first :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
use List::Util qw/first/;
print "$elem est dans le tableau\n" if first {$elem eq $_} @array;

Si tu ne fais pas beaucoup de recherches dans ce tableau, ça ne vaut pas le coup de le trier juste pour pouvoir faire des recherches dichotomiques.

--
Jedaï

[djibril]

après plusieurs test, cmp est pas fait pour la dichotomie, trop long, un bon grep suffit et en plus avec cmp, le sort est mortel .

Par contre pour des tableau d'entier, c pas mal, mais faut qu'il soit trié à la base, sinon on perd en performance et un grep fait serait donc plus judiciable

[Jedai]

après plusieurs test, cmp est pas fait pour la dichotomie, trop long, un bon grep suffit et en plus avec cmp, le sort est mortel .

Non, le sort avec cmp (ou plus exactement sans routine de tri, puisqu'il s'agit du défaut) est le plus rapide des tris. De plus une recherche par dichotomie avec cmp est extrêmement rapide, bien meilleure qu'un grep.
Si tu as beaucoup de recherche à faire dans un tableau, il est toujours mieux de le trier (ou maintenir trié) et de faire des recherches par dichotomie (NB : dans les cas où c'est possible, un hash est encore plus rapide).
De plus tu devrais toujours utiliser first plutôt que grep pour faire une recherche dans un tableau : first s'arrête dès qu'il a trouvé l'élément, grep parcourt tout le tableau dans tous les cas.