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

Python FInd Largest number in past k items

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

示例输入:

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

示例输出:

6
9
9
9
7
7

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

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)

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

尝试使用 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)想要。

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

  1. 让我们维护一个双端队列(值、位置)。最初,它是空的。

  2. 当一个新元素到达时,执行以下操作:当前面元素的位置超出范围(小于i - K)时,弹出它。当后面元素的值小于新元素时,弹出它。最后,将一对(当前元素,它的位置)推到双端队列的后面。

  3. 当前位置的答案是双端队列的前端元素

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