Discussion :

[progcyb]

Bonjour,

Je fais un petite algorithme très simple, mais j'essaie de le faire le plus "performant".

La question est très simple, je pars d'une position, 0,1,2 ou 3, et la position d'après peut être 0,1,2,ou 3 SAUF la position actuelle. Je m'exprime mieux :

Soit la position de départ 0,
le coup d'après, je peux avoir 1,2 ou 3.
Mettons que ce soit 2, le coup d'après, je peux 0,1 ou 3.

J'ai pensé utiliser le module random, et dedans, random.choice sur la liste positions qui contient les valeurs 0,1,2,3... Mais comment je fais pour éviter la valeur actuelle ? Il n'y a pas un random.choice(positions).but(n) ou quelque chose du genre ?

Sinon, ce que j'ai fait, c'est d'enregistrer une variable temporaire (temp) avec la valeur tirée au sort. Si celle-ci est égale à la valeur de référence, je recommence. Mais en terme de performance, je fais potentiellement 1/4 de sélection aléatoire en trop, donc...
Comment contourner ce problème pour faire au plus efficace ?

Je voudrais pouvoir simuler un grand nombre de lancés, et c'est une très bonne occasion pour moi de peaufiner cela.

Si une bonne âme pouvait me mettre sur la voie ou m'aider, ce serait vraiment super super super gentil, merci infiniment d'avance !

[Julien N]

Salut,

Voici quelque chose qui pourrait te dépanner:

Code :

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

1
2
3
4
5
6
7
8
9
10
# -*- coding: utf-8 -*-
 
import numpy as np
 
lst = np.arange(4)
 
val = 0
for i in range(20):
    val = [elem for elem in lst if elem != val][np.random.randint(0,len(lst)-1)]
    print val

Dans ce code, val c'est la valeur que tu cherches. Je génère une liste (array en fait) nommé lst à l'aide de numpy. cette liste est ici:

Code :

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

lst = [0,1,2,3]

A chaque itération de la boucle for je créé une nouvelle liste contenant tout les éléments de lst excepté la valeur val. De cette nouvelle liste je récupère l'élément à un indice aléatoire qui vient écraser ma valeur.

Bon c'est pas très optimisé, mais ça marche!

Ju

[progcyb]

Bonjour,

merci pour cette réponse,

en effet, je me suis dit aussi qu'une autre solution consistait à recréer une liste sans l'élément sélectionné à chaque itération.
Comme je suis un peu une nioub en python, je ne connaissais pas numpy...

Je vais chercher dans cette direction, je crois.

J'aurais aimé pouvoir comparer les "performances" (je sais, c'est un code rikiki, mais c'est à titre d'exercice, quoi) entre le fait de recréer une liste à chaque itération avec le fait de faire un random.choice de trop dans 1/4 de cas.
Mais je n'ai pas du tout les compétences pour le faire ^^

Merci à toi !

[Julien N]

J'ai écris un truc un peu à l'arrache (comme souvent d'ailleurs). J'ai utilisé le module numpy sans trop le faire non plus.

Numpy est un module très utilisé pour faire des calculs en python. Il gère très bien tout ce qui est calcul vectoriel et matriciel. Dans le code que j'ai écris on pouvait tout à fait s'en passer.

Pour faire un benchmark, je te conseil d'encapsuler tes différents méthodes dans des fonctions distinctes, puis de les appeler un grand nombre de fois. Il faut qu'elles traitent la même chose.

Code :

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

1
2
3
4
5
def random_number(lst,N=20):
    val = 0
    for i in range(int(N)):
        val = [elem for elem in lst if elem != val][np.random.randint(0,len(lst)-1)]
        #print val

Calculer le temps d'exécution de la fonction peut se faire à l'aide de la méthode clock() du module time:

Code :

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

1
2
3
4
5
6
import time
 
lst = np.arange(400)
t0 = time.clock()
random_number(lst, 100000)
print 'Function elapsed in %f s' % (time.clock()-t0,)

En fonction de l'OS sur lequel tu fais cet exercice, ce n'est pas forcément clock() qu'il faut utiliser. C'est le cas pour Windows.

Chez moi, la fonction en question à pris 7.84s pour générer 100.000 nombres aléatoires provenant d'une liste de 400 entiers. C'est pas top.

Ju

[__dardanos__]

Salut,
Pour une liste de 4 éléments, je suis pas sûr que le gain de temps avec NUMPY soit mesurable. Ça se fait simplement en PYTHON :

Code :

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

idx = choice( a_list[:idx] + a_list[idx+1:] )

Pour l'exemple :

Code :

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

1
2
3
4
5
6
7
from random import choice
a_list, idx = range(4), 0
for _ in range(10):
    interm = a_list[:idx] + a_list[idx+1:]
    new = choice(interm)
    print('Current : {}, Choice in : {}, New : {}'.format(idx,interm,new))
    idx = new

Code :

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

1
2
3
4
5
6
7
8
9
10
Current : 0, Choice in : [1, 2, 3], New : 3
Current : 3, Choice in : [0, 1, 2], New : 0
Current : 0, Choice in : [1, 2, 3], New : 2
Current : 2, Choice in : [0, 1, 3], New : 1
Current : 1, Choice in : [0, 2, 3], New : 2
Current : 2, Choice in : [0, 1, 3], New : 0
Current : 0, Choice in : [1, 2, 3], New : 3
Current : 3, Choice in : [0, 1, 2], New : 0
Current : 0, Choice in : [1, 2, 3], New : 3
Current : 3, Choice in : [0, 1, 2], New : 1

[Julien N]

Code :

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

idx = choice( a_list[:idx] + a_list[idx+1:] )

Je pense que c'est à ça (ou presque) que pensait le PO initialement. Je ne connaissait pas choice, c'est beau!

Ju

[progcyb]

ok, ok... hum.

Alors en gros, puisque j'aime comprendre par moi-même, j'ai écrit deux codes différents sans numpy, en générant un simple tableau avec un for ... in range().

Je suis sous linux (mint, dérivé debian), et j'ai essayé clock mais ça n'a pas l'air bien probant pour le moment.
...

Jusque là, j'ai compris l'idée en tout cas

edith : oh mais moi non plus je ne connaissais pas (évidemment) choice !

edith2 : heu... Je viens de comprendre... Et puis clock() ça marche.

Merci !!

[progcyb]

heuuuuuu... m'excuse de dérange encore, mais en fait :

idx = choice( a_list[:idx] + a_list[idx+1:] )
=>"TypeError: unsupported operand type(s) for +: 'range' and 'range'"
j'imagine que c'est une question de version de Python ?...

[josmiley]

j'ferai une rotation ...

Code :

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

1
2
3
4
5
6
7
8
9
10
>>> from random import randint
>>> ls = list("ABCDEFGHIJ")
>>> ls
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
>>> choix = ls.pop(randint(0,len(ls)-2))
>>> choix
'F'
>>> ls.append(choix)
>>> ls
[ 'A', 'B', 'C', 'D', 'E', 'G', 'H', 'I', 'J', 'F']

enfin pas vraiment une rotation, mais mettre l'élément sélectionné à la fin de la liste.
niveau perf ça ne doit pas être génial.

sinon, si il n'y a pas de doublon dans la liste, tu fais des set()

Code :

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

choix = random.choice(list(set(ma_liste).difference(set(choix))))