Forums Développement Multimédia

Aller au contenu

Mélanger Array : function Shuffle

CODE Actionscript

36 réponses à ce sujet

#1 julienrobidet

    Ceinture Noire

  • Members
  • PipPipPipPipPipPipPip
  • 201 messages

Posté 03 September 2008 - 14:55 PM

Bonjour,

je cherche à développer une fonction permettant de mélanger un tableau dans un ordre aléatoire, je suis novice en POO, mais je me suis dis qu'il doit être mieux que je créé une classe permettant de faire ça... En cherchant un peu je suis tomber sur la class ci-dessous mais j'ai un peu de mal à la mettre en place !!!

Déjà si j'ai bien compris c'est un extension de la class Array et il me suffit de faire monTableau.shuffle(); pour le mélanger ?

Ou dois-je enregistrer ce fichier ExtendedArray.as ?

Action Script


package com.utils
{
dynamic public class ExtendedArray extends Array
{
public function ExtendedArray(... optionalArgs){
for each (var value:* in optionalArgs){
super.push(value);
}
}

public function shuffle(startIndex:int = 0, endIndex:int = 0):Array{
if(endIndex == 0) endIndex = this.length-1;
for (var i:int = endIndex; i>startIndex; i--) {
var randomNumber:int = Math.floor(Math.random()*endIndex)+startIndex;
var tmp:* = this[i];
this[i] = this[randomNumber];
this[randomNumber] = tmp;
}
return this;
}
}
}

Merci !!!

#2 paodao

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 7081 messages

Posté 03 September 2008 - 15:04 PM

salut

y' a plus simple pour mélanger un tableau

Action Script


var tab:Array = [1,2,3,4,5,6,7]

tab.sort(tri)
function tri(a:Number, b:Number){
return Math.random()
}

trace(tab)

a+

#3 julienrobidet

    Ceinture Noire

  • Members
  • PipPipPipPipPipPipPip
  • 201 messages

Posté 03 September 2008 - 15:36 PM

En effet ça marche, j'ai tout de même un peu de mal à comprendre !!!

Merci, cependant je n'arrive pas à résoudre mon problème de classe !

#4 0900.am

  • Members
  • PipPipPipPipPipPipPipPip
  • 1505 messages

Posté 03 September 2008 - 15:47 PM

si tu veux utiliser la méthode shuffle de cette classe il faut d'abord l'instancier et ensuite tu pourras appeler la méthode shuffle sur cette instance de ta classe

Action Script



var tab:ExtendedArray = new ExtendedArray (1,2,3,4,5,6);
tab.shuffle ();




mais c'est vrai que tu te compliques la vie et la méthode que te donne paodao est bien meilleure (la simplicité n'a pas de prix)

#5 julienrobidet

    Ceinture Noire

  • Members
  • PipPipPipPipPipPipPip
  • 201 messages

Posté 03 September 2008 - 16:05 PM

Oui, par contre je dois virer le com.utils derrière package ?

Merci !

#6 yoxos

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3757 messages

Posté 03 September 2008 - 16:40 PM

salut,

soit tu mets la classe dans un dossier utils placé dans un dossier com soit tu vires le com.utils et place la classe au même niveau que ton fla, tu peux aussi définir un classPath dans les paramètres du fla.



#7 neolao

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3827 messages

Posté 03 September 2008 - 16:55 PM

par contre, la fonction de tri est exécuté plus de fois que le total d'éléments du tableau

faudrait faire des bench
j'aime bien la permutation aléatoire moi

#8 julienrobidet

    Ceinture Noire

  • Members
  • PipPipPipPipPipPipPip
  • 201 messages

Posté 03 September 2008 - 16:59 PM

Désolé mais je ne trouve pas le dossier com, mais je trouve le utils dans C:\Program Files\Adobe\Adobe Flash CS3\fr\First Run\Classes\mx\utils ??

Merci !

#9 paodao

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 7081 messages

Posté 03 September 2008 - 17:10 PM

yop

a+

