我正在开发一款游戏,其中用户会获得随机奖励,每个奖励的交付机会由“分享”系统加权。为了说明这个问题,让我们看一个例子:
假设我要给出一个完全随机的奖励,超出集合:[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),并返回这些结果中百分比最高的奖励。
我想我可能刚刚回答了我自己的问题,但希望有第三方的观点。谢谢大家!
最佳答案
您应该使用累积百分比。设置示例:
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)
使用公共(public)表表达式在循环中获取单个随机数:
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)
关于python - 确定加权奖励的算法/查询,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58465646/