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

WRInaute accro
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 :(
 
WRInaute passionné
ç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
 
WRInaute passionné
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)
 
WRInaute accro
perso, je ferais un array() qui contiendrait 500 fois jean et 1000 foi paul, un petit shuffle () et tu prends le 1° du tableau
 
WRInaute accro
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
 
WRInaute accro
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 ;)
 
Nouveau WRInaute
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 :)
 
WRInaute discret
Salut?
Et en sql ça ne serait pas possible de faire ça, avec quelque chose du genre?

Code:
select * from hamster where valide=1 order by rand(),force desc limit 1
 
WRInaute accro
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.
 
WRInaute passionné
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).
 
WRInaute passionné
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
 
WRInaute accro
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.
 
WRInaute accro
moktoipas a dit:
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" ;)
 
WRInaute passionné
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 :eek: )
 
WRInaute passionné
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)
 
WRInaute accro
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.

Code:
-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é.
 
WRInaute passionné
blman ce que veux dire Leonick c'est que j'explique comme un manche :D

A cas ou certain le voudrais, voici le code:
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;
 
Nouveau WRInaute
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:
Code:
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...)

:)
 
WRInaute passionné
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.
 
Nouveau WRInaute
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.
 
WRInaute passionné
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 :D :D
 
WRInaute passionné
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
 
WRInaute passionné
[LIEN MORT]



Code:
$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>";
}
 
WRInaute passionné
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
 
WRInaute passionné
ça marche plutôt bien, je n'ai pas pu m'empêcher de le rogiser
:D

Code:
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
 
WRInaute passionné
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.
 
WRInaute passionné
oups

comme ça au reveil c'est un peu agressif :D

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

Code:
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]
 
Discussions similaires
Haut