Créer une liste alléatoire sans redondance

Thyphoon · Message par **Thyphoon** » ven. 13/nov./2009 6:47

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

kelebrindae · Message par **kelebrindae** » ven. 13/nov./2009 9:45

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)

Thyphoon · Message par **Thyphoon** » ven. 13/nov./2009 9:53

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

kelebrindae · Message par **kelebrindae** » ven. 13/nov./2009 9:59

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.

Thyphoon · Message par **Thyphoon** » ven. 13/nov./2009 10:50

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 !

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

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

Thyphoon · Message par **Thyphoon** » ven. 13/nov./2009 19:14

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,

PureBasic

Créer une liste alléatoire sans redondance

Créer une liste alléatoire sans redondance

Re: Créer une liste alléatoire sans redondance

Re: Créer une liste alléatoire sans redondance

Re: Créer une liste alléatoire sans redondance

Re: Créer une liste alléatoire sans redondance

Re: Créer une liste alléatoire sans redondance

Re: Créer une liste alléatoire sans redondance

Re: Créer une liste alléatoire sans redondance