选择的概率随机进入 [英] Select random entry with probability
问题描述
说我有存储在数据库中的以下信息：
Say I have the following information stored in a database:
User Points
A 2000
B 1000
我想选择随机赢家基于点的量的概率。在这种情况下，由于共3000点是，A已被选定的67％的机会和B有33％的机会。
I want to select a winner at random with a probability based on the amount of points. In this case, since there's a total of 3000 points, 'A' has a chance of 67% to be selected and 'B' has a 33% chance.
什么是选择使用PHP（通过计算概率来选择获胜者）的赢家的最有效方法是什么？请注意，用户玩的量是不固定的并可以高达大量（因此它应该计算每个用户的，而不是固定在A和B）。
What is the most efficient way to select the winner using PHP (from calculating probabilities to selecting the winner)? Note that the amount of users playing is not fixed and can range up to a large amount (so it should calculate 'each user' rather than fix on A and B).
我一直在玩弄潜在的解决方案，但还没有计算出来。我很想听听您的解决方案！
I've been playing around with potential solutions but have not yet figured it out. I'd love to hear your solution!
推荐答案
有可能是基于处理用户和点的全地图很多类似的做法。这很简单，如果没有大量的用户将正常工作。但是，当用户数量的增长可能存在关于存储器，甚至CPU使用一个大的性能问题。所以，我已经想到一个可能的解决方案将性能提升到帐户。
There could be many similar approaches based on handling the whole map of users and points. That is simple and will work fine if there are not a lot of users. But when the number of users grows there may be a big performance issue regarding memory and even CPU usage. So that I've thought on a possible solution taking performance into account.
下面介绍的方法我会按照根据概率来吸引用户：
Here is described the method I will follow to draw a user depending on probabilities:
+------+--------+
| User | Points | Bar graph:
+------+--------+
| A | 20 | |~~~~~~~~~~~~~~~~~~~~|
+------+--------+
| B | 10 | |~~~~~~~~~~|
+------+--------+
| C | 1 | |~|
+------+--------+
| D | 5 | |~~~~~|
+------+--------+
| E | 12 | |~~~~~~~~~~~~|
+------+--------+
| F | 8 | |~~~~~~~~|
+------+--------+
TOTAL | 56 | Random number: 33
+--------+
If we take all bars and put them heel and toe we get something like this:
A B C D E F
|~~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~|~|~~~~~|~~~~~~~~~~~~|~~~~~~~~|
Position 33 is up here ▲ so we got a winner: user D
这是一个简单的概念，而是取决于算法的实现就可以毁掉性能（例如，如果我们试图按顺序做）。
This is a simple concept but it can ruin performance depending on the algorithm implementation (e.g. if we try to do it sequentially).
我要做的就是平分组用户，并从用随机数的第一部分进行比较的点的总和。如果该数小于第一的部分点（积累）总和的数量必须对应于该部分中的用户，如果不是，数目对应于所述第二部分。这个方法必须要直到我们得到一个单一用户（赢家）上的每个选择部分递归应用。这样，我们扔用户的总量的距离的1/2的第一次迭代，1/4的第二个，等等。这意味着，如果我们有100万用户，在第二次迭代，我们会摆脱750K。不坏IMO。
What I'll do is to bisect the group of users and compare the sum of points from the first part with the random number. If the number is less than first's part points (accumulated) sum, the number must correspond to a user within that part, and if not, the number corresponds to the second part. This method must to be applied on each chosen part recursively until we get one single user (the winner). This way we throw away 1/2 of the total amount of users on the first iteration, 1/4 on the second one, and so on. This means that if we had 1M users, on second iteration we'd get rid of 750k. Not bad IMO.
下面那张PHP和放大器;基于MySQL的解决方案...
Here goes the PHP & MySQL based solution...
User表：
CREATE TABLE `User` (
`id` int(15) NOT NULL AUTO_INCREMENT,
`name` varchar(255) COLLATE utf8_unicode_ci NOT NULL,
`points` int(15) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci AUTO_INCREMENT=1;
数据库交互类：
class UserDb
{
private $pdo;
private $sumIntervalStmt;
public function __construct(\PDO $pdo)
{
$this->pdo = $pdo;
$this->sumIntervalStmt = null;
}
public function getTotal()
{
$query = 'SELECT COUNT(`id`) FROM `User`;';
$result = $this->pdo->query($query);
return (int)($result->fetchColumn());
}
public function getTotalPoints()
{
$query = 'SELECT SUM(`points`) FROM `User`;';
$result = $this->pdo->query($query);
return (int)($result->fetchColumn());
}
public function sumPointsInterval($offset, $length)
{
if ($this->sumIntervalStmt === null) {
$this->sumIntervalStmt = $this->pdo->prepare(
'SELECT SUM(points) FROM (' .
'SELECT points FROM `User` LIMIT ?, ?' .
') AS Subgroup;'
);
}
$this->sumIntervalStmt->bindValue(1, (int)$offset, \PDO::PARAM_INT);
$this->sumIntervalStmt->bindValue(2, (int)$length, \PDO::PARAM_INT);
$this->sumIntervalStmt->execute();
return (int)($this->sumIntervalStmt->fetchColumn());
}
public function getUserByOffset($offset)
{
$query = 'SELECT * FROM `User` LIMIT ?, 1;';
$stmt = $this->pdo->prepare($query);
$stmt->bindValue(1, (int)$offset, \PDO::PARAM_INT);
$stmt->execute();
return $stmt->fetchObject();
}
}
用户抽奖类：
class UserRaffle
{
private $users;
public function __construct(UserDb $users)
{
$this->users = $users;
}
public function drawUser()
{
$total = $this->users->getTotal();
$number = rand(1, $this->users->getTotalPoints());
$offset = 0;
$length = ceil($total / 2);
$count = $total;
$sum = $this->users->sumPointsInterval($offset, $length);
$accum = 0;
while ($count > 1) {
if ($number <= $sum) {
$count -= $count - $length;
$length = ceil($length / 2);
$interval = $this->users->sumPointsInterval($offset, $length);
$sum = $accum + $interval;
} else {
$accum += $sum;
$offset += $length;
$count -= $length;
$length = ceil($count / 2);
$interval = $this->users->sumPointsInterval($offset, $length);
$sum += $interval;
}
}
return $this->users->getUserByOffset($offset);
}
}
和执行：
$pdo = new \PDO('mysql:dbname=test;host=localhost', 'username', '********');
$users = new UserDb($pdo);
$raffle = new UserRaffle($users);
$winner = $raffle->drawUser();
这篇关于选择的概率随机进入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
