Python 查找过去 k 项中的最大数

Question

给定一个整数数组和一个整数值 K，我的任务是编写一个函数，向标准输出打印数组中该值的最大数字以及它之前的过去 K 个条目。

示例输入：

tps: 6, 9, 4, 7, 4, 1
k: 3

示例输出：

有人告诉我，我编写的代码对于大型数据集可以更加高效。我怎样才能使这段代码最有效？

def tweets_per_second(tps, k):
    past = [tps[0]]
    for t in tps[1:]:
        past.append(t)
        if len(past) > k: past = past[-k:]
        print max(past)

Answer 1

pandas 可以很好地做到这一点：

import pandas as pd
df = pd.DataFrame(dict(data=[6, 9, 4, 7, 4, 1]))
df['running_max'] = pd.expanding_max(df.data)
df['rolling_max'] = pd.rolling_max(df.data, 3, min_periods=0)


print df
   data  running_max  rolling_max
0     6            6            6
1     9            9            9
2     4            9            9
3     7            9            9
4     4            9            7
5     1            9            7

Answer 2

尝试使用 heap 来实现将 max 操作的复杂度从 O(K) 降低到 O(logK) 时间。

先加(-tps[i])*，i in range(0,k)每次输出(-heap[0])
对于接下来的 N-k 个数字，您应该在堆中添加 tps[i] 删除 tps[i-k]，然后打印 (-heap[0])

总的来说你得到了一个 O(N log(K)) 的算法，而你现在使用的是 O(N*K)。如果 K 不小，这将非常有用。

*由于堆的实现将 heap[0] 中的 min(heap) 作为不变量，如果您添加 -value，则 -heap[0] 将成为 max(heap)想要。

Answer 3

您可以使用单调队列实现线性时间复杂度（对于任何 k 值，O(n)）。思路如下：

让我们维护一个双端队列（值、位置）。最初，它是空的。
当一个新元素到达时，执行以下操作：当前面元素的位置超出范围（小于i - K）时，弹出它。当后面元素的值小于新元素时，弹出它。最后，将一对（当前元素，它的位置）推到双端队列的后面。
当前位置的答案是双端队列的前端元素

每个元素只添加到双端队列一次，最多删除一次。因此，时间复杂度是线性的，它不依赖于 K。这个解决方案是最优的，因为只读取输入是 O(n)。

Python 查找过去 k 项中的最大数

Python FInd Largest number in past k items

python

algorithm