2

次の情報がデータベースに保存されているとします。

User         Points
 A            2000
 B            1000

ポイント数に応じた確率で当選者をランダムに選びたいです。この場合、合計3000点なので、「A」が67%、「B」が33%の確率で当選します。

PHPを使用して勝者を選択する最も効率的な方法は何ですか(確率の計算から勝者の選択まで)? プレイしているユーザーの数は固定されておらず、最大数に及ぶ可能性があることに注意してください (したがって、A と B に固定するのではなく、「各ユーザー」を計算する必要があります)。

私は潜在的な解決策をいじっていますが、まだそれを理解していません。あなたの解決策を聞きたいです！

4

3 に答える 3

6

ユーザーとポイントのマップ全体を処理することに基づいて、多くの同様のアプローチが考えられます。これは簡単で、多くのユーザーがいない場合は問題なく機能します。しかし、ユーザー数が増えると、メモリや 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

これは単純な概念ですが、アルゴリズムの実装によってはパフォーマンスが低下する可能性があります (たとえば、順次実行しようとすると)。

ここで行うことは、ユーザーのグループを二等分し、最初の部分のポイントの合計を乱数と比較することです。数が最初の部分のポイント (累積) 合計よりも小さい場合、その数はその部分内のユーザーに対応している必要があり、そうでない場合、数は 2 番目の部分に対応しています。このメソッドは、1 人のユーザー (勝者) が得られるまで、選択した各パーツに再帰的に適用する必要があります。このようにして、最初の反復でユーザーの合計量の 1/2 を破棄し、2 回目の反復で 1/4 を破棄する、というようにします。これは、100 万人のユーザーがいた場合、2 回目の反復で 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();
于 2012-11-20T12:43:01.520 に答える
2

単なるアイデア (チャンスに関する私のコメントを参照): すべてのポイントを合計し、プレーヤーを並べ替えます。次に、1 ～ の間で乱数を選択します$sum。これで、0 になるまで乱数からプレイヤーのポイントを差し引くことができます。

$players = array(
        "A" => 2000,
        "B" => 1000
);
$sum = array_sum($players);
echo $random = rand(1, $sum)."\n";
foreach($players as $player => $points) {
        $winner = $player;
        $random -= $points;
        if($random <= 0)
                break;
}
echo $winner."\n";

$points/$sum確率と 0.0 から 1.0 の間の乱数を使用して、これを同様に行うことができます。

于 2012-11-19T14:25:38.053 に答える
0

式 1/p はすべてのプレーヤーで使用できます。すべての確率の合計が 1 になるように正規化することをお勧めします。その後、[0...1] からランダム ジェネレーターを使用して、すべてのプレイヤーをループできます。乱数発生器からの数値が現在のプレーヤーの確率よりも小さい場合は、このプレーヤーを選択します。それ以外の場合は、乱数から現在の確率を差し引いて、次のプレーヤーに移動します。

       x = random([0.0, 1.0])
       for i in 0..n
           if x < probabilities[i]
               choose(i)
              break
           else
              x -= probabilities[i]
          end
        end

正規化する必要がある場合は、すべての 1/px 乗数の合計の reziproken ですべての 1/px を乗算する必要があります。例: 2 つのエッジ p1=30 と p2=15 を持つ頂点があります。1/(1/30 + 1/15) = 10、また P1 = 10 * 1/30 = 1/3 および P2 = 10 * 1/15 = 2/3 です。

于 2012-11-19T14:30:42.753 に答える