在一个大的数字矩阵中快速找到第n大的乘积

Question

我正在研究一个与大量项目一起使用的排序/排名算法，我需要有效地实现以下算法才能使其正常工作：

---

有两个数字列表。它们长度相等，约为10-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，它比两者都大。因此，您不能只看两个邻居，而必须回溯。

- Timmy

---

n被限制在范围(0..m^2)内，因此我认为您不能声称任何O(f(n))与矩阵大小无关。 - mbeckish

生成的矩阵被称为两个向量之间的外积。 - tskuzzy

你的列表值范围是多少？如果实际上范围比列表大小小得多，那么一个以范围大小为函数的算法可能比以列表大小为函数的算法更好。 - mbeckish

请查看有关第K大和的类似问题：https://dev59.com/a2435IYBdhLWcg3wyzQJ - MBo

你的A和B样本都已经排序。我们应该假设它们总是排好序的吗？ - user unknown

Answer 1

我认为可以使用 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] 将遍历 s 个值 A[i]*B[0], A[i]*B[1], …, A[i]*B[s-1]。（需要 O(s)）
5. 将这些迭代器放入优先队列 q 中，根据它们当前的值进行排序。（需要 O(s)，因为最初它们已经按顺序排好了）
6. 从 q 中取出 n 个值。最后一个取出的值就是所需结果。当取出一个迭代器时，使用它的下一个值作为新的优先级将其重新插入 q 中。如果迭代器已经用完，则不要重新插入。（需要 O(n log s)）

总的来说，这个算法需要 O(m log m + (s + n)log s) 的时间，但 s 等于 m 或 n。

- recursive

Answer 2

你不需要对 500,000 个元素进行排序，就可以得到前三名。

只需取前三个元素，将它们放入 SortedList 中，并遍历该列表，用新值替换其中最小的三个元素之一，如果该新值更高，则重新排序结果列表。

对这两个列表都执行此操作，最终将得到一个3*3矩阵，在其中获取第三个值会很容易。 这是 scala 的实现方式。

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

那么你需要取(3,4) => 排序它们 (4,3)
然后取(2,5) => 排序它们 (5,2)

你现在可以进行一次压缩搜索。当然，最大的乘积现在是（5，4）。但下一个乘积要么是（4*2），要么是（5*3）。对于更长的列表，你可以记住4*2的结果，只与下一个乘积相比较，采用另一种方式。这样你只需要多计算一个乘积。

- user unknown

---

但我并不总是需要第三个。它可以是从 1 到 m^2 的任何数字。如果它在后一半部分，我可以反转排序并找到第 (m^2 - n) 小的元素。所以最坏情况是获取第 (250,000)^2 个元素，这是很多的。 - Timmy

搜索5x5而不是10x10仍然是一个很大的改进。(2n2n)总是4n²，相比之下nn=n²-至少提高了75%。如果n相对于m更小，则改进更大:(3n*3n)=9n²等等。 - user unknown

仍然是O(m^2)，这远远不够好。O(m log m)对于初始排序是可以接受的，之后需要变得更聪明一些。 - Timmy

@Timmy：我还没有完全弄清楚递归算法的作用，但他首先对A和B进行排序，而我只会在最坏情况下对min(N, M-N)进行排序，即A/2，B/2。 - user unknown

Answer 3

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

但是有一个相对较快的 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)。

编辑：添加一些细节。

- RoBa

---

我认为你可以将O(nlogm)视为O(m^2logm)，这相当于对整个产品集进行排序。 - mbeckish

理论上，你是对的。但是如果 n 不是 \Theta(m^2)，我的解决方案会更快。因此我认为至少在某些情况下它是有价值的。 - RoBa

真实情况是，并非每个n的值在解决给定m的问题时都需要相同数量的步骤。但是，当谈论大O时，仍然被认为是O(m^2logm)。我认为OP想要在任何n的情况下超越O(m^2logm)。 - mbeckish