分割数据集的选取范围

Question

我有0到64K之间的几百万整数。我想将它们拆分成N个桶，每个桶包含大约相同数量的连续范围内的项目。因此，举个例子，如果我只有一个数据点，每个可能的值和64个桶，理想情况下，我最终会得到一个0-1024桶，一个1025-2048等。

什么是算法用于计算最均匀分配物品数量的铲斗范围？

Answer 1

如果你的重点是均匀分布的，去最简单的方法很可能是对列表进行排序，然后将第一(list_length/N)项目到第一桶，那么接下来(list_length/N)项目进入下一个水桶，等等。因为你有一个相当大的名单来排序，这可能不是最有效的解决方案。

Answer 2

排序你的数字并填充包含所需数量的元素，当你通过排序列表中的元素是一种可能性。

通过使用heap，您可以做类似的事情，但速度可能更快：您可以使用元素填充堆，然后可以非常快速地提取最小的元素。

但是，如果速度不是太大，那么对100万个数字进行排序既简单又快速（Python中使用Numpy只需几分之一秒）。