这是一个问题:我有随机整数说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)具有铲斗尺寸,如果是完全重新加工则增加否.水桶 在我的用例中,这可能是一项代价高昂的练习,并希望避免使用它.3)以某种方式试图适应Bin Packing问题.但它并不容易告诉我整数将进入的bin是什么.要记住的一个显而易见的事情是,因为这些是随机的,如果计数是10万个中的一个.也可能是500,000.
你推荐什么方法？如果需要,我可以稍后提供用例.
Raf*_*sta 10
你已经结束了复杂化.整数是随机的,因此不需要思考.如果整数不是随机的,那么我们可能不得不想出一个哈希算法.
只要整数的范围合理地大于桶的数量,只需通过桶的数量模数将它们分配给它们的桶.
像这样:
void assignToBucket( int r )
{
bucket[ r % NUM_BUCKETS ].add( r );
}
你尝试插入的数量无关紧要 - 或者它们是一次性进入还是多次进入.只要流是随机的,那么模数将确保它们大致均匀地分布在桶中.
如果每个r的范围接近桶的数量,则这将不起作用.也就是说,如果每个r都是0-7并且有6个桶,它将不会均匀分布.并且它不适用于非随机流.
对于具有非随机分布的流,您需要了解有关分布的信息以创建适当的散列函数.