Page 1 sur 1
Créer une liste alléatoire sans redondance
Publié : ven. 13/nov./2009 6:47
par Thyphoon
Voilà une petite procedure qui me permet de faire une liste aléatoire
ici dans l'exemple j'ai une liste de 100 nombre que je veux avoir dans un ordre alléatoire sans avoir 2 fois le même nombre
ça fonctionne, mais je ne sais pas si c'est la meilleur façon de faire ! Car sur la fin la boucle parcourt la liste jusqu'à trouver un emplacement vide .... et si on demande une tres grande liste, c'est peut être un peu gourmand en ressource ! Qu'en pensez vous ?
Code : Tout sélectionner
Global Dim RandomList.l(10)
Procedure Liste(Nb.l)
RandomSeed(ElapsedMilliseconds())
ReDim RandomList(Nb)
n=0 ; Noter compteur
Repeat
n=n+1 ;
therand=Random(Nb)
countloop=0
Repeat
If RandomList(therand)>0 ; si il y a déjà une valeur a cette endroit on regarde juste apres
therand+1
countloop+1 ;on compte le nombre de fois ou ne peut pas mettre la valeur
EndIf
If therand>=Nb
therand=0
EndIf
If countloop>=nb ; si on rate le même nombre de fois que le nombre max de notre liste alors c'est qu'on a tout remplit !
Break 2;
EndIf
Until RandomList(therand)=0
RandomList(therand)=n
Until n=Nb
EndProcedure
NB=100
Liste(NB)
For z=0 To NB-1
Debug "Rand("+Str(z)+")="+Str( RandomList(z))
Next
Re: Créer une liste alléatoire sans redondance
Publié : ven. 13/nov./2009 9:45
par kelebrindae
J'vais dire une connerie, comme ça, sans réfléchir (mais ça ne me gène pas, j'ai l'habitude):
Tu te créé une structure avec deux champs:
- la valeur réelle, que tu peux renseigner séquentiellement (pas de doublons, donc);
- un autre champ numérique, que tu renseignes aléatoirement sans te soucier des doublons (mais avec un random sur une très grande valeur, pour qu'il y en ait le moins possible);
Ensuite, tu tries cette liste sur le deuxième champ avec "sortStructuredList" => les valeurs réelles se retrouvent en ordre aléatoire.
Enfin, tu recopies les valeurs dans la liste en sortie.
(je vais essayer de coder ça rapidement pour voir si ça marche, et je te poste le tout)
Re: Créer une liste alléatoire sans redondance
Publié : ven. 13/nov./2009 9:53
par Thyphoon
je suis curieux de voir ce que ça peut donner Kelebrindae !
moi en relisant la doc je suis tombé sur swap ! et ça m'a donnée une idée (j'aime bien relire de temps en temps la doc, car il y a toujorus des commandes qu'on oublie, ou qu'on utilise pas ... et voici le résultat de mon idée
Code : Tout sélectionner
Procedure Liste2(Nb.l)
RandomSeed(ElapsedMilliseconds())
ReDim RandomList(Nb)
For z=0 To Nb-1
RandomList(z)=z
Next
For z=0 To Nb-1
Swap RandomList(Random(Nb)),RandomList(Random(Nb))
Next
EndProcedure
Les différences de performance entre ma première procedure et la deuxième est vraiment flagrant !
voici un code pour comparer (je sais le debugger est activé, mais c'est tellement flagrant que le debugger ne rentre pas vraiment en compte)
Code : Tout sélectionner
Global Dim RandomList.l(10)
Procedure Liste(Nb.l)
RandomSeed(ElapsedMilliseconds())
ReDim RandomList(Nb)
n=0 ; Noter compteur
Repeat
n=n+1 ;
therand=Random(Nb)
countloop=0
Repeat
If RandomList(therand)>0 ; si il y a déjà une valeur a cette endroit on regarde juste apres
therand+1
countloop+1 ;on compte le nombre de fois ou ne peut pas mettre la valeur
EndIf
If therand>=Nb
therand=0
EndIf
If countloop>=nb ; si on rate le même nombre de fois que le nombre max de notre liste alors c'est qu'on a tout remplit !
Break 2;
EndIf
Until RandomList(therand)=0
RandomList(therand)=n
Until n=Nb
EndProcedure
Procedure Liste2(Nb.l)
RandomSeed(ElapsedMilliseconds())
ReDim RandomList(Nb)
For z=0 To Nb-1
RandomList(z)=z
Next
For z=0 To Nb-1
Swap RandomList(Random(Nb)),RandomList(Random(Nb))
Next
EndProcedure
NB=100000
Time=ElapsedMilliseconds()
Liste(NB)
Debug ElapsedMilliseconds()-Time
Time=ElapsedMilliseconds()
Liste2(NB)
Debug ElapsedMilliseconds()-Time
Re: Créer une liste alléatoire sans redondance
Publié : ven. 13/nov./2009 9:59
par kelebrindae
Ah oui, très bonne idée, le Swap!
Pour ma proposition, voilà ce que ça donne:
Code : Tout sélectionner
Global Dim RandomList.l(10)
Procedure liste(nb.i)
Structure randomList_struct
valeur.i
ordre.l
EndStructure
Protected NewList templist.randomList_struct()
Protected i.i
For i = 1 To nb
AddElement(templist())
templist()\valeur = i
templist()\ordre = Random(2147483647) ; maximum autorisé pour Random
Next i
SortStructuredList(templist(),0, OffsetOf(randomList_struct\ordre), #PB_Sort_Long)
ReDim RandomList(Nb)
i=0
ForEach templist()
RandomList(i) = templist()\valeur
i+1
Next templist()
EndProcedure
NB=100
Liste(NB)
For z=0 To NB-1
Debug "Rand("+Str(z)+")="+Str( RandomList(z))
Next
Mais je n'ai pas testé les perfs... A vue de nez, je dirais que le Swap est plus rapide.
Re: Créer une liste alléatoire sans redondance
Publié : ven. 13/nov./2009 10:50
par Thyphoon
c'est pas mal ! ta procedure est beaucoup plus rapide que mon premier code mais un peu plus lent que mon deuxième (250 contre 93 sur ma machine)
En tout cas merci l'idée est bonne !
Re: Créer une liste alléatoire sans redondance
Publié : ven. 13/nov./2009 18:51
par Le Soldat Inconnu
moi j'ai ce système : (tuto débutant)
http://www.purebasic.fr/french/viewtopic.php?t=1739
plus rapide que le code original mais plus lent que le swap. Mias le swap ne fonctionne pas à tous les coups dans l'état actuel des choses.
Code : Tout sélectionner
Global Dim RandomList.l(10)
Procedure Liste(Nb.l)
RandomSeed(ElapsedMilliseconds())
Redim RandomList(Nb)
NewList Temp_Liste.l()
For n = 1 To Nb ; On rempli la liste chainée avec des valeurs de 1 à 5000
AddElement(Temp_Liste())
Temp_Liste() = n - 1
Next
nb2 = Nb
Repeat ; Boucle de traitement
; Cette partie du code permet de mettre les valeurs dans le désordre.
nb2 - 1 ; Je décompte un élément car je vais le traiter ci-dessous
SelectElement(Temp_Liste(), Random(nb2)) ; Je choisis un élément au hazard dans la liste temporaire
RandomList(Nb - nb2 - 1) = Temp_Liste() ; Je le copie dans la liste final
DeleteElement(Temp_Liste()) ; Je supprime cet élément de la liste temporaire
Until nb2 = 0
EndProcedure
Procedure Liste2(Nb.l)
RandomSeed(ElapsedMilliseconds())
Redim RandomList(Nb)
For z=0 To Nb-1
RandomList(z)=z
Next
For z=0 To Nb-1
Swap RandomList(Random(Nb)),RandomList(Random(Nb))
Next
EndProcedure
Nb=5
time=ElapsedMilliseconds()
Liste(Nb)
Debug ElapsedMilliseconds()-time
Debug ""
For n = 0 To Nb - 1
Debug Str(n) + " = " + Str(RandomList(n))
Next
Debug "--------------------"
time=ElapsedMilliseconds()
Liste2(Nb)
Debug ElapsedMilliseconds()-time
Debug ""
For n = 0 To Nb - 1
Debug Str(n) + " = " + Str(RandomList(n))
Next
sui tu compiles plusieurs fois ce code, tu verras que tu obtiens parfois 2 fois la même valeur avec le swap
Re: Créer une liste alléatoire sans redondance
Publié : ven. 13/nov./2009 19:08
par Le Soldat Inconnu
j'ai corrigé ton système de swap
Code : Tout sélectionner
Global Dim RandomList.l(10)
Procedure Liste(Nb.l)
RandomSeed(ElapsedMilliseconds())
Redim RandomList(Nb)
NewList Temp_Liste.l()
For n = 0 To Nb - 1 ; On rempli la liste chainée avec des valeurs de 1 à 5000
AddElement(Temp_Liste())
Temp_Liste() = n
Next
nb2 = Nb
Repeat ; Boucle de traitement
; Cette partie du code permet de mettre les valeurs dans le désordre.
nb2 - 1 ; Je décompte un élément car je vais le traiter ci-dessous
SelectElement(Temp_Liste(), Random(nb2)) ; Je choisis un élément au hazard dans la liste temporaire
RandomList(Nb - nb2 - 1) = Temp_Liste() ; Je le copie dans la liste final
DeleteElement(Temp_Liste()) ; Je supprime cet élément de la liste temporaire
Until nb2 = 0
EndProcedure
Procedure Liste2(Nb.l)
RandomSeed(ElapsedMilliseconds())
Redim RandomList(Nb)
For z=0 To Nb-1
RandomList(z)=z
Next
Nb - 1
For z=0 To Nb
Swap RandomList(Random(Nb)),RandomList(Random(Nb))
Next
EndProcedure
Nb=5
time=ElapsedMilliseconds()
Liste(Nb)
Debug ElapsedMilliseconds()-time
Debug ""
For n = 0 To Nb - 1
Debug Str(n) + " = " + Str(RandomList(n))
Next
Debug "--------------------"
time=ElapsedMilliseconds()
Liste2(Nb)
Debug ElapsedMilliseconds()-time
Debug ""
For n = 0 To Nb - 1
Debug Str(n) + " = " + Str(RandomList(n))
Next
Re: Créer une liste alléatoire sans redondance
Publié : ven. 13/nov./2009 19:14
par Thyphoon
j'ai vu ton code LSI avec en utilisant les listes c'est très ingénieux comme système ! mais ça reste plus lent que les swaps ! En tout cas merci pour la correction,