在 Python 的列表中查找第二大项的更有效方法

Question

我编写了这个简单的代码来完成在整数列表中查找第二大项的简单任务：

def second_largest(input_list):
  input_list.sort()
  return input_list[-2]

但是，对于大型列表，此功能可能真的无效，例如，运行一百万项的时间超过 1.5 秒。

我知道这是因为函数 更改了列表本身 （使用 .sort 方法），这对于长列表来说效率非常低。如何在不必使用更改列表的低效方法的情况下执行此任务？

谢谢大家的提前。

Answer 1

下面的怎么样：

lst = list(range(1000000))

largest, second_largest = sorted(lst[:2])
for x in lst[2:]:
    if x > largest:
        largest, second_largest = x, largest
    elif x > second_largest:
        second_largest = x
print(largest, second_largest) # 999999 999998

它只遍历一个iterable一次，所以我希望它是高效的。（假设列表至少有两个项目。）

Answer 2

弹出最大值，再次求最大值：

my_list.pop(my_list.index(max(my_list)))
max(my_list)

Answer 3

如@juanpa.arrivillaga所述，我们可以使用堆队列算法的heapq.nlargest method

import heapq

data = list(range(100))
data.append(100)
print(heapq.nlargest(2, data)[1])

输出：

免责声明：

如果数据包含重复值，它将return唯一的第二大元素。

Answer 4

我发现基于 np.argpartition 的解决方案是最快的。它确实需要 Numpy，但它没有考虑将列表转换为 numpy 数组。但是，最后，如果您希望进一步处理数字，您可能需要使用 numpy 数组，因为对这些数组的操作通常比对列表的操作快得多。所以我假设你就是这种情况。

首先，您应该将列表转换为数组：

import numpy as np
v = list(range(10000000))
var = np.array(v)

然后我们可以使用np.argpartition

%%time
ind = np.argpartition(var, -2)[-2]

CPU times: user 46.3 ms, sys: 25.9 ms, total: 72.2 ms
Wall time: 71.7 ms

ind = 9999998，所以结果似乎是正确的。

现在，如果我们与此处的其他建议进行比较：

%%time
v.pop(v.index(max(v)))
max(v)

CPU times: user 619 ms, sys: 1.96 ms, total: 621 ms
Wall time: 623 ms

大约慢 10 倍

%%time
heapq.nlargest(2,v)[1]

CPU times: user 2.66 s, sys: 1.84 ms, total: 2.66 s
Wall time: 2.66 s

嗯……慢多了

最后一个

largest, second_largest = v[0], v[0]
for x in v:
    if x > largest:
        largest, second_largest = x, largest
    elif x > second_largest:
        second_largest = x
print(largest, second_largest) # 999999 999998

CPU times: user 1.41 s, sys: 0 ns, total: 1.41 s
Wall time: 1.41 s

同样，慢很多倍。

如果您计划在某个地方使用数组，np.argpartition 解决方案似乎是最快的。否则，您将花费大量 CPU 时间将您的列表转换为您不会再次使用的数组（见下文）。尽管如此，它仍然优于其他一些解决方案。如果我们考虑到数组的转换，我们会得到这个结果：

%%time
var=np.array(v)
ind = np.argpartition(var, -2)[-2]

CPU times: user 867 ms, sys: 59 ms, total: 926 ms
Wall time: 924 ms

This question 很好地解释了为什么这个解决方案更快。原因是您仅使用 np.argpartition 执行部分排序，而不是对列表进行完全排序。

在 Python 的列表中查找第二大项的更有效方法

More Efficient Way to find the Second Largest Item in a List in Python

python

performance