algorithm - 确定性地在加权桶列表中分配一个 id

Question

我在网站上运行 n 个拆分测试。我想将一个均匀分布的整数用户 ID 分配给 n 个存储桶之一，并且确定性地让同一用户始终获得相同的测试。

此时，我可以通过将用户 ID 修改为 n 来在拆分测试列表中选择一个索引。如果我想对某些测试进行加权怎么办？

例如，桶 #1/21 被分配了 90% 的时间，其余 20 个测试被分配了 0.5% 的时间。

我觉得我可以以某种方式扩大我的列表的大小，并且仍然使用 mod 技术来实现这一点，但是在内存中拥有可能巨大的临时列表似乎并不优雅。

Answer 1

如果大多数桶具有不同的大小，其中大小定义为 ID 的百分比，那么您将不得不以某种方式在内存中表示它。否则，您还怎么知道这些百分比？

一种解决方案是使用 100 个虚拟桶，每个桶代表 1% 的 ID。然后将 90 个虚拟桶关联到桶 #1/21。然后你可以执行 mod 100，如果它落在前 90 个虚拟桶中，则将 id 分配给桶 #1。您可以通过将每个桶的百分比除以 GCD 来获得最佳虚拟桶数。所有百分比的百分比，在您的示例中为 0.5 (GCD(90, 0.5))。

但是从您的示例来看，只有一个不同的存储桶大小。最佳解决方案实际上取决于您可能拥有的安排类型。