Python寻找过去k个元素中最大的数字

Question

给定一个整数数组和一个整数值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)

- kilojoules

---

我不明白你的输入是如何得出那个输出的。为什么会有多个“9”和“7”？ - Adam Smith

@Adam：对于数组的每个成员，它打印出过去K个成员（包括当前成员）的最大值。 - Ani

您可以使用最多k个元素的最大堆（http://en.wikipedia.org/wiki/Heap_(data_structure)） 。复杂度将为O（nlogk），我相信这是最优的。 - Jarlax

可能的重复问题：https://dev59.com/H2sz5IYBdhLWcg3wQFUq，https://dev59.com/9Woy5IYBdhLWcg3wg-Um#8499392 - augurar

@Jarlax 不对，不是最优的。最优是 O(n)。 - btilly

@btilly 你说得对，感谢指出！我不知道这种方法。 - Jarlax

Answer 1

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

1. 维护一个由数值和位置组成的双端队列，初始为空。

2. 当新元素到来时，进行以下操作:弹出前端元素的位置超出范围(小于i - K)；弹出末尾元素数值小于新元素的数值。最后，将当前元素及其位置的一对入队到队列末尾。

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

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

- kraskevich

---

这是一个很好的答案。双端队列的最大大小是k+1，这也意味着它可以通过循环数组有效地实现。 - Paul Hankin

@匿名者 是的，它是 k + 1。 - kraskevich

@Anonymous True，或者使用Python内置的deque类。 - augurar

Answer 2

尝试使用堆来实现将max操作的复杂度从O(K)降至O(logK)。

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

总体而言，您将获得一个O(Nlog(K))的算法，而您现在使用的是O(N*K)。如果K不小的话，这将非常有用。

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

- pankgeorg

---

这个方法已经比较好，但不是最优解，你可以使用摊销 O(1) 复杂度来完成这个操作。 (详见 ILoveCoding 的回答) - augurar

Answer 3

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

- acushner

---

他正在寻求一种算法，而不是工具。 - augurar

他正在问如何让它对大数据集更加高效，这是一个很好的答案。 - acushner

@acushner 我认为augurar的解释是正确的。这个问题被标记为“算法”，这表明这个问题正在寻求一个算法，而不是一个库函数。 - Paul Hankin