python - 处理概率变化系统的高效算法

Question

我在制定算法方面需要帮助。我有一个用 python 构建的带有 redis 后端的社交网络应用程序。其中一项功能是广告服务器，广告商可以使用它来为网站用户制作和转换广告。

广告商购买点击次数。每次点击费用不固定。一个广告商可能支付 1 美分/点击，另一个可能支付 2 美分/点击，等等。广告商支付的费用越多，她的广告被展示的可能性就越大。即，在其他条件相同的情况下，出价更高的广告商更快获得点击。

例如假设广告商 1 为 1000 次点击支付了 10 美元，广告商 2 为 1000 次点击支付了 20 美元，广告商 3 为 1000 次点击支付了 30 美元。在其他条件相同的情况下，在每次广告展示中，广告商 1 的广告将有 1/6 的出现概率，广告商 2 的广告将有 2/6 的出现概率，而广告商 3 的广告将有 3/6 的出现概率。如果将第 4 个广告商添加到组合中，则概率将发生变化。一旦达到广告商的指定点击次数，她就会被排除在外，概率会再次修改。

如何用高效的算法对其进行建模？

---

我在尝试对此建模时感到困惑的一个原因是，在添加(或减去)广告商时，整个系统的概率会即时修改。我一直无法解决这个问题；希望高手帮帮忙。

Answer 1

作为购买广告位的广告商，我个人不确定我是否愿意为我的广告展示的不确定概率付费。我能想到的最接近合理的事情(这可能是你正在考虑的)是只保证那些支付相同费用的人获得相同的概率。执行此操作的一种有效方法是保留支付费率的累计总和以提供随机范围:

cumsum, rate, company

1,  1,  A
2,  1,  B
4,  2,  C
8,  4,  D

如果您生成一个从 0 到 7(或 1 到 8)的随机数，您可以进行二进制搜索 (O log(n)) 以确定应显示哪个广告。

如果你让公司按比率排序，你甚至可能比 (O log(n)) 做得更好......也许

添加和减去公司会相对简单:添加(或减去)公司和费率的一行，然后重新计算 cumsum。