Une méthode qui vaut ce qu’elle vaut mais qui sert pas mal.
Cas de figure, on veut uploader du contenu qui sera mis à disposition d’utilisateurs sur 3 serveurs sur lesquels il ne reste pas la même place…
on peut utiliser une commande ssh pour récupérer la place sur les serveurs par exemple et mettre le résultat dans une liste:
[[place_restante, nom_du_serveur]] servers = [['10','server1'],['45','server2'],['34','server3']] |
La logique voudrait qu’on balance le contenu sur tous les serveurs mais surtout sur le 1 car il a beaucoup de place le salop mais qu’il faut pas tout mettre dessus car on va bouffer toute sa bande passante lors des downloads du contenu alors qu’on a 2 autres serveurs qui branlent rien ou presque…
def w_choice(lst, nb=2): """ weighted choice give it a list as this: [[45, 'item1'], [12, 'item2'],[88, 'item3']] nb= Number of items to return """ items = [] w_items = [] # on récupère tous les serveurs de la liste et leur "poids" (place restante en % par ex) for weight, item in lst: # on créé une liste dans laquelle on multiplie le nom du serveur par son poids, ex si server1 a 4 de poids on aura 4 éléménts server1 for x in xrange(100-weight): items.append(item) # on secoue mais on frappe pas random.shuffle(items) # on récupère x serveurs sur lesquel on uploadera le contenu for item in items: if item not in w_items: w_items.append(item) if len(w_items)==nb: break return w_items |
ci-dessous un petit test pour voir que ça marche:
servers = [['10','server1'],['45','server2'],['34','server3']] items = {} for i in xrange(1000): lst = w_choice(servers) for item in lst: items.update({item:items.get(item, 0)+1} ) print items |
On obtient:
{'server1': 414, 'server2': 273, 'server3': 313}
Ici server1 sort le plus souvent(414 fois) car la place occupée sur son disque est de 10%, logique qu’on lui envoie plus souvent du contenu histoire de le remplir.
Je ne trouve pas ma fonction spécialement élégante ceci-dit, si certains ont mieux à proposer qu’ils se fassent entendre ;)
Version très vite faite, j’ai pas mal de boulot là…
http://pastebin.com/mWeKGHiq
mais qui donne l’esprit
Je fais un code qui répond complètement au besoin plus tard si ça intéresse.
C’est bon de savoir que scipy a une fonction pour ça toute faite (c’est logique en même temps).
Par contre, je sais pas si installer NumPy et Scipy juste pour ça, c’est pas un peu lourd VS le bricolage de max.
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 !
L’avantage de la méthode scipy c’est que distrib.rvs() est en O(1) si elle est bien foutue
Y a la bouton “force coloration” qui pallie à ça.
Pour le reste, je laisse l’auteur du code répondre ^^
En fait je pense que c’est plutot O(ln(N)) où N est le nombre d’élément (recherche binaire)
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.
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 ;)
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.
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.
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.
Salaud*, pas salop ;)