7

我正在研究一种适用于大量项目的排序/排名算法，我需要以有效的方式实现以下算法以使其工作：

有两个数字列表。它们同样长，大约 100-50 万条。从这里我需要找到这些列表之间的第 n 个最大的产品，即。如果您创建一个矩阵，其中顶部有一个列表，一侧有另一个列表，每个单元格都是上面数字和侧面数字的乘积。

示例：列表是A=[1, 3, 4]和B=[2, 2, 5]。然后是产品[2, 2, 5, 6, 6, 15, 8, 8, 20]。如果我想要第三大，那将是 8。

天真的解决方案是简单地生成这些数字，对它们进行排序，然后选择第 n 个最大的。但这就是O(m^2 * log m^2)m 是小列表中元素的数量的地方，这还不够快。

我想我需要的是首先对两个小列表进行排序。那就是O(m * log m)。然后我肯定知道最大的一个A[0]*B[0]。第二大的是 A[0]*B[1] 或 A[1]*B[0], ...

我觉得这可以分O(f(n))步完成，与矩阵的大小无关。但我想不出一种有效的方法来完成这部分。

编辑：有一个答案被删除，它建议记住两个排序集中的位置，然后查看 A[a]*B[b+1] 和 A[a+1]*B[b]，返回更大的一个并递增 a/b。我打算在它被删除之前发布这条评论：

这行不通。想象两个列表 A=B=[3,2,1]。这会给你像 [9,6,3 ; 6,4,2; 3,2,1]。所以你从 (0,0)=9 开始，到 (0,1)=6，然后选择是 (0,2)=3 或 (1,1)=4。但是，这将错过 (1,0)=6 比两者都大。所以你不能只看两个邻居，但你必须回溯。

4

3 回答 3

4

我认为它可以在O(n log n + n log m). 这是我的算法的草图，我认为它会起作用。这有点粗糙。

  1. 对 A 进行降序排序。（采取O(m log m)）
  2. B 降序排序。（采取O(m log m)）
  3. 让。s_ min(m, n)（采取O(1)）
  4. 通过.创建s惰性序列迭代器。 将遍历值, , ..., . （采取）L[0]L[s-1]L[i]sA[i]*B[0]A[i]*B[1]A[i]*B[s-1]O(s)
  5. 将迭代器放入优先队列q中。迭代器将根据其当前值进行优先级排序。（O(s)因为最初它们已经按顺序排列）
  6. 从 中提取n值q。拉出的最后一个值将是所需的结果。当一个迭代器被拉出时，它被重新插入，q使用它的下一个值作为新的优先级。如果迭代器已经用完，不要重新插入它。（采取O(n log s)）

总之，该算法将采用O(m log m + (s + n)log s)，但s等于m或n。

于 2012-05-17T15:24:39.227 回答
0

您无需对 500 000 个元素进行排序即可获得前 3 个元素。

只需取前 3 个，将它们放在 SortedList 中，然后遍历列表，用新值替换 3 个元素中最小的一个，如果新值更高，然后再使用结果列表。

对两个列表都执行此操作，您将得到一个 3*3 矩阵，在该矩阵中取第三个值应该很容易。

这是 scala 中的一个实现。

如果我们假设n小于m，并且A=[1, 3, 4] and B=[2, 2, 5]，n=2：

您将采用 (3, 4) => 对它们进行排序 (4,3)
然后采用 (2,5) => 对它们进行排序 (5, 2)

您现在可以进行压缩搜索。当然现在最大的产品是(5, 4)。但下一个是 (4*2) 或 (5*3)。对于更长的列表，您可以记住 4*2 的结果是什么，仅将其与下一个产品进行比较，反之亦然。这样一来，您只会过多地计算一种产品。

于 2012-05-17T14:27:27.893 回答
0

我不认为有 O(f(n)) 的算法，它独立于 m。

但是有一个相对较快的 O(n*logm) 算法：

首先，我们对两个数组进行排序，我们得到 A[0] > A[1] > ... > A[m-1] 和 B[0] > B[1] > ... > B[m- 1]。（当然，这是 O(mlogm)。）

然后我们构建一个最大堆，其元素为 A[0]*B[0], A[0]*B[1], ... A[0]*B[m-1]。我们维护一个“指针数组”P[0], P[1], ... P[m-1]。P[i]=x 表示 B[i]*A[x] 当前在堆中。所有的 P[i] 最初都是零。

在每次迭代中，我们从堆中弹出最大元素，这是下一个最大的产品。假设它来自B[i]*A[P[i]]（我们可以记录堆中的元素来自哪个B[i]），然后我们将对应的指针向前移动：P[i] += 1，并将新的 B[i] * A[P[i]] 推入堆中。（如果 P[i] 移动到超出范围 (>=m)，我们只需将 -inf 推入堆中。）

在第 n 次迭代之后，我们得到第 n 个最大的乘积。

有n次迭代，每次都是O(logm)。

编辑：添加一些细节

于 2012-05-17T15:08:36.197 回答