Mélanger une liste aléatoirement

**Ickou** · 22/12/2005, 11h11

Salut à tous !

je cherche la meilleur façon pour mélanger une liste aléatoirement, je viens d'écrire un tirage aléatoire mais il est trop gourmand en processeur et il met une plombe à s'exécuter....... car mes listes peuvent comporter des millions de valeurs !!

voici ce que j'ai écrit :

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
 
$taille=$#liste_v+1;
    for ($position=0; $position<=$#ech; $position++) {
      $truc=undef;
      while($truc eq "") {
        $tirage  = int(rand($taille))-1;
        if (defined ($liste_v[$tirage])) {
          $truc=$liste_v[$tirage];
          delete $liste_v[$tirage];
        }
      }
      if ($truc ne 'null') {
        print V "\t$truc";
      }
      else {
        print V "\t";
      }
    }
    print V "\n";

Ma liste c'est "@liste_v".

Je viens de voir qu'en php, il existe une fonction pour mélanger une liste (srand(time()); shuffle($tab)

, il y a un truc équivalent en perl ??

Comment optimiser mon script pour qu'il aille beaucoup plus vite ??

merci

**Arioch** · 22/12/2005, 12h15

Ta liste contient quoi comme type de données exactement ? Du numérique (int, float), des chaînes de caractères ? Peux-tu nous montrer un exemple concret ?

**Arioch** · 22/12/2005, 12h35

Bon. Y a sûrement moyen de faire plus simple mais voici un bout de code travaillé à l'instant et qui fonctionne.

Il prend aléatoirement un élément d'un tableau et supprime cet élément du même tableau. A toi de revoir mon code selon tes besoins bien entendu

:

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
#/usr/bin/perl
use strict;
srand();
 
@_ = (1,2,3,4,5,6,7,8,9,10);
 
while(@_)
{
    $_ = scalar(@_);
    my $pos = int(rand($_));  # position de l'élément choisi dans la liste
    my $resultat = $_[$pos];  # resultat contient l'élément choisi
    $_[$pos] = undef;
    @_ = ReconstruitListe(@_);
}
 
# fonction qui reconstruit une liste en la nettoyant de ses éléments undefined
sub ReconstruitListe
{
    my @liste = @_;
    my @new_liste;
 
    for(my $i = 0; $i < scalar(@liste); ++$i)
    {
        push(@new_liste, $liste[$i]) if $liste[$i] ne undef;
    }
    return @new_liste;
}

**Arioch** · 22/12/2005, 12h45

Tu veux traiter des millions de valeurs ??? Ah, heu

Quoiqu'il arrive, ça prendra du temps, tu t'en doutes

Je pense que si ta méthode prend bcp de temps, c'est parce que tu cherches un élément de la liste en parcourant la liste tant que tu en trouves un qui n'est pas null.

Ma méthode nettoie ta liste de chaque élément supprimé, puis recompose une liste ne contenant que des valeurs. Je pense qu'aux premiers appels à la fonction que j'ai codé, ça prendra du temps mais que plus la liste diminuera, plus ça ira vite.

Enfin, moi j'dis ça, j'dis rien. Y a pas un spécialiste dans les parages ? Jedaï, fais pas l'timide, je sais qu't'es là !

**Ickou** · 22/12/2005, 13h59

Merci Arioch

je vais essayer ta méthode ....

Pour être plus précis dans ce que je veux faire :
j'ai une matrice (fichier texte tabulé) de nombres à virgule (30 000 lignes, 160 colonnes) et je voudrais construire la même matrice en mélangeant les valeurs....

le début de mon programme "split" chaque ligne pour en faire la liste que tu connais ....

**Ickou** · 22/12/2005, 15h57

Hello Arioch

J'ai testé les 2 algorithmes, verdict ........

désolé mais le mien est bien plus performant et de très loin !!!
la liste d'essais comporte 13 millions de valeurs et le fait de recréer la liste utilise beaucoup de performance.....

je pense que je vais garder mon code à moins que quelqu'un me propose quelque chose......

merci quand même

**Jedai** · 22/12/2005, 16h51

Si le "shuffle" de List::Util est codé nativement, c'est sans doute la solution à privilégier, sinon, pour mélanger (avec une équiprobabilité des permutations) une liste, un algorithme simple en O(n) est de faire la chose suivante :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
sub shuffle ($) {
  my $arref = shift;
  my $i = @$arref;
  my $n;
  while( $i > 0 ){
    $n = int(rand($i));
    ($arref->[$i], $arref->[$n]) = ($arref->[$n], $arref->[$i]);
    $i--;
  }
}

(Après vérification, il s'avère que le shuffle de List::Util n'est pas codé nativement, et est très proche du code ci-dessus.)
[EDIT] Correction, j'ai été trompé par du code d'Autoloader, le shuffle de List::Util est en natif par défaut et il y a une version en perl pur dont voici le code pour référence (sérieusement contourné mais c'est le même algorithme!

) :

Code :

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

1
2
3
4
5
6
7
8
9
sub shuffle (@) {
  my @a=\(@_);
  my $n;
  my $i=@_;
  map {
    $n = rand($i--);
    (${$a[$n]}, $a[$n] = $a[$i])[0];
  } @_;
}

