优化算法用于从长度的数组返回前k值对应N

Question

我有n个float数组，我希望返回相关的前k （在我的情况下，n〜100，K〜10）

是那么这个问题有一个已知的最优解路径？

有人可以提供一个C算法吗？

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

Answer 1

方法1

由于k较小，可以用比赛的方法找到的第k最大。该方法在Knuth的编程艺术第3卷第212页中有描述。

首先在n-k + 2元素上创建一个锦标赛。像淘汰赛网球比赛。首先你分成两对并比较对的成员（就好像这两个人打了一场比赛，一场输了）。然后获胜者，你分裂再次配对等等，直到你有一个胜利者。您可以将它视为一棵树，顶部是胜利者。

这需要n-k + 1的准确比较。

现在这些n-k + 2的获胜者不能成为你的第k个最大元素。考虑它在比赛中的路径。

其余的k-2现在选择一个，并沿着路径P，这将给你一个新的最大。基本上你可以重做比赛，而前一名获胜者将被k-2元素之一所取代。让P成为新赢家的路径。现在从k-3中选择另一个，然后沿着新的路径等等。

在耗尽k-2之后，将最大值替换为-infinity，而最大的锦标赛将成为第k最大值。你扔掉的元素是最高的k-1元素。

这最多需要n - k + (k-1) [log (n-k+2)]比较来找到顶部k。它使用O（n）内存。

根据数量比较，这应该可能击败任何选择算法。

方法2

作为替代方案，也可以保持k个元素的最小堆。

首先插入k个元素。然后，对于数组的每个元素，如果它小于堆的最小元素，则将其扔掉。否则，删除堆并从数组中插入元素。

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

当然，如果n很小，只要对数组进行排序应该足够好。代码也会更简单。

Answer 2

看看"Efficient selection and partial sorting based on quicksort"末尾讨论的部分快速排序算法。

Answer 3

您可以使用selection algorithm在O(n)中执行此操作。用分区算法找到第一个最大的元素，然后它之后的所有元素都将大于它，这些是你的最高元素k。

如果您需要排序顺序排列的顶部k，您可以按O(k log k)排序。

Answer 4

简答：没有。

较长的回答：是的，有几个互不兼容的最佳解决方案是已知的。它取决于n，k以及可以保证的数组属性。

如果对数组一无所知，复杂度的下界显然是O（n），因为必须检查源数组的所有元素，以确定它们是否适合前10位。如果您知道源数组允许元素被安全地跳过，你应该使用这些知识。因为你总是可以选择通过排序数组（O（n.log（n））和返回前10项（O（n））来找到答案， （1））

将每个项目与迄今为止找到的第十个最高值进行比较并将其插入到最高可找到的至今项目列表中的相应位置（如果需要）的线性搜索具有相似的平均复杂度和最好的情况下，并且O（kn）的最坏情况明显好于O（n-squared）。对于你估计的尺寸，我期望这种方法表现良好。

如果n更大（〜10000）和k增加的概率可能相同值得实施快速选择算法。 Quickselect可以更好地满足您想要的更多元素。但是，如果k不随n增加，你应该坚持线性搜索。 QuickSelect &朋友修改原始数组，因此如果您无法在适当位置执行此操作，则不太合适，因为您需要更多的存储空间以及算法复杂性不包含的大量复制。

如果n很大（〜1e20），您会希望从输入数组的多个分区中的每个分区中找到k个最大值，然后从这些结果的聚合中找到k-maximum，这样就不会试图分析比您一次可以放入内存中的数据更多的数据，并使操作能够高效并行化。

Answer 5

如果你有一个花哨的GPU，我可以告诉你如何在同一时间计算巨大的n个实例的顶部巨大的k，所以在每个实例的纹理上展开em，并将混合添加到纹理上他们的“高度”作为沿着纹理的位置。

但是请注意，您必须猜测一个可接受的范围或知道它，否则您不会传播到您可能拥有的最大细节。

你克隆职位。 （如果有2个，则应该有2个，如果有10个，则应该有10个）。 （只需在8192x8192纹理和64x64的这些“高度”框中说出它的全部内容），并且您还可以跳过0计数的插槽。

然后做一个平滑的添加层次结构，除非你像二叉树那样做，你只能像它的1维一样处理，所以先拿2个以前的数字并将它们加在一起，并继续为每个二进制mip做。

然后，我们使用这些mips（已收集计数）来发现k的大概位置，在过程中使用所有mips，在最终线程上执行此操作，您将从中取出大块，然后慢慢使用更详细的mips来查找每个像素的值，k位于。

这样做更有意义，如果它再次实例化，那么它是每个阈值发现的一个线程。 （只是说你一次运行安全128x128次，（平移不变任何人？），那么它是非常合理的。

并达到该计数的阈值高度，但其近似...所以你得到一个近似的k你可以做更多的工作来获得确切的k值，但是在相似度匹配中，但是如果你可以忽略它的近似值，就像它获得最高k激活值一样，那么别担心它

Answer 6

以下是基于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); 
} 

}