根据行的“权重”随机选择行

Question

我有一个类似这样的表格：

ID chance
1 1
2 2
3 4
4 1

现在我需要从这个表中选择一个 rand()。

SELECT * FROM table
ORDER BY RAND()
LIMIT 1

但是，与ID #1和4相比，ID #2被选中的机会增加了一倍。同样地，与ID #1和4相比，ID #3被选中的机会增加了四倍。

有点类似于基于概率的彩票。

- hossein karimi

---

抱歉我的英语不太好，没关系。 - Aniket Sahrawat

请问您能否编辑您的问题并添加一个使用'rand()'函数的示例？ - rudolf_franek

Answer 1

这是一些游戏中抽奖的工作原理。给定类似于您示例的表格（假设我们还有一个表示获得此特定奖励的基于值的可能性的“机会”列），算法如下：

1. 计算总抽奖价值（在您的示例中，它是1 + 2 + 4 + 1 = 8）。
2. 生成一个范围在1..max（当前示例中的max为8）之间的值，包括max。
3. 迭代所有奖励列表项以查找其中一个项目，其中所有先前机会的总和大于生成的数字但小于或等于

例如，我们已生成数字5。我们的比较步骤如下：

1. 0 < 5 <= (0) + 1为false，因此我们没有得到ID1。左侧为0，因为我们从0开始计算。
2. 1 < 5 <= (1) + 2为false，因此我们没有得到ID2。
3. 1 + 2 < 5 <= (1 + 2) + 4为true，因此我们得到ID3。

JavaScript示例：

var rewards = [
  { id: 1, chance: 1 },
  { id: 2, chance: 2 },
  { id: 3, chance: 4 },
  { id: 4, chance: 1 }
];

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function generate() {
  var sum = 0;
  var next_sum = 0;
  var random = getRandomInt(1, rewards.reduce(function(pv, cv) {
    return pv + cv.chance;
  }, 0));

  for (var i = 0; i < rewards.length; i++) {
    next_sum = sum + rewards[i].chance;
    if ((random > sum) && (random <= next_sum)) {
      return rewards[i].id;
    }
    sum += rewards[i].chance;
  }
}

var winnerCounts = {}, i, winner;
for (i = 0; i < 8000; i++) {
  winner = generate();
  winnerCounts[winner] = (winnerCounts[winner] || 0) + 1;
}
console.log("Number of times each id was selected after %d itrations", i);
console.log(winnerCounts);

- lolbas

---

@x-rw 这个算法与机器学习无关，至少不是故意的。 - lolbas

Answer 2

这里有一个仅使用MySQL的解决方案，可以访问SQL Fiddle

select * from (
  select id, @running_total as previous_total, @running_total := @running_total + chance AS running_total, until.rand
  from (
    select round(rand() * init.max) as rand from (
      select sum(chance) - 1 as max from demo
    ) as init
  ) as until,
  demo,
  ( select @running_total := 0.00 ) as vars
) as results
where results.rand >= results.previous_total and results.rand < results.running_total

算法如下:

1. 计算所有机会的总和，并将其存储在max中
2. 在区间[0,max)内生成一个随机数
3. 对于每一行，计算当前已遇到的机会的previous_total(初始值为0)和current_total
4. 仅保留所生成的数字处于区间[previous_total,current_total)的行

因为我们有相同的机会在区间[0,sum_of_all_chances)中选择每个数字，所以我们可以将每个条目分配为该条目被选中的机会数量的数字，在这个区间中确保均匀分布。 @running_total只是一个MySQL变量，我使用(select @running_total := 0.00) as vars只是为了给它一个初始值。此外，我使用( select round(rand() * init.max) as rand from ( select sum(chance) - 1 as max from demo ) as init ) as until只是为了总结机会并存储由MySQL的rand函数生成的随机数字。希望这样能使代码易于理解。

- Valdrinium

Answer 3

如果您需要清晰的MySQL解决方案，可以使用以下代码：

SELECT id FROM `table` ORDER BY -LOG(1-RAND())/chance LIMIT 1

这里是关于从指数分布中选择随机数的内容 http://www.tushar-mehta.com/publish_train/xl_vba_cases/0806%20generate%20random%20numbers.shtml 这是一个简单的代码，"仅供测试"。

$sql = "SELECT id FROM `table` ORDER BY -LOG(1-RAND())/chance LIMIT 1";
$Res=array();
for ($i=0;$i<10000;$i++) {
    $result = mysqli_query($db,$sql);
    $row=mysqli_fetch_array($result, MYSQLI_ASSOC);
    if (isset($row['id'])) {
       echo "$i. => ".($row['id'])."\n";
       if (!isset($Res[$row['id']])) $Res[$row['id']]=0;
       $Res[$row['id']]++;
    } else {
        echo ' error.432 ';exit;
    }
}

print_r($Res);

你会发现数字“2”出现的频率比“4”或“1”多两倍。而数字“3”出现的频率比“2”多两倍。

- ABelikov