--
Jedaï

**Ickou** · 22/12/2005, 17h34

Merci jedai

ta foonction tu l'appel comment après ??

comme ça ( @liste suffle @liste ) ???

**Jedai** · 22/12/2005, 19h15

"shuffle \@array;"

Mais bon... Benchmark à l'appui, le shuffle en XS (donc en natif) de List::Util est 8 fois plus rapide que le mien, en plus il est pas sur place "@permute = shuffle @orig" !!

Par contre, leur shuffle en Perl pur est plus lent que le mien (mais il ne travaille pas sur place, donc c'est normal).

Utilise donc le shuffle de List::Util qui devrait être le shuffle en natif (sauf si tu es sur une plateforme exotique). Il met moins d'une demi-seconde à "shuffler" 1000000 d'éléments (le mien met 2s). (ça c'est valable sur mon ordinateur qui n'est pas un foudre de guerre... )

[EDIT] Et même en faisant une copie préalable (c'est à dire à fonctionnalité équivalente), mon programme reste supérieur au leur en perl pur, na !

--
Jedaï

**Jedai** · 22/12/2005, 21h41

Et pour en remettre une couche, voici ma version avec Inline::C, encore plus rapide que la version native de List::Util (mais sur place) !!

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
 
use Inline C => <<'END_OF_C_CODE';
 
void cshuffle(SV* array_ref) {
  AV* array;
  I32 index, i;
  SV** sv_1, **sv_2;
  SV* sv_temp;
 
  if (! SvROK(array_ref))
    croak("array_ref is not a reference");
 
  srand(time( NULL ));
  array = (AV*)SvRV(array_ref);
  index = av_len(array);
  for (; index; index--) {
    i = (I32) (rand() % (index + 1));
    if( i != index ){
      sv_1 = av_fetch(array, index, 0);
      sv_2 = av_fetch(array, i, 0);
      sv_temp = *sv_1;
      *sv_1 = *sv_2;
      *sv_2 = sv_temp;
    }
  }
  return;
}
 
END_OF_C_CODE

( 1/3 de vitesse en plus !

3.12 shuffle d'une liste d'un million d'élément par seconde)

--
Jedaï

**Jedai** · 23/12/2005, 01h57

Et voici une version avec Inline::C, mais pas en place ce coup-ci ! Tout de même 20% plus rapide que le shuffle de List::Util : (avec en prime la version finale du cshuffle en place)

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
 
use Inline C => <<'END_OF_C_CODE';
 
void cshuffle(SV* array_ref) {
  AV* array;
  I32 index, i;
  SV** sv_1, **sv_2;
  SV* sv_temp;
 
  if (! SvROK(array_ref))
    croak("array_ref is not a reference");
 
  srand(time( NULL ));
  array = (AV*)SvRV(array_ref);
  index = av_len(array);
  for (; index; index--) {
    i = (I32) (rand() % (index + 1));
    sv_1 = av_fetch(array, index, 0);
    sv_2 = av_fetch(array, i, 0);
    sv_temp = *sv_1;
    *sv_1 = *sv_2;
    *sv_2 = sv_temp;
  }
  return;
}
 
void cshuffle_copy ( SV* truc, ... ){
  SV* sv_temp;
  I32 index, i;
  Inline_Stack_Vars;
 
  srand(time( NULL ));
  index = Inline_Stack_Items;
  for (; index; index--) {
    i = (I32) (rand() % (index + 1));
    sv_temp = Inline_Stack_Item(index);
    Inline_Stack_Item(index) = Inline_Stack_Item(i);
    Inline_Stack_Item(i) = sv_temp;
  }
  Inline_Stack_Done;
}
 
END_OF_C_CODE

Avec tout ça si t'es pas content !

--
Jedaï

**Jedai** · 23/12/2005, 02h03

Je rappelle que Inline::C compile la partie C la première fois que le script est exécuté, et ne la recompile que si le script est modifié.

--
Jedaï

**Ickou** · 23/12/2005, 11h28

Merci Jedai !

t'es vraiment un BOSS

mais je sais pas comment on utilise tes scripts

même ton premier script, je sais pas comment l'utiliser....
regarde, j'ai écrit ça (peux tu corriger mon code ?) :

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
 
@array=(2,5,6,9,7,8,5,25,45,78,25,668,235,78);
foreach $momo (@array) {print "$momo\n";}    print "et après :\n";
shuffle \@array;
foreach $momo (@array) {print "$momo\n";}
 
sub shuffle (@) {
  my @a=\(@_);
  my $n;
  my $i=@_;
  map {
    $n = rand($i--);
    (${$a[$n]}, $a[$n] = $a[$i])[0];
  } @_;
}

et les codes qui compile en C, tu fais comment pour les utiliser ??
tu sais je suis qu'un bricoleur moi

je te remercie

**Jedai** · 23/12/2005, 12h01

Là t'utilises pas le bon, celui-là c'est le "Pur Perl" de List::Util (il est pas très bon..), en plus celle-là de fonction n'est pas sur place, donc tu ne l'utilises pas de la bonne façon... Voici la version correcte (en utilisant ma version en Pur Perl)

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
 
@array=(2,5,6,9,7,8,5,25,45,78,25,668,235,78);
foreach $momo (@array) {print "$momo\n";}    print "et après :\n";
shuffle \@array;
foreach $momo (@array) {print "$momo\n";} 
 
sub shuffle ($) {
  my $arref = shift;
  my $i = @$arref;
  my $n;
  while( $i > 0 ){
    $n = int(rand($i));
    ($arref->[$i], $arref->[$n]) = ($arref->[$n], $arref->[$i]);
    $i--;
  }
}

Néanmoins, le plus rapide avec le moins de problème c'est de faire cela :

Code :

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

1
2
3
4
5
6
7
 
use List::Util qw(shuffle);
 
@array=(2,5,6,9,7,8,5,25,45,78,25,668,235,78);
foreach $momo (@array) {print "$momo\n";}    print "et après :\n";
@array = shuffle @array;
foreach $momo (@array) {print "$momo\n";}

Dans le tas, comme c'est pas sur place, t'es obligé de faire une copie intégrale de ton tableau, ce qui peut-être très génant pour un tableau de 13000000 d'éléments.
Donc tu peux aussi te tourner vers mes solutions en Inline::C.
Pour cela j'ai besoin de savoir sur quel système (OS surtout) tu es ?

[EDIT] Sur une machine plus récente, mon code est finalement 2 fois plus rapide pour la version "en place" et 1,5 fois plus rapide pour la version par copie.

--
Jedaï

**Arioch** · 23/12/2005, 12h11

Envoyé par Jedai

[EDIT] Sur une machine plus récente, mon code est finalement 2 fois plus rapide pour la version "en place" et 1,5 fois plus rapide pour la version par copie.

--
Jedaï

Ce type est une brute

Adieu, je vais me pendre

**Ickou** · 23/12/2005, 12h41

Merci Jedai !

Je travail avec plusieurs OS :
- Redhat (nos serveurs)
- SunOS 5.9 (serveur distant)
- avtive perl sous windows xp (mon pc)

je pense que je ferai tourné le programme sur le sunOS car c'est le plus puissant....
Explique moi sur ce qui t'arrange....

encore merci

**Ickou** · 23/12/2005, 13h05

Sinon jedai, que penses tu de ça :

pour rampalcer ça :

Code :

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

1
2
 
@tab = sort {$a  <=> $b} @tab ;

faire ça car la liste contient 500 000 000 valeurs :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
while ($test!= ($#tab-1)) {
  $test=0;
  for ($i=0; $i<$#tab; $i++){
    if ($tab[$i]>$tab[$i+1]) {
      $temp=$tab[$i]; $tab[$i]=$tab[$i+1]; $tab[$i+1]=$temp;
    }
    else {
      $test++;
    }
  }
}

le temps n'est pas un problème dans ce programme car je vais l'exécuter qu'une fois.....

je te remercie

**Jedai** · 23/12/2005, 13h11

En fait sur les Unix, il suffit d'installer Inline(::C) avec CPAN, et si CPAN marche alors Inline::C marchera aussi probablement (ensuite il suffit de lancer le script Perl et Inline s'occupe de tout

).
Sous Windows c'est un peu plus compliqué : en gros il faut que tu puisses compiler des modules Perl comportant du XS, donc il faut que tu ais un compilateur compatible avec ActivePerl. Le dernier build (815) permet d'employer mingw-gcc (et ça marche très bien, j'ai testé) et dmake, mais sinon il te faut le compilateur Microsoft et nmake.

Par ailleurs, j'ai découvert un "petit" problème : les randoms de Perl ou le rand() de la librairie standard ne prennent que 32000 valeurs différentes environ... Autrement dit, que ce soit avec mon code ou celui de List::Util, la distribution pour une liste à 13000000 d'éléments ne sera pas très homogène !

C'est assez facile à corriger en fait : il suffit de récupérer un rand() plus puissant, par exemple avec une librairie faite pour ça (pour la solution en Inline) ou un module (pour la solution Pur Perl). En fait ça exclut la solution List::Util, du moins si tu veux un vrai bon mélange.

--
Jedaï

**Jedai** · 23/12/2005, 13h17

500000000 de valeurs ? En Perl ? C'est peut-être une mauvaise idée....
De quelle type de valeur s'agit-il ?
De toute façon tu devrais considérer la possibilité d'employer PDL, sinon les performances seront désastreuses...
Si tes valeurs sont stockées dans un fichier, tu devrais aussi considérer la possibilité d'employer File::Sort.

--
Jedaï

**Ickou** · 23/12/2005, 13h56

mes valeurs sont des nombres à virgule dont le nombre de chiffre après le virgule est très variable, ils peuvent être positifs comme négatifs.....

Je te remercie pour tes très bons conseils

j'essairai Inline(::C) sous

de retour de vacances...

je ne vais plus pouvoir continuer à surveiller ce sujet car je pars dans ma famille.....

Bonnes fêtes

Mélanger une liste aléatoirement

Langage Perl

Discussions similaires

Partager

Partager