Fichier(s) joint(s)



#10 yoxos

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3757 messages

Posté 03 September 2008 - 17:25 PM

Citation (jr2003 @ Sep 3 2008, 05:59 PM) Voir le message
Désolé mais je ne trouve pas le dossier com, mais je trouve le utils dans C:\Program Files\Adobe\Adobe Flash CS3\fr\First Run\Classes\mx\utils ??

Merci !

je voulais dire : faut que tu crées un dossier com et un dossier utils dans le même répertoire que ton fla et que tu y places la classe. (comme ce qu'a fait pao dans le zip qu'il t'a joint en fait icon_smile.gif )

j'aime bien la permutation aléatoire moi aussi icon_smile.gif

#11 neolao

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3827 messages

Posté 03 September 2008 - 17:34 PM

Action Script


var tab:Array = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
var totalIteration:int = 0;



// methode 1
tab.sort(tri)
function tri(a:Number, b:Number){
totalIteration++;
return Math.random()
}
trace("Iterations: "+totalIteration);
trace(tab)



// methode 2
function tri2(element:*, index:int, arr:Array) {
var tmpId:int = Math.round(Math.random()*(arr.length - 1));
var tmp:* = arr[tmpId];
arr[tmpId] = arr[index];
arr[index] = tmp;
totalIteration++;
}
totalIteration = 0;
tab.forEach(tri2);
trace("Iterations: "+totalIteration);
trace(tab);


#12 paodao

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 7081 messages

Posté 03 September 2008 - 17:39 PM

neo-lao: gourou.gif

merki icon_biggrin.gif

#13 tlecoz

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3486 messages

Posté 03 September 2008 - 18:35 PM

Citation
salut

y' a plus simple pour mélanger un tableau

Action Script

 
var tab:Array = [1,2,3,4,5,6,7]

tab.sort(tri)
function tri(a:Number, b:Number){
return Math.random()
}

trace(tab)

a+


hummmm....
Ca a l'air bigrement efficace...
Mais comment ca fonctionne ? icon_redface.gif



Merci d'avance gourou.gif


#14 paodao

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 7081 messages

Posté 03 September 2008 - 18:38 PM

suffit de lire l'aide icon_wink.gif
f1->reference du language...AS3->Array->Methides->sort()

en gros ta fonction de tri renvoie -1,0 ou 1
-1 a et devant b
0 a=b
1 b devant a

donc le random suffit a le simuler
ca marche aussi en AS2 et c'est pas de moi, je l'es trouvé sur le forum, c'est efficace en AS2, en AS3 y'a mieux cf:neo-lao

a+

#15 fabien.huet

    Ceinture Marron

  • Members
  • PipPipPipPipPipPip
  • 173 messages

Posté 03 September 2008 - 19:26 PM

J'avais eu à faire un shuffle sur un tableau multidimentionnel. En l'occurence, c'est beaucoup plus simple, à la création du tableau, on créé une dimension supplémentaire pour le tableau, on lui attribue une valeur aléatoire, puis on sort le tableau sur cette valeur. Ça randomise assez bien.

#16 tlecoz

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3486 messages

Posté 03 September 2008 - 19:48 PM

Merci pour ta réponse gourou.gif

Jusqu'a present j'utilisais la methode de El Magico que l'on trouve ici :

http://flash.mediabox.fr/index.php?showtop...0&hl=unsort

#17 marc.ollivrin

    Ceinture Blanche

  • Members
  • Pip
  • 8 messages

Posté 28 September 2010 - 18:22 PM

Bah heuuu ... Sans vouloir re-lancer un vieux sujet, merci à neo-lao !

Je viens de repiquer ta fonction pour mélanger un tableau de tiles de couleur au début d'une partie (je me suis fixé de faire un petit jeu simple de carrés de couleur à aligner pour marquer un score en as3), et bien ça marche du tonnerre ! :D

#18 neolao

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3827 messages

Posté 28 September 2010 - 18:29 PM

Hehe, ça date :)

