确定加权奖励的算法/查询

Question

我正在开发一个游戏，其中用户获得随机奖励，每个奖励的交付机会由“共享”系统加权。为了说明这个问题，让我们看一个例子：假设我要给出一个纯粹的随机奖励，超出集合：[A，B，C]。这就像获取随机索引并从数组中返回任何奖励一样简单。然而，在我的用例中，奖励集是带有“共享”系统的权重。所以我们有如下情况：A - 重量为 2。B - 3 的重量。C - 重量为 5。所以这个集合看起来像这样：[A，A，B，B，B，C，C，C，C，C]。现在，我可以构建该数组并获得这样的随机结果，但我担心性能影响。这些奖励存储在数据库中（如果考虑在内，则使用 Django 和 PSQL 作为后端），并且可能有超过 100 个潜在奖励，每个奖励的权重为 1-100（或更多）。因此，我试图找出一种有效的方法来根据这种权重提取随机奖励。在我写这篇文章时，我想到了一件事（但我想听听其他想法）：奖励集更新后，构建一次数组，然后为每个奖励分配一个百分比机会。所以计算一次百分比。在上面，我们最终会得到类似：[A: 0.2, B: 0.3, C: 0.5]。那么我们可以得到一个 0 到 1 之间的随机数，并在不超过的情况下拉取最接近的奖励？（所以随机掷出 0.45 会得到 B，因为 0.3 最接近 0.45 而不会高于 0.45）。但是，我正在努力思考如何为此编写高性能查询。也许查询所有百分比低于滚动的奖励（在上面的示例中为 0.45），并从这些结果中返回百分比最高的奖励。我想我可能刚刚回答了我自己的问题，但会欣赏第三方的观点。谢谢大家！

Answer 1

您应该使用累积百分比。示例设置：

create table weights(label text, weight int, cumulative_percentage float);

insert into weights (label, weight) values

('A', 2),

('B', 3),

('C', 5);

update weights w

set cumulative_percentage = cumulative_sum::float/ total

from (

    select 

        label,

        sum(weight) over (order by label) as cumulative_sum,

        sum(weight) over () as total

    from weights

    ) s

where s.label = w.label;

所以表格看起来像这样：

select *

from weights

 label | weight | cumulative_percentage 

-------+--------+-----------------------

 A     |      2 |                   0.2

 B     |      3 |                   0.5

 C     |      5 |                     1

(3 rows)

使用公用表表达式在循环中获取单个随机数：

with seed(r) as (select random())

select min(label)

from weights, seed

where r <= cumulative_percentage

或创建一个函数：

create or replace function get_percentageed_reward(r float)

returns text language sql as $$

    select min(label)

    from weights

    where r <= cumulative_percentage

$$; 

检查算法的结果：

select get_percentageed_reward(random()), count(*)

from generate_series(1, 100000)

group by 1

order by 1

 get_percentageed_reward | count 

-------------------------+-------

 A                       | 20008

 B                       | 30165

 C                       | 49827

(3 rows)