从运行流中无限个元素的数组中返回最大k个元素的优化算法

Question

我有一个运行的整数流，如何在任何时间点从这个流中获取最大的k个元素。

Answer 1

import heapq
def klargestelements(arr1,k):
    q=heapq.nlargest(k,arr1)
    return q
k=3
arr1=[1,2,4,5,6,7]
m=klargestelements(arr1,k)
print(m)

nsmallest或nlargest方法接受参数k和要在其中找到最小/最大元素的数组

Answer 2

这个问题也被称为重击者。计数草图数据结构是解决这个问题的方法。

参考:

< Li > https://en . Wikipedia . org/wiki/Count–min _ sketch

Answer 3

最简单的解决方案是填充大小为 k 的最小堆。

首先，用前 k 个元素填充堆。

接下来，对于流中的每个元素 - 检查它是否大于堆的头部，如果是 - 弹出当前头部，然后插入新元素。

在流期间的任何点-堆包含最大的< code>k个元素。

此算法为 O（nlogk），其中 n 是到目前为止在流中遇到的元素数。

另一种解决方案，稍微复杂一点，但在某些情况下理论上在渐近复杂度方面更好，是保存一个2k元素的数组。

首先，加载前 2000 个元素。
运行选择算法，并从中找到最高的 k。丢弃其余部分，此时数组中只剩下 k 个元素。
现在，用接下来的k个元素再次填充数组，然后重复。

在每个点上，数组都包含k最大的元素，以及最多k更多不是最大的元素。您可以为此数组上的每个查询运行选择算法。

运行时分析：

维护数组：每个选择算法都是 O（2k） = O（k）。<这是每k个元素完成一次，所以n / k乘以n，如果n表示到目前为止看到的元素数量，这给了我们O（n / k * 2k） = O（n）。

此外，每个查询都是< code>O(k)，如果查询的数量是< code>Q，这就给出了< code>O(n Q*k)的运行时间。

为了使这个解决方案更有效，我们需要Q * k

Q*k < nlogk
Q < n/k * logk

因此，如果查询的数量如上所述是有限的，这个解决方案在渐近复杂性方面可能更有效。

在实践中，获取top k通常是通过使用最小堆解决方案来完成的，至少在我认为需要的地方是这样。