#19 nniten

    Ceinture Jaune

  • Members
  • PipPip
  • 19 messages

Posté 04 March 2011 - 17:16 PM

Voir le messageneo-lao, le 03 September 2008 - 17:34 PM, dit :

Action Script

// methode 2
function tri2(element:*, index:int, arr:Array) {
	var tmpId:int = Math.round(Math.random()*(arr.length - 1));
	var tmp:* = arr[tmpI"];
arr[tmpId] = arr[index];
arr[index] = tmp;
totalIteration++;
}
totalIteration = 0;
tab.forEach(tri2);
trace("Iterations: "+totalIteration);
trace(tab);

Bonjour à tous.
Je viens d'utiliser cette fonction pour un boulot et elle fonctionne à la perfection, donc je vais commencer par te remercier neo-lao.

Seul souci (et j'ai un peu honte de l'avouer), je ne la comprend pas.
IL y a en particulier un truc qui me chagrine :

dans la définition de la fonction tri2, tu dis qu'elle a besoin de 3 arguments, hors quand on l'appel, on ne précise pas ces arguments.

Ensuite, dans ces arguments, que signifie : "element:*".

Serait il possible que qq'un m'explique ces deux points ?

#20 neolao

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3827 messages

Posté 04 March 2011 - 17:21 PM

Quand on écrit
tab.forEach(tri2);
On n'appelle pas la fonction tri2, on appelle la fonction forEach avec comme argument tri2, nuance.
La fonction forEach attend comme premier argument, une fonction (eh oui).

Ensuite, "element:*" veut dire que l'argument "element" peut être de n'importe quel type.

#21 Nataly

    Community Jane

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 5783 messages

Posté 04 March 2011 - 17:38 PM

Et hop ! le tuto qui débrouille l'embrouille :)
Le savoir est le seul bien qui s'accroit quand on le partage
une tartine de tutos

#22 nniten

    Ceinture Jaune

  • Members
  • PipPip
  • 19 messages

Posté 04 March 2011 - 17:41 PM

Waw, rapide ! Tout d'abord merci de ta réponse.

En fait j'avais bien compris qu'on appelait pas directement tri2. Mais j'avoue que je comprend toujours pas ou est ce qu'on lui précise les arguments "element", "index" et "array".

Le fait qu'elle ne soit pas appeler directement, mais via le forEach ne change pas vraiment mon problème de compréhension.

En fait moi pour l'instant je lis :
"à chaque index du tableau tu lances tri2", alors que je m'attendrais plutôt à lire
"à chaque index du tableau tu lances tri2 avec element = ..., index = ... et array = ...".

Je comprend bien qu'ici arr c'est tab et index c'est l'index de tab à chaque "boucle" du forEach, mais je vois pas ou est ce qu'on précise cela à tri2

(j'ai l'impression de pas être clair du tout...déoslé).

edit : vais de ce pas lire le tuto, merci Nataly.

edit 2 :

Citation

"La signature diffère selon les méthodes, mais le tronc commun ce sont les trois arguments requis :
• un variant qui vaut l'élément en cours, lors de chaque passage
• un int qui vaut l'index de l'élément courant
• un Array qui vaut le tableau sur lequel la méthode a été appelée."

OK, c'est donc logic.

Merci à vous deux.

Modifié par nniten, 04 March 2011 - 17:44 PM.


#23 neolao

  • Honoris
  • PipPipPipPipPipPipPipPip
  • 3827 messages

Posté 04 March 2011 - 17:46 PM

On ne le précise pas, tu peux imaginer que la fonction forEach soit :


function forEach(myFunction)
{
    for(var index:int = 0; index < this._list.length; index++) {
        myFunction(this._list[index], index, this._list);
    }
}
 

forEach va juste appeler la fonction de tri que tu lui as donné. Il va l'appeler avec comme premier argument l'élément courant, comme deuxième argument l'index et comme troisième argument le tableau.

#24 nniten

    Ceinture Jaune

  • Members
  • PipPip
  • 19 messages

Posté 04 March 2011 - 17:52 PM

Excellent.
Encore merci pour l'explication.

#25 makarloin

    Ceinture Blanche

  • Members
  • Pip
  • 8 messages

Posté 03 January 2012 - 21:12 PM

Hello

Y'a aussi la solution du while.
J'imagine qu'elle est moins performante, mais elle n'oblige pas à avoir une variable totalIteration qui se balade hors de la function, ce qui permet de l'ajouter facilement ds une classe arrayutils (et accessoirement pour les flemmards, elle est plus courte)


public function randomize(aSource:Array):Array
{
        var finaltab:Array = new Array();
        while (aSource.length) finaltab.push(aSource.splice(Math.round(Math.random() * aSource.length - 1), 1));
        return finaltab;
}
trace(randomize([0,1,2,3,4,5,6,7,8,9])); //  -->  7,5,2,1,3,9,8,6,4,0
 


++
makar

#26 Badwolf

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 667 messages

Posté 04 January 2012 - 11:29 AM

si c'est la meilleure performance qui est recherchée, il faut éviter les splice, slice ainsi que le boucles for/foreach.

 function shuffle(array:Array):Array {
    var n:Number = array.length;
        while (n > 1) {
            var k:Number = Math.floor(Math.random()*n);
                        n--;
            var tmp:* = array[k];
            array[k] = array[n];
            array[n] = tmp;
        }
    return array;
}

Haoooooooooooooooooooooooooooooooooooooooooooooou !!!

#27 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 04 January 2012 - 11:52 AM

Si c'est la meilleure performance qui est recherchée, il faut éviter les Math.floor() et préférer des variables de type int (presque 30 à 40% de gain chez moi). Je ne parle que du code, pas de l'algo…
;-)

