从长度为N的数组中返回前k个值的最佳算法

Question

从长度为N的数组中返回前k个值的最佳算法

algorithmsorting

36

我有一个包含n个浮点数的数组，希望返回前k个最大值（在我的情况下，n约为100，k约为10）

这个问题是否有已知的最优解路径？

能否有人提供一个C语言算法？

编辑：实际上有两个问题：排序和未排序。我对未排序感兴趣，应该更快！

- P i

请查看“基于快速排序的高效选择和部分排序”末尾讨论的部分快速排序算法。 - NPE

1

相应的非损坏链接 https://web.archive.org/web/20160110151823/http://blogs.msdn.com/b/devdev/archive/2006/01/18/514482.aspx - Nicolas Filotto

5个回答

39

你可以使用选择算法在O(n)时间复杂度内完成此操作。使用分区算法找到第k大的元素，然后它后面的所有元素都比它大，这些就是你的前k个元素。

如果你需要按排序顺序获取这前k个元素，那么你可以在O(k log k)时间复杂度内对它们进行排序。

- IVlad

请注意，此算法的时间复杂度为O(2n)，最终为O(n)，但对于许多实际应用来说速度非常慢。 - aviggiano

4

相对于nlogn或nlogk步骤，2n步仍然快得多，除非您的n或k非常小。使用以2为底的对数计算，k必须小于等于4，才会比nlogk的解决方案更慢。 - NickLamp

12

简短回答：不行。

详细回答：是的，已知几个相互不兼容的最优解。这取决于 n、k 和您可以保证的数组属性。

如果您对数组一无所知，则复杂度的下限显然为 O(n)，因为必须检查源数组的所有元素是否适合前十项。如果您了解有关源数组的任何信息，允许跳过元素，那么应该使用该知识。

同样，上限复杂度为 O(n.log(n))，因为您总是可以通过对数组进行排序（O(n.log(n))）并返回前10个项目（O(1)）来找到答案。

线性搜索将每个项目与到目前为止发现的第十高的项目进行比较，并在必要时将其插入到迄今为止发现的最高项目列表中的适当位置。对于平均和最佳情况，它具有类似的复杂度，并且具有 O(kn) 的最坏情况，比 O(n²) 要好得多。对于您估计的大小，我希望这种方法表现良好。

如果 n 更大（~10000），并且 k 以同样的比例增加，实施快速选择算法可能是值得的。 Quickselect 对于要求的元素越多，性能越好。然而，如果 k 没有按比例与 n 增加，您应该坚持线性搜索。 Quickselect 和其他算法会修改原始数组，因此如果不能在原地执行此操作，则不太合适，因为需要更多的存储空间和许多复制，算法复杂度不包括其中。

如果 n 很大（~1e20），则您需要从输入数组的若干个分区中找到 k 个最大值，然后从这些结果的聚合中找到 k 个最大值，以便不尝试分析超过一次可以一次装入内存的数据，并且允许有效地并行化该操作。

- Phil Willoughby

4

以下是一种基于堆的优雅解决方案，使用Java编写，时间复杂度为O(nlogK)。虽然不是最高效的解决方案，但我认为它足够易于理解。如果您想要一个基于浮点数的解决方案，可以将Integer更改为Float。

import java.util.Arrays;
import java.util.PriorityQueue;

public class FindKLargest {

public static void find(int[] A, int k) {

    PriorityQueue<Integer> pq = new PriorityQueue<>(k);// Min heap because the element has to be greater
                                                        // than the smallest element in the heap in order
                                                        // to be qualified to be a member of top k elements.
    for (int i = 0; i < A.length; i++) {
        if (i < k) // add until heap is filled with k elements.
            pq.add(A[i]);
        else if (pq.peek() < A[i]) { // check if it's bigger than the
                                        // smallest element in the heap.
            pq.poll();
            pq.add(A[i]);
        }
    }
    int[] topK = new int[pq.size()];
    int index = 0;
    while (index != k)
        topK[index++] = pq.poll();
    System.out.println(Arrays.toString(topK));
}

public static void main(String[] args) {
    int[] arr = { 1, -2, -3, -4, -5 };
    find(arr, 4);
}

}

- piyush121

1

如果您拥有一款高端GPU，我可以告诉您如何同时计算巨大的n个实例中的前k个，将它们分散在纹理上，每个实例都有自己的纹理位置，并按照它们的“高度”将它们混合到纹理上。

但请注意，您必须猜测或知道一个可接受的范围，否则您无法展开到可能达到的最大细节。

您需要克隆位置。（如果其中有2，则应得到2；如果其中有10，则应得到10。）跨所有实例。（只需说它们全部在一个8192x8192的纹理上，64x64个这样的“高度”框。）并且您还要跳过数量为0的插槽。

然后进行mipped add层次结构，除了您像二叉树一样处理，只将其视为1维，因此将前两个数字相加，并为每个二进制mip重复执行此操作。

然后我们使用这些mip（已收集计数）来发现k的近似位置，在整个过程中使用所有mip，最终线程会从中取出大块，然后缓慢使用更详细的mip查找k所在的每个像素值。

如果所有内容都再次实例化，那么每个阈值发现都需要一个线程，这样做更有意义。(假设您同时运行128x128次ANN（平移不变性？），那么这是完全合理的。

并且达到该计数的阈值高度，但它是近似的...所以您会得到一个近似的k，用于n个列表。

您可以做更多工作以获得精确的k，在相似匹配中，但如果您可以接受它是近似的，例如如果它正在获取前~k个激活，则不要担心它。

- Magnus Robert Carl Wootton

但是Mag！为什么拥有近似的前K个结果很重要呢？我认为这对于更便宜的相似度匹配非常重要！！！ - Magnus Robert Carl Wootton

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aryabhatta · Accepted Answer

方法1

由于k很小，您可以使用锦标赛方法找到第k大的元素。此方法在Knuth的《编程之美》第3卷第212页中有描述。

首先，在n-k+2个元素上创建一个锦标赛，就像击败网球锦标赛一样。首先将其分成一对，并比较这对成员（好像这两个人打了一场比赛并输了一个）。然后，将获胜者再次分成一对，以此类推，直到你有一个获胜者。您可以将其视为一棵树，获胜者在顶部。

这需要恰好进行n-k + 1次比较。

现在这n-k+2个中的获胜者不能是您的第k大元素。考虑它在锦标赛中向上路径P。

从剩下的k-2个中选择一个，并沿着路径P跟随它，这将给您一个新的最大值。基本上，您重新排序以前的获胜者被k-2个元素之一替换时锦标赛。让P成为新获胜者的路径。现在从k-3中选择另一个并跟随新路径，以此类推。

在你排除前k-2个元素后，将最大值替换为负无穷大，竞赛中的最大值将是第k个最大值。你舍弃的元素是前k-1个最大的。

这需要最多n - k + (k-1) [log (n-k+2)]次比较才能找到前k个最大值。虽然它使用O(n)内存。

就比较次数而言，这应该可以击败任何一种选择算法。

方法二

作为另一种选择，你可以维护一个k个元素的小根堆。

首先插入k个元素。然后对于数组的每个元素，如果它小于堆的最小元素，则丢弃它。否则，删除堆的最小值并插入来自数组的元素。

最后，堆将包含前k个最大元素。这将需要O(n log k)次比较。

当然，如果n很小，只需对数组进行排序就足够了。代码也会更简单。