选择随机行但有赔率

Question

我有一个行数据集，每行的“赔率”数字在 1 到 100 之间。我希望以最有效的方式做到这一点。赔率加起来不一定是 100。

我有一些想法。

一个） 选择整个数据集，然后将所有赔率相加并生成 1 到该数字之间的随机数。然后循环遍历数据集，从数字中扣除赔率，直到为 0。

我希望将对数据库的影响降至最低，因此我考虑是否只能选择我需要的行。

b）

SELECT * FROM table WHERE (100*RAND()) < odds

我考虑过LIMIT 0,1

但是如果项目具有相同的概率，则只会返回其中之一

或者获取整个数据集并从那里随机选择一个......但几率是受到影响，因为它变成了有赔率的随机，然后变成了无赔率的随机，因此赔率变得有利于更高的赔率（甚至更是如此）。

我想我可以按赔率排序 ASC，然后获取整个数据集，然后使用 PHP 从与第一条记录（最低）赔率相同的行中随机抽取。

似乎是一个笨拙的解决方案。

有人有更好的解决方案吗？如果不是，以上哪一项最好？

Answer 1

做一些前期工作，在表格中添加一些有助于选择的列。例如，假设您有这些行，

 X  2  
 Y  3
 Z  1

我们添加一些累积值，

 Key Odds Start  End 
 X    2     0     1      // range 0->1, 2 values == odds
 Y    3     2     4      // range 2->4, 3 values == odds
 Z    1     5     5      // range 5->5, 1 value == odds

选择“开始”和“结束”，如下所示。第一行从零开始。后续行的开始位置比前一个结束位置多一个。结束是（开始 + 赔率 - 1）。

现在在 0 到 Max(End) 范围内选择一个随机数 R

Select * from T where R >= T.Start and R <= T.End

如果数据库足够聪明，我们也许可以使用

 Select * from T where R >= T.Start and R <= (T.Start + T.Odds - 1)

我推测拥有带有索引的 End 列可能会提供更好的性能。此外，Max(End) 可能会被隐藏在某个地方，并在必要时通过触发器进行更新。

显然，更新开始/结束存在一些麻烦。 或插入以某种方式自然排序，那么这可能还不错，

• 如果表内容稳定
• 以便每个新行都从旧的最高行继续。

Answer 2

如果您使用代码并添加 ORDER BY RAND() 和 LIMIT 1 会怎样？

SELECT * FROM table WHERE (100*RAND()) < odds ORDER BY RAND() LIMIT 1

这样，即使你有相同概率的倍数，它也总是会随机排序，然后你只需要第一个条目。

Answer 3

select * from table 
where id between 1 and 100 and ((id % 2) <> 0) 
order by NewId() 

Answer 4

唔。不完全清楚你想要什么结果，所以如果这有点疯狂，请耐心等待。话虽这么说，怎么样：

制作一张新桌子。该表是固定数据表，如下所示：

Odds
====
   1
   2
   2
   3
   3
   3
   4
   4
   4
   4
etc, 
etc.

然后从数据集连接到赔率列上的该表。对于表中的每一行，您将获得与该行的给定赔率一样多的行数。

然后随机选择其中一组。

Answer 5

如果您在赔率列上有一个索引和一个主键，那么这将非常有效：

SELECT id, odds FROM table WHERE odds > 0

数据库甚至不必从表中读取，它会从赔率索引中获取所需的一切。

然后，您将选择一个介于 1 和返回的行数之间的随机值。

然后从返回的行数组中选择该行。

然后，最后选择整个目标行：

SELECT * FROM table WHERE id = ?

这确保了具有赔率值的所有行之间的均匀分布。

---

或者，将赔率放入不同的表中，并使用自动增量主键。

Odds
ID     odds
1      4
2      9
3      56
4      12

将ID外键代替赔率值存储在主表中，并为其建立索引。

首先，获取最大值。这永远不会触及数据库。它使用索引：

SELECT MAX(ID) FROM Odds

获取 1 和最大值之间的随机值。

然后选择记录。

SELECT * FROM table
JOIN Odds ON Odds.ID = table.ID
WHERE Odds.ID >= ?
LIMIT 1

如果您倾向于删除赔率值或回滚插入以保持分布均匀，则这将需要一些维护。

SQL Antipatterns 书中有一整章关于随机选择的内容。

Answer 6

我没有尝试过，但也许是这样的（带有？从 0 到 SUM(odds) - 1 的随机数）？

SET @prob := 0;

SELECT
  T.*,
  (@prob := @prob + T.odds) AS prob
FROM table T
WHERE prob > ?
LIMIT 1

这与您的想法 a) 基本相同，但完全在一个（好吧，如果算上变量设置的话，技术上是两个）SQL 命令内。

Answer 7

适合 O(log(n)) 更新的通用解决方案是这样的：

• 将对象存储为（平衡）树的叶子。
• 在每个分支节点处，存储其下所有对象的权重。
• 添加、删除或修改节点时，更新其父节点的权重。

然后选择 0 到（总重量 - 1）之间的数字并沿着树向下导航，直到找到正确的对象。

由于您不关心树中事物的顺序，因此可以将它们存储为由 N 个指针和 N-1 个数字组成的数组。