c++ - 均匀填充大小不一的 "buckets"未排序列表的最有效方法是什么

Question

假设我有一个 bucket 的未排序列表秒。 (每个桶都有一个 size 属性。)假设我有一个数量 Q我必须尽可能均匀地分布在桶列表中(即最小化最大值)。

如果桶排序的大小越来越大，那么解决方案就很明显了:完全填满每个桶，比如 buckets[i] , 直到 Q/(buckets.length-i) <= buckets[i]->size , 然后用相同数量的 Q/(buckets.length-i) 填充剩余的桶，如图:

如果桶未排序，解决此问题的最有效方法是什么？

我只能想到这样迭代(伪代码):

while Q > 0
    for i in 0..buckets.length-1
        q = Q/(buckets.length-i)
        if q > buckets[i]->size
            q = buckets[i]->size
        buckets[i]->fill(q)
        Q -= q

但我不确定是否有更好的方法，或者对列表进行排序是否会更有效率。

(我面临的实际问题有更多，例如这个“未排序”列表实际上是由一个单独的属性“rank”排序的，它决定了当数量不多时哪些桶会得到额外的填充'平均分配等。因此，例如，要使用 sort-then-fill 方法，我会按存储桶大小和排名对列表进行排序。但知道这个问题的答案会对我有所帮助找出其余部分。)

Answer 1

在许多情况下，如果数据已排序，解决方案“非常简单”或“非常有效”，但如果未排序则非常复杂或无效，最好的解决方案通常是先对数据进行排序然后寻求简单有效的解决方案。尽管这意味着您将有先对数据进行排序的开销，但有很多非常好的排序算法可用于几乎任何目的，并且在许多情况下，“首先对数据进行排序然后应用简单、有效的算法”的总开销到它”仍然低于“不对数据进行排序并对其应用非常复杂、无效的算法”。

您需要按不同键对数据排序这一事实对我来说仅意味着您需要两个列表，每个列表按不同的标准排序。除非我们在这里谈论几千个桶，否则第二个列表的内存开销很可能不是问题(毕竟两个列表只包含指向您的桶对象的指针，这意味着每个指针 4/8 字节，具体取决于事实你有 32 位或 64 位代码)。一个列表的存储桶按大小排序，另一个列表的存储桶按“等级”排序，当按照问题中的描述添加新项目时，您使用“按大小排序”列表，同时使用“按等级排序”列表与您现在使用它的方式相同。