[php/MySQL] Tirage au sort avec pondération

[HawkEye]

Hello,

Je cherche à faire un tirage au sort, avec une condition et une pondération basée sur un score.

Exemple: Choisir un hamster gagnant parmi ceux qui ne sont pas éliminés, et en les favorisant proportionnellement à leur force.

Les données seraient organisées comme suit:

[ nom_joueur | nom_hamster | valide | force ]

--> (jean, ham_star, 1, 500)
--> (paul, hemmster, 1, 1000)
--> (marc, lobster, 0, 1800)

--> le hamster de marc ne peut pas gagner (il est éliminé)
--> le hamster de paul a 2x plus de chances d'être tiré au sort...

Je ne trouve pas de solution simple

 

[oli004]

ça ne fonctionne pas ça :

soit x la plus grande force

if rand(1,x) < y {

y gagne ;

}

else {

x gagne ;

}


? :roll:

bien sur, préalablement, tu fais un select sur ta base de deux id aléatoire dont eliminé est à 0

 

[moktoipas]

Moi je le ferai en duex requettes
1 pour recureper la liste des hamster dansl a courses
1 pour recuperer la somme des forces des hamster dans la course.

la seconde renvoie 1500 donc

et tu choisi un nombre au pif entre 0 et 1500

ensuite, tu parcours (dans n'importe quel ordre, osef) le resultat de la requete des hamster qui sont dans la course.

a chaque hamster( enfin) ligne) tu soustrait de ton random la force du hamster.

Quand juste après ta soustraction tu a ton random qui fait 0 ou est négatif, c'est que tu est tombé sur le hamster gagnant

(moi je prefere les gerbilles)

 

[Leonick]

perso, je ferais un array() qui contiendrait 500 fois jean et 1000 foi paul, un petit shuffle () et tu prends le 1° du tableau

 

[HawkEye]

oli004, j'aurais du préciser qu'il peut y avoir 100 hamsters dans la course... pas obligatoirement 2

moktoipas, ton idée m'a l'air bien. Aucun souci pour les deux requêtes, mais c'est la suite qui va me poser problème...

Je t'envoie un petit MP pour la partie "php"

Merci

 

[blman]

Moi je ferais pareil que Leonick si tu n'a pas trop d'enregistrement et pareil que moktoipas si tu en a beaucoup

PS : HawkEye, laisse Moktoipas tranquille, il a déjà assez de boulot comme ça

 

[auboutdufil]

Moi je pondèrerai sur une échelle de 1 à 10 les forces :
--> (jean, ham_star, 1, 500, 0)
--> (paul, hemmster, 1, 1000, 1)
--> (marc, lobster, 0, 1800, 2)

Ensuite je fais un tableau pondéré :
(lobster, lobster, hemmster)

[note: il n'y a pas ham_star car il a une note de 0, et il y a 2 fois lobster parce qu'il a une note de 2)


et je fais un joli random dessu

 

[athoms]

Salut?
Et en sql ça ne serait pas possible de faire ça, avec quelque chose du genre?

select * from hamster where valide=1 order by rand(),force desc limit 1

 

[Leonick]

non, je crois que la seule solution semble être celle que j'ai donnée. Si on effectue un tri selon un 2° critère (genre la force), que j'ai force 2 ou 2000, je serais juste devant celui qui a une force 1 et j'aurais toujours 1 chance sur 2 d'être tiré au sort.

 

[moktoipas]

Non, ta solution n'est pas la seule ^^


La mienne est tout a fait valable et évite de faire un tri sur un tableau de millions d'entrées (1000 hamster de force 1000 et on se retrouve avec un méga tableau).

 

[rog]

j'ai l'impression qu'aucune des deux solutions ne convient

ça marche pas avec un tableau de 3
lol

1 - 500
2 - 1000
3 - 2000

= 3500

si on divise par 500, on obient 7
sur 7 affichages on devrait avoir
une fois le 1
deux fois le 2
quatre fois le 3

