Comments on: Récupérer des éléments d’une liste au hasard avec pondération en python http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/ Du code, du cul Sat, 07 Nov 2015 11:08:18 +0000 hourly 1 http://wordpress.org/?v=4.1 By: Gaga http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1819 Wed, 12 Sep 2012 18:50:17 +0000 http://sametmax.com/?p=2034#comment-1819 Salaud*, pas salop ;)

]]>
By: Réchèr http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1749 Fri, 07 Sep 2012 22:22:34 +0000 http://sametmax.com/?p=2034#comment-1749 De rien m’sieur Maxou. C’est fait avec amour et avec du beurre.

La solution de GM marche bien aussi. Plus rapide à l’exécution, mais plus consommateur de mémoire. On retrouve l’éternel choix cornélien du programmeur : le temps ou la mémoire ?

Bon de toutes façons, Corneille, il est tellement mort que maintenant, c’est un chanteur.

]]>
By: GM http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1748 Fri, 07 Sep 2012 19:36:33 +0000 http://sametmax.com/?p=2034#comment-1748 Pour éviter la boucle de tirage de Recher, on peut mixer les deux solutions :

1) Construire le ruban sous forme de liste pondérée :
items = [‘server1′] * 10 + [‘server2′] * 45 + [‘server3′] * 34
2) Ne pas mélanger
3) Choisir un nombre x au hasard entre 0 et 88, et retourner items[x].

Avec un yield au bon endroit, ça doit marcher.

]]>
By: Max http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1747 Fri, 07 Sep 2012 19:01:49 +0000 http://sametmax.com/?p=2034#comment-1747 merci François mais je n’aime pas trop dépendre de tout un tas de libs, surtout pour de si petits bouts de codes, après on se retrouve avec des tas de dépendances parfois plus compatibles lors de mises à jour.
Je vais quand même voir de plus près cette lib pour ce qu’elle apporte d’autre.

]]>
By: Max http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1746 Fri, 07 Sep 2012 18:59:15 +0000 http://sametmax.com/?p=2034#comment-1746 merci recher pour ton code ça fait plaisir ^^

En effet c’est bourrin ce que j’ai fais, pour ça que je demandais une idée alternative et mon crie de désespoir a fini par carresser le cil de ton oreille interne, Amen…

Je suis d’accord pour la confusion en première partie, c’est effet l’espace disque occupé en %, pour ça que je fais un 100-weight ensuite.

Merci en tous cas pour ton code, je le rajoute en edit pour pas le perdre ;)

]]>
By: Kontre http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1745 Fri, 07 Sep 2012 17:01:05 +0000 http://sametmax.com/?p=2034#comment-1745 D’accord avec l’algo de Recher. On doit même pouvoir faire une recherche par dichotomie pour aller un peu plus vite dans le “ruban”.
C’est au passage la manière de faire un tirage avec une loi de probabilité quelconque.

]]>
By: Xavier Combelle http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1744 Fri, 07 Sep 2012 16:30:02 +0000 http://sametmax.com/?p=2034#comment-1744 En fait je pense que c’est plutot O(ln(N)) où N est le nombre d’élément (recherche binaire)

]]>
By: Sam http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1743 Fri, 07 Sep 2012 16:27:27 +0000 http://sametmax.com/?p=2034#comment-1743 Y a la bouton “force coloration” qui pallie à ça.

Pour le reste, je laisse l’auteur du code répondre ^^

]]>
By: Xavier Combelle http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1742 Fri, 07 Sep 2012 16:27:17 +0000 http://sametmax.com/?p=2034#comment-1742 L’avantage de la méthode scipy c’est que distrib.rvs() est en O(1) si elle est bien foutue

]]>
By: Recher http://sametmax.com/recuperer-des-elements-dune-liste-au-hasard-avec-ponderation-en-python/#comment-1741 Fri, 07 Sep 2012 16:24:56 +0000 http://sametmax.com/?p=2034#comment-1741 Première remarque :

il y a une légère confusion sur les termes “place_restante” et “poids en %”.

J’ai vaguement l’impression que la valeur dans la liste initiale représente la place occupée, et non pas la place restante. Si ce n’est pas ça, comment expliquer que le nombre d’élément ajouté dans la liste items est “100-weight”, alors que ça devrait être, tout simplement, “weight”.

Deuxième remarque :

Permettez-moi de trouver ça bourrin. Si il y a, ne serait-ce que 20 serveurs, on peut très vite avoir une liste “items” de plusieurs centaines d’éléments. Un shuffle là-dessus, ce n’est pas anodin, et ça prend un certain temps. Tout ça pour choisir des trucs au hasard. Hem…

Pour Blarg, (mon superbe jeu vidéo), j’ai eu besoin de générer des nombres aléatoires pondérés. Je l’ai fait de la manière suivante.

– Initialement, on a une liste de coefficient. Par exemple : (7, 3, 0, 20, 5). Cela signifie qu’on veut générer un nombre aléatoire entre 0 et 4, avec les poids de la liste. (Dans notre exemple, le nombre 2 ne sortira jamais, puisqu’il a un poids de 0).

– L’idée, c’est de voir cette liste comme un grand ruban, avec des morceaux de taille différente mis bout à bout. On choisit un point au hasard sur le ruban, on regarde à quel morceau il appartient, et ça donne le résultat.

– On calcule la somme des coefs. Ca vaut 35. Cela correspond à la taille du ruban.

– On choisit un nombre au hasard, sans pondération, entre 0 et 34. Cela correspond au point du ruban que l’on a choisi. Mettons qu’on obtienne 15.

– On avance dans le ruban, jusqu’à trouver le morceau appartenant au point. Ca se fait avec une boucle.

— curseur = 15. morceau courant = le premier. taille du morceau = 7.
— 15 > 7. Ce n’est pas le bon morceau. curseur = 15 – 7 = 8
— curseur = 8. morceau courant = le 2ème. taille du morceau = 3
— 8 > 3. Ce n’est pas le bon morceau. curseur = 8 – 3 = 5
— curseur = 5. morceau courant = le 3ème. taille du morceau = 0
— 5 > 0. Ce n’est pas le bon morceau. curseur = 5 – 0 = 5
— curseur = 5. morceau courant = le 4ème. taille du morceau = 20
— 5 <= 20. C'est le bon morceau.

– On renvoie la valeur 4.

Il suffit, ensuite, de choisir le serveur correspondant à l'index 4.

On recommence le même process autant de fois que nécessaire. Pas besoin de module de statistiques compliqué, pas besoin de créer une grande liste. Les seules actions lentes, c'est le random.randrange (mais c'est un peu inévitable quand on veut choisir des trucs au hasard), ainsi que la boucle pour avancer dans le ruban.

Si on est puriste, on classe la liste de coef par ordre décroissant. Cela permet de faire moins d'itérations dans la boucle, à chaque tirage. On a plus de chances de tomber immédiatement sur le morceau de ruban choisi. Il faut juste garder quelque part une correspondance entre la liste de coef initiale et la liste de coef classée.

Et voici le pastebin "kivabien".
http://is.gd/b3GbA4

Votre biniou de 0bin n'a pas détecté que c'était du python, et ne me l'a pas syntaxiquement coloré. C'est bien dommage. Tant pis, vous vous abîmerez les yeux !

]]>