4

这是一个问题：我有随机整数说 count = M 并且它们需要在 N 个桶中平均分配（或大致相等）。

如果我要为 M 和 N 分配一个范围，N 将在 10000 左右，M 可能在 100 到 500 万之间。

到目前为止，这看起来像是一个小散列问题。但这使事情变得更加复杂。所以这些数字在计数上是 M，但它们将被逐步考虑，所以说最初你有 X 没有。整数，你平均分配它们，然后 Y 没有。整数可用更多，因此您再次分配它们，然后 Z 没有。整数个可用 (X+Y+Z = M)。

也是一个特定的号码。应该以这样的方式分布，即他们的桶没有。可以高效搜索。

到目前为止，我想到了几种方法，但没有一种方法可以接近平均分配。

1）有桶号。高，因此 N 的最大值为 500 万。平均分配意味着 500 个桶，所以从创建 500 个桶开始。它们最终将同样充满。但这也有可能很难处理的最终情况。2）根据当前可用的大小（X，然后是 X+Y，然后是 M）具有桶大小，如果它是完整的 rehash 以增加 no。桶。在我的用例中，这可能是一项代价高昂的练习，并且希望避免它。3）不知何故试图适应装箱问题。但它并不能轻易地告诉我整数将进入的 bin 是什么。要记住的一件明显的事情是，由于这些是随机数，如果计数是 100,000 则其中一个数。也可能是500,000。

你推荐什么方法？如果需要，我可以稍后提供用例。

4

2 回答 2

11

你把这复杂化了。整数是随机的，所以不需要思考。如果整数不是随机的，那么我们可能不得不提出一个哈希算法。

只要整数的范围合理地大于桶的数量，只需通过桶数的模将它们分配给它们的桶。

像这样：

void assignToBucket( int r )
{
    bucket[ r % NUM_BUCKETS ].add( r );
}

无论您尝试插入多少个 - 或者它们是一次全部插入，还是分几次插入都没有关系。只要流是随机的，那么模将确保它们大致均匀地分布在桶中。

如果每个 r 的范围接近桶的数量，这将不起作用。也就是说，如果每个 r 是从 0-7 并且有 6 个桶，它就不会均匀分布。它不适用于非随机流。

对于具有非随机分布的流，您需要了解一些有关分布的信息才能创建适当的散列函数。

于 2012-07-11T01:15:24.013 回答
0

听起来你不必要地使这复杂化，但很难说出你在问什么。这听起来很像一个球和垃圾箱的问题，检查一下，看看它是否适用，如果你能以更正式的方式描述你正在寻找的东西。

于 2012-07-11T00:01:51.493 回答