php - 以概率选择随机条目

Question

假设我在数据库中存储了以下信息:

User         Points
 A            2000
 B            1000

我想根据点数随机选择一个获胜者。在这种情况下，由于总共有 3000 分，“A”有 67% 的机会被选中，“B”有 33% 的机会被选中。

使用 PHP 选择获胜者的最有效方法是什么(从计算概率到选择获胜者)？请注意，玩游戏的用户数量不是固定的，范围可能很大(因此它应该计算“每个用户”而不是固定在 A 和 B 上)。

我一直在尝试各种可能的解决方案，但还没有弄清楚。我很想听听您的解决方案!

Answer 1

在处理用户和点的整个 map 的基础上，可能有许多类似的方法。这很简单，如果用户不多，也能正常工作。但是当用户数量增长时，内存甚至 CPU 使用率可能会出现很大的性能问题。所以我考虑了一个可能的解决方案，将性能考虑在内。

这里描述了我将遵循的根据概率绘制用户的方法:

+------+--------+
| 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

这是一个简单的概念，但它可能会破坏性能，具体取决于算法实现(例如，如果我们尝试按顺序执行)。

我要做的是将用户组平分，并将第一部分的点总和与随机数进行比较。如果该数字小于第一部分积分(累计)总和，则该数字必须对应该部分内的用户，否则，该数字对应第二部分。此方法必须递归地应用于每个选定的部分，直到我们获得一个用户(获胜者)。这样，我们在第一次迭代中丢弃了用户总数的 1/2，在第二次迭代中丢弃了 1/4，依此类推。这意味着如果我们有 100 万用户，在第二次迭代中我们将摆脱 750k。 IMO 还不错。

这是基于 PHP 和 MySQL 的解决方案...

用户表:

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();