6

假设我有一个未排序的 s 列表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方法，我会按存储桶大小和排名对列表进行排序。但是知道这个问题的答案将帮助我找出其余的。）

4

6 回答 6

3

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

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

于 2013-01-08T16:56:30.753 回答
2

我认为这可能在线性时间内是可能的，但是我被困在某个点上。也许你可以解决问题，也许不能这样解决。

考虑以下算法。

基于二分查找，我们希望找到未满的最小桶。在一个桶列表中找到这样一个桶可能在线性时间内是可能的，但正如我所说，我被困在这里。一旦我们找到那个桶，剩下的就变得微不足道了，因为对于所有较小的桶，我们将它们的大小相加，从要放置的项目总数中减去它，然后除以大于或等于我们刚刚找到的桶的数量.

所以下面是解决这个问题的一个尝试：没有完全装满的最小桶是多少？该算法由 QuickSelect 驱动。

选择一个枢轴桶。看看它比我们要找的桶小还是大。（这一步很简单。）

  • 如果它更小，则将所有小于或等于该值的桶的大小相加，从项目总数中减去该总和，然后继续搜索包含所有较大桶的集合。

  • 如果它更大，我们将不得不做类似的事情，但现在减去放置在所有比这个大的桶中的项目数。我们不知道要放置在这些桶中的项目数量。这就是问题所在……但如果我们知道，我们将继续在包含所有较小存储桶的集合上进行搜索。

如果此算法有效，它将在随机枢轴元素的预期线性时间内运行（请参阅 QuickSelect）。

于 2013-01-08T17:05:19.570 回答
2

如果您可以确定 q，填充每个桶的适当最小水平，使总数为 Q，则线性解决方案是明确的：

for (bucket b : buckets)
{
    int f = max(b.capacity(), q);
    b.fill(f);
}

所以问题是确定水平 q。

您可以对 q 进行二分搜索。也就是说，我们知道 q 是 和 之间的min(b.capacity)整数max(b.capacity)。IE：

  1. q'从最小（容量）和最大（容量）之间的候选人开始
  2. Q'通过桶计算使用产生的总量q'
  3. if ( Q' > Q) 比重复q'减半
  4. if ( Q' < Q) 比重复q'增加一半
  5. 返回q = q'

步骤 2 的每一遍都是 O(N)，并且会有 log(L) 遍，其中L = max(capacity) - min(capacity)

这比排序时更好L << N

一个足够的统计数据是将桶简化为直方图：

unordered_set<int,int> bucket_capacity;

for (bucket b : buckets)
    bucket_capacity[b.capacity]++;

这仍然是线性的，但是在最坏的情况下并没有给我们带来太多好处，因为桶可能有不同的大小，但是它限制了通过，L所以现在的效率是O(min(L,N) * logL)

L << N当效率变为 O(LlogL)时，这再次运行良好

我怀疑以下是正确的，但不是 100%：在L >> N可以证明没有线性解决方案的情况下。首先我们假设我们有一个线性解决方案。然后，我们使用这个解决方案作为一种工具，在线性时间内进行比较排序。已经证明比较排序在线性时间内是不可能的，因此我们的假设一定是错误的，并且没有线性解决方案。

于 2013-01-08T17:32:46.363 回答
1

另一种想法如下。确定每个桶的平均项目数。然后尝试用该数字填充所有存储桶（通常，并非所有存储桶都可以容纳该数量的项目）。

之后，您有一些剩余的项目要放置在存储桶中（因为并非所有项目都适合上一次迭代）以及一个存储桶列表，其中可以容纳比当前包含的项目更多的项目（在上一次迭代中计算）。

同样，根据要分配的剩余项目数计算要在剩余存储桶上分配的平均项目数。

重复，直到您放置所有项目。

我预计运行时间为O(n * log n)，但没有分析它。它与您的sort-then-fill方法的运行时间相同，但是，如果您的存储桶只有有限数量的不同尺寸，则预计会更低，例如：有些小，有些很大，有些很大。

于 2013-01-08T16:54:16.590 回答
1

在一个步骤中，您从 n 个未排序的有限容量桶、k 个无限桶（您存储 k，而不是这些桶的列表，并且在第一次迭代时 k=0）和一定量的水 w 开始。在 O(n) 时间内，我们将把问题简化为具有 n', k', w' 的另一个实例，其中 n' < c * n 对于常数 c < 1。迭代此过程将解决问题（一旦 n是一个常数，你可以在常数时间内求解它）在线性时间内：n+c*n+c^2*n+...=O(n)。

在所有 n 个有限容量中，选择中位数（即选择一个使得一半容量较高而一半容量较低）。这可以在 O(n) 时间内完成（选择算法）。计算 1) 较低容量和 2) 中值容量乘以较高容量桶的数量（包括无限桶）的总和。

如果它小于 w，您知道您需要将桶装得更高，因此特别是所有容量较低的桶都将被装满。删除它们，从 w 中删除它们的容量总和，您就完成了这次迭代，n'=n/2。

另一方面，如果总和大于 w，则您知道没有桶将被填充到中位容量或更高容量。因此，可以移除所有更高容量的存储桶，并将它们的数量添加到无限存储桶的数量中。w 保持不变。同样，n'=n/2，我们就完成了。

一些简单的细节被跳过（特别是如何处理许多桶具有完全相同容量的情况）以保持简短。最后，您还需要进行一些清理，一旦您知道正确的水位，为每个“无限”（即非满）桶设置它。

于 2013-01-09T19:43:36.963 回答
-1

为什么需要对存储桶列表进行排序？只需遍历桶两次。

第一次计算所有尺寸。从那你可以说，“我想要每个桶里有 K 个项目”

不过第二次，把桶装满。

于 2013-01-08T16:49:33.917 回答