我為在整數串列中查找第二大項的簡單任務撰寫了這個簡單的代碼：
def second_largest(input_list):
input_list.sort()
return input_list[-2]
但是，對于大型串列，此功能可能真的無效，例如一百萬個專案的運行時間超過 1.5 秒。
我知道這是由于函式更改了串列本身（使用 .sort 方法），這對于長串列可能非常低效。如何在不使用更改串列的低效方法的情況下執行此任務？
謝謝大家。
uj5u.com熱心網友回復：
以下情況如何：
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
它只遍歷一個可迭代物件一次，所以我希望它是有效的。（這假設串列至少有兩個專案。）
uj5u.com熱心網友回復：
我發現基于的解決方案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]
嗯……慢得多
最后一個
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
這個問題很好地解釋了為什么這個解決方案更快。原因是您只使用np.argpartition而不是完全排序串列執行部分排序。
uj5u.com熱心網友回復：
彈出max，再次找到max：
my_list.pop(my_list.index(max(my_list)))
max(my_list)
uj5u.com熱心網友回復：
正如@juanpa.arrivillaga 提到的，我們可以使用堆佇列演算法的heapq.nlargest 方法
import heapq
data = list(range(100))
data.append(100)
print(heapq.nlargest(2, data)[1])
輸出：
99
免責宣告：
如果資料包含重復值，它將回傳唯一的第二大元素。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/410080.html
標籤：
上一篇：我應該使用什么集合來組合最快的鍵檢索，以及c#中最快的排序列舉？
下一篇：帶有可移動邊框的Qt框架