var n2:int;
var k2:int;
var temp:*;
function shuffle2(array:Array):Array {
    n2 = array.length;
        while (n2 > 1) {
            k2 = Math.random()*n2;
                        n2--;
            temp = array[k2];
            array[k2] = array[n2];
            array[n2] = temp;
        }
    return array;
}


#28 frangois

    Ceinture Noire

  • Members
  • PipPipPipPipPipPipPip
  • 224 messages

Posté 04 January 2012 - 11:59 AM

La méthode de Badwolf tarte environ 10x plus vite que le traditionnel :

data.sort(function(): int {return (Math.random() > .5? -1: 1)});

Ce qui est tout à fait remarquable mais logique: il n'a pas d'instanciation d'objet Function.
Je suis dispo en free-lance. Et j'ai un blog.

#29 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 04 January 2012 - 12:10 PM

Rapide, OK.
Mais côté algo, j'ai du mal à suivre… j'ai eu le premier sentiment que les objets etaient tous positionnés plus avant que leur place dans le tableau originel. Mon bon sens m'a fait remarqué que ce n'etait pas possible, faute d'espace :D et je vois bien qu'un élément placé avant dans le tableau sera retrié ensuite… puisqu'on décrémente la variable n.
Seulement, je n'arrive pas à voir le résultat de façon globale et du coup, je n'arrive pas à me convaincre que le tri soit complètement aléatoire.
Quelqu'un a une vision claire du résultat ? De comment on peut vérifier "l'aléatoiritée" d'un tri ?


La méthode de Badwolf tarte environ 10x plus vite que le traditionnel :
 
Du coup, avec les int et sans Math.floor() on serait à 16 fois plus rapide ? :shock: :Hola:

#30 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 04 January 2012 - 12:14 PM

Voir le messageDldler, le 04 January 2012 - 12:10 PM, dit :

… j'ai eu le premier sentiment que les objets etaient tous positionnés plus avant que leur place dans le tableau originel. Mon bon sens m'a fait remarqué que ce n'etait pas possible, faute d'espace :D


VU !
Suis-je bête.

On ne fait pas avancer les éléments… on échange 2 éléments. L'un avance, tandis que l'autre recule.
Je rouille…