à moins trouver une fonction mysql qui correspond à cet algo, ça va être un peu plus compliqué à mettre en place que cela ne le paraît

rog

 

[blman]

La solution de Moktoipas fonctionne ainsi, si j'ai tout bien compris.

Ma table :
Tibo -> force 500
Cyril -> force 1000
Yves -> force 100
Jean -> force 2000 (balaise Jean)
Bruno -> force 500

Total des forces : 4100

Test 1 :
-------------------------------------------------------
Nbre prix au pif dans l'interval 0-4100 -> allé au hasard 4000 (voir http://fr3.php.net/rand)

Ensuite, on mélange le tableau des hamsters pour faire un tri aléatoire ( http://fr.php.net/shuffle )
Jean -> 4000 - 2000 = 2000 -> perdu
Cyril -> 2000 - 1000 = 1000 -> perdu
Tibo -> 1000 - 500 = 500 -> perdu
Bruno -> 500 - 500 = 0 -> gagné !!!

Test 2 :
-------------------------------------------------------
Nbre prix au pif dans l'interval 0-4100 -> allé au hasard 2000

Ensuite, on mélange le tableau des hamsters pour faire un tri aléatoire ( http://fr.php.net/shuffle )
Bruno -> 2000 - 500 = 1500 -> perdu
Tibo -> 1500 - 500 = 1000 -> perdu
Jean -> 1000 - 2000 = -1000 -> gagné !!!


Et oui, effectivement, avec cette solution, on consomme moins de ressources sur un nombre important d'enregistrements que de multiplier le nombre d'entrées d'un tableau. Et plus on a de force, plus on a de chance de gagner.

 

[HawkEye]

Non, ta solution n'est pas la seule ^^


La mienne est tout a fait valable et évite de faire un tri sur un tableau de millions d'entrées (1000 hamster de force 1000 et on se retrouve avec un méga tableau).

C'est aussi la crainte que j'avais

Disons qu'il n'y a qu'une dizaine de hamsters pour l'instant, et que leur force va de 50 à 6500... mais ces deux valeurs sont haussières :roll:

J'ai appliqué la solution de moktoipas (désolé blman, j'te l'ai pris quelques minutes ). Merci à tous.

Note: comme certains l'ont compris, il ne s'agit pas de hamsters ou de force, mais bien de comptes AdSense et de "mérite"

 

[moktoipas]

c'est meme pas la peine de faire un shuffle.

meme bruno, qui est a la fin du tableau a des chance de gagner, il gagnera quand le random sera entre 3600 et 4100.
sa proba est donc de (4100-3600)/4100= 500/4100

en fait c marche peu importe l'ordre des hamster (jean est un hamster )

 

[moktoipas]

Note: comme certains l'ont compris, il ne s'agit pas de hamsters ou de force, mais bien de comptes AdSense et de "mérite"

moi j'avais pas compris


je pensais que tu voulais faire un jeu de paris en ligne pour les enfants :$ (véridique)

 

[blman]

Et oui, Jean est même un gros hamster

Plus sérieusement, oui, effectivement il n'y a pas besoin de faire le shuffle, donc en fait, c'est super simple à mettre en place.

-1-|-----2-----|---3---|------------4----------------|------5--------|-6-|-7-|-8-|

La règle représente la somme des forces

Le joueur 4 a plus de chance d'être tiré que les joueurs 1,6,7 ou 8

Si on tire un nombre aléatoire, l'utilisateur qui a l'interval le plus grand (celui qui a le plus de force) a logiquement, plus de chance d'être sélectionné.

 

[Leonick]

La solution de Moktoipas fonctionne ainsi, si j'ai tout bien compris.

effectivement, je n'avais pas compris sa solution. Elle est bien moins gourmande que la mienne et produit du pseudo aléatoire.

 

[blman]

Ce n'est pas du pseudo aléatoire, c'est carrément de l'aléatoire.

 

[moktoipas]

blman ce que veux dire Leonick c'est que j'explique comme un manche

A cas ou certain le voudrais, voici le code:

$query = mysql_query("SELECT SUM(force) FROM `hamsters` WHERE `valide` = 1");
$lignederesultat=mysql_fetch_array($query);
$forcetotaledeshamster=$lignederesultat[0];


$monrandom=rand  (0,$forcetotaledeshamster); //attention fonction un peu limitée sous windows ( elle peut pas faire plus que 32768 ). Mais il existe plein d'autre

$query = mysql_query("SELECT `hamster_name`, `force` FROM `hamsters` WHERE `valide`= 1");


$jaitrouvemongagnant=false;
//tant quej 'ai pas trouvé mon gagnant et que mon tableau sql est pas fini
while (!($jaipasencoretrouvemongagnant) && $ligendehamster=mysql_fetch_array($query))
{
$monrandom-=$ligendehamster['force'];//je fait ma soustraction

if ($monrandom<=0) //quand je deviens négatif ou nul
{
$jaitrouvemongagnant=true;//c'est qu ej'ai mon gagnant
$gagnant=$ligendehamster['hamster_name'];
}

}


echo $gagnant;

 

[HawkEye]

je pensais que tu voulais faire un jeu de paris en ligne pour les enfants :$ (véridique)

Rhaaa m*****rde... un nouveau projet :mrgreen:

 

[dd32]

je pensais que tu voulais faire un jeu de paris en ligne pour les enfants :$ (véridique)

Rhaaa m*****rde... un nouveau projet :mrgreen:

Je vois tout à fait de quoi tu veux parler :mrgreen:

 

[moktoipas]

Je vois tout à fait de quoi tu veux parler :mrgreen:

Tu fais des courses de Panda ??

 

[blman]

Je vois tout à fait de quoi tu veux parler :mrgreen:

Tu fais des courses de Panda ??

Nan, elle fait les courses en Panda, c'est pas pareil, c'est moins glamour

 

[Leonick]

Note: comme certains l'ont compris, il ne s'agit pas de hamsters ou de force, mais bien de comptes AdSense et de "mérite"

l'alternance de code adsense, comme sur WRI ?

 

[HawkEye]

Note: comme certains l'ont compris, il ne s'agit pas de hamsters ou de force, mais bien de comptes AdSense et de "mérite"

l'alternance de code adsense, comme sur WRI ?

Oui

 

[ndavoust]

ok c'est tout simple :

tu as un tableau avec tes hamsters et tes poids :

hamster1 2
hamster2 3
hamster3 0 (elimine)
hamster4 1
hamster5 7

tu rajoute une troisième colonne avec la somme des poids précédents plus le poids du hamster:

hamster1 2 2
hamster2 3 5 (=2+3)
hamster3 0 5 (=2+3+0)
hamster4 1 6 (=2+3+0+1)
hamster5 7 13 (=2+3+0+1+7)

tu tire au hasard entre 1 et 13 (compris) => $rand

Ca te demande un autre champs dans ta table, mais ensuite le tirage au sort est hyper facile en sql:

un truc du style:

select hamster_nom 
from hamsters 
where sommepoids>$rang 
          AND poids<>0
order by poids desc 
limit 1

Je l'utilise pour tirer des bannières pub au sort avec des poids différents

L'avantage, c'est que la reponse de la bdd ne fait qu'une ligne (donc hyper rapide), il n'y a pas de traitement par derriere (parcours de tableau...)

 

[moktoipas]

c'est la solution que j'ai proposée
je l'ai implémenté différemment

 

[ndavoust]

je viens de l'editer pour montrer ses quelques avantages ;-)

 

[moktoipas]

inconvénient, il faut réécrire toute la BDD chaque fois qu'un hamster change de force ou est "hors concours"

et en mysql les écritures sont plus longues que les lecture.

 

[ndavoust]

vrai, tout cela dépend des utilisations... en ce qui concerne les bannières de pub, je change pas les poids souvent donc bon.

ceci dit, pour rester dans le cas du hamster, vu que tu perd ton tableau a chaque chargement de page pour le recréer, et que tout changement de poids te fait aussi recharger une page et réinscrire ta base, je pense qu'on est dans le kif kif.

Dans le cas ou on a une lecture par ecriture (cas d'un joueur unique faisant monter et descendre le poids de son hamster), ta solution est meilleure.

Dans le cas ou nb lectures >> nb ecritures (cas de beaucoup de tirages au sort pour pas beaucoup de changement de poids respectifs), ma solution l'emporte.

 

[moktoipas]

ben le mysql c une ecriture disque...le table php c'est une ecriture ram, c'est pas du tout pareil en terme de perfs !
(et en cas de modification de force, j'ai qu'ne ligne a changer)

lui il change souvent les force des hamster soit dit en passant (en fonction de l'activité des hamsters sur le site (a) )
donc je pense que c'est mieux.

mais effectivement pour un cas ou on change pas souvent la force des hamsters, c'est mieux de plus utiliser mysql

il faudrai qu'il s'ammuse a faire des tests de perfs

 

[rog]

bizarre

je dois être le seul à penser que c'est nimporte quoi

lol

rog

 

[moktoipas]

lol je t'assure que ca marche

 

[rog]

1 - 500
2 - 1000
3 - 2000

= 3500

si on divise par 500, on obient 7
sur 7 affichages on devrait avoir
une fois le 1
deux fois le 2
quatre fois le 3

on pourrait facilement coder un proof of concept :
tu rajoutes un champs ou tu incremente les selections et tu lances une boucle de 70, si tu obtiens

1 - 500 [10]
2 - 1000 [20]
3 - 2000 [40]

tu obtiendras aussi mon respect et toutes mes excuses

rog

 

[moktoipas]

[LIEN MORT]

$hamster[0]=500;
$hamster[1]=1000;
$hamster[2]=2000;

function poc($hamster)
{
	$forcetotaledeshamster=3500;
	$monrandom=rand  (0,$forcetotaledeshamster); 
	$a=0;
	$trouve=false;
	while (!$trouve)
	{
		$monrandom-=$hamster[$a];
		if ($monrandom<=0)
		{
			$trouve=true;
			$result=$a;
		}
		$a++;
	}
	return $result;
}

$result[0]=0;
$result[1]=0;
$result[2]=0;
for ($aa=0;$aa<700;$aa++)
{
	$result[poc($hamster)]++;
}


foreach ($result as $in=>$val)
{
	echo $in." - ".$hamster[$in]." [".$val."]<br>";
}

 

[rog]

lol

je n'ai d'autre choix que de m'incliner, bravo et j'en profite pour m'excuser

j'avais pas vu la proportionnalité dans l'equation

tu fais comment si il y a deux hamster de même force ?

rog

 

[moktoipas]

bah rien de spécial, je change la force du hamster, ca change la somme des force et l'algo change les proportions tout seul

 

[rog]

ça marche plutôt bien, je n'ai pas pu m'empêcher de le rogiser

error_reporting(E_ALL);
#
$hamster[0]=500; 
$hamster[1]=1000; 
$hamster[2]=2000; 
$hamster[3]=2000; 
$hamster[4]=500; 

define('FORCE_HAMSTER',array_sum($hamster));
#
function poc($hamster){
# 
$monrandom = rand(0,FORCE_HAMSTER); 
$a = 0; 
$trouve = false; 
# 
while(!$trouve) 
   	{ 
    $monrandom -= $hamster[$a]; 
	#
    if ($monrandom <= 0) 
    	{ 
        $trouve = true; 
        $result = $a; 
      	} 
	$a++; 
	} 
return $result; 
} 
#
$result = array();
#
for($i = 0; $i < count($hamster); $i++)
	{
	$result[$i] = 0;
	}
#
for ($a = 0; $a < 800; $a++) 
	{ 
 	$result[poc($hamster)]++; 
	} 
#
foreach ($result as $in=>$val) 
	{ 
   	echo $in." - ".$hamster[$in]." [".$val."]<br>"; 
	}

rog

 

[moktoipas]

ATTENTION

J'ai remarqu" que j'avias fait une erreur dans mon script, il y a un leger biais en faveur du premier hamster.

mon random devrai commencer à 1, pas 0.

 

[rog]

oups

comme ça au reveil c'est un peu agressif

ce qui me gênait dans ce concept c'est la totale dependance de la pertinence de la fonction rand(), le poc est très bien mais le comportement de la fonction à l'interieur d'une boucle n'est pas forcement le même que lorsqu'elle est lancée à intervalles irréguliers

j'ai donc fait un poc qui randomise les intervalles

error_reporting(E_ALL);
#
$sleep = rand(1,3);
sleep($sleep);
#
session_start();
#
if(!isset($_SESSION['loop']))
	{
	$_SESSION['hamster'][0] = 500; 
	$_SESSION['hamster'][1] = 1000; 
	$_SESSION['hamster'][2] = 2000; 
	$_SESSION['hamster'][3] = 2000; 
	$_SESSION['hamster'][4] = 500; 
	#
	$_SESSION['result'][0] = 0;
	$_SESSION['result'][1] = 0;
	$_SESSION['result'][2] = 0;
	$_SESSION['result'][3] = 0;
	$_SESSION['result'][4] = 0;
	#
	$_SESSION['FORCE_HAMSTER'] = array_sum($_SESSION['hamster']); 
	$_SESSION['loop'] = 0;
	}
#
$_SESSION['loop']++;
#
$_SESSION['result'][poc()]++; 
#
$display = "<li> boucle n° : ".$_SESSION['loop'];
#
foreach ($_SESSION['result'] as $in=>$val) 
	{ 
   	$display .= "<br> hamster n° : ".($in + 1)." - force : ".$_SESSION['hamster'][$in]." cumul des requêtes : {$val} - derivation : ".pertinence($in)."<br>"; 
	} 
#
if($_SESSION['loop'] < 6000)
	{
	$display .= ("<SCRIPT LANGUAGE=\"JavaScript\"> document.location.href=\"".$_SERVER['PHP_SELF']."\"</script>");
	}
echo($display);
flush();
#
#	counter reset
#session_destroy();
#
##############################################################################################################
function poc(){
##############################################################################################################
$monrandom = rand(1,$_SESSION['FORCE_HAMSTER']); 
$a = 0; 
$trouve = false; 
# 
while(!$trouve) 
   	{ 
    $monrandom -= $_SESSION['hamster'][$a]; 
	#
    if ($monrandom <= 0) 
    	{ 
        $trouve = true; 
        $result = $a; 
      	} 
	$a++; 
	} 
return $result; 
} 
##############################################################################################################
function pertinence($index){
##############################################################################################################
#
$coef = $_SESSION['FORCE_HAMSTER'] / $_SESSION['loop'];
# cumul hamster réaligné
$realign = $_SESSION['result'][$index] * $coef;
#
$pertinence = round($realign / $_SESSION['hamster'][$index],2);
#
return $pertinence;
}
##############################################################################################################

la derivation de pertinence n'excede pas 20%

edit : a 1000 la derivation descend au dessous de 10%
re edit : resultat sur 6000 requêtes

boucle n° : 6000

hamster n° : 1 - force : 500 cumul des requêtes : 488 - derivation : 0.98
hamster n° : 2 - force : 1000 cumul des requêtes : 1003 - derivation : 1
hamster n° : 3 - force : 2000 cumul des requêtes : 1978 - derivation : 0.99
hamster n° : 4 - force : 2000 cumul des requêtes : 2057 - derivation : 1.03
hamster n° : 5 - force : 500 cumul des requêtes : 474 - derivation : 0.95

pour obtenir une derivation de pertinence de 0 on devra tenir compte d'une statistique de selection dans l'algo

rog[/quote]