#31 frangois

    Ceinture Noire

  • Members
  • PipPipPipPipPipPipPip
  • 224 messages

Posté 04 January 2012 - 12:18 PM

la tienne est 25% + rapide que celle de BadWolf avec les int (64ms vs 86ms, sur 200000 int).
Je suis dispo en free-lance. Et j'ai un blog.

#32 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 04 January 2012 - 14:23 PM

Oui. Je vois. En fait, plus le tableau est long, plus la méthode Badwolf explose les perfs… et le gain via les int s'amenuise d'autant. Ça reste quand même appréciable si on a besoin de perf brute.

Autre avantage de la version Badwolf, elle fonctionne aussi bien en as2 qu'en as3 (si j'ai tout bien suivi).
L'essayer c'est l'adopter.




---
Dernière question ?
Pourquoi un while et un n - - plutôt qu'un for basique avec un i + + ? J'ai fait un test comparatif, les perfs sont identiques. Est-ce que le tri serait alors moins aléatoire ?

#33 molosc

    Ceinture Noire

  • Members
  • PipPipPipPipPipPipPip
  • 487 messages

Posté 12 January 2012 - 23:34 PM

Perso pour mélanger un tableau contenant des objets, j'utilise ceci :

public static function shakeArray(a:Array):void {
        var b:Array = getShakedArray(a);
        a = b;
}
public static function getShakedArray(a:Array):Array {
        var tabForRand:Array = [];
        var lng:int = a.length;
        for (var i:int = 0; i < lng; i++) {
                tabForRand.push( { rand:Math.random(), item:a[i] } );
        }
        tabForRand.sortOn("rand");
        var tab:Array = [];
        for (var j:int = 0; j < lng; j++) {
                tab.push(tabForRand[j].item);
        }
        return tab;
}

C'est pas le plus optimisé mais ça marche bien.

#34 Badwolf

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 667 messages

Posté 13 January 2012 - 13:59 PM

Je cois bien que si tu fais ca sur 1000 tableaux ton PC explose :texas:
Haoooooooooooooooooooooooooooooooooooooooooooooou !!!

#35 Galacta

    Etudiant Ingénieur

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 689 messages

Posté 13 January 2012 - 18:30 PM

Yop,

Si on veut pousser le vis jusqu'au bout, un boucle répéter est plus adaptée et fait gagner 5ms.

On sait qu'on va boucler au moins une fois, ce qui du coup permet d'économiser le premier test à l'entrée de la boucle tant que.

59ms :

public function shuffle2(array:Array,l:int):void {
        var k2:int;
        var temp : int;
        var start: uint = getTimer();
        do {
                k2 = Math.random()*l;
                temp = array[k2];
                array[k2] = array[l];
                array[l] = temp;
           }while (--l > 1);
}

Modifié par Galacta, 13 January 2012 - 18:34 PM.

Word hard, play hard.

#36 dldler

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 4163 messages

Posté 13 January 2012 - 18:37 PM

:-D


Je creuse aussi une version plus rapide. Je ne sais pas si je vais y arriver, mais au moins l'espoir fait vivre…

#37 Galacta

    Etudiant Ingénieur

  • Moderateur
  • PipPipPipPipPipPipPipPip
  • 689 messages

Posté 13 January 2012 - 18:44 PM

Je cherche aussi ! Il semblerait qu'il ne soit pas possible de descendre en dessous de nlog(n), mais ça se fait avec une boucle for
Word hard, play hard.



1 utilisateur(s) li(sen)t ce sujet

0 membre(s), 1 invité(s), 0 utilisateur(s) anonyme(s)

authorised training centre

Centre de Formation Mediabox - Adobe et Apple Authorised Training Center.

Déclaré auprès de la Direction du Travail et de la Formation Professionnelle

Mediabox : SARL au capital de 62.000€ - Numéro d'activité : 11 75 44555 75 - SIRET : 49371646800035

MEDIABOX, 23, rue de Bruxelles, 75009 PARIS

FFP