Python FInd過去k項中的最大數字

給定一個整數數組和一個整數值K我的任務是編寫一個函數，該函數向標準輸出輸出該數組中最高的數值以及之前的K個條目。Python FInd過去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)

來源

2015-01-09 kilojoules

我不明白你的輸入如何給出輸出。爲什麼你會得到多個'9'和'7'？ – 2015-01-09 22:37:38

@Adam：對於數組的每個成員，它將打印過去K個成員（包括當前成員）的最大值。 – Ani 2015-01-09 22:41:37

您可以使用max堆，最多包含k個元素（http：//en.wikipedia。組織/維基/ Heap_（data_structure））。複雜性是O（nlogk），我相信它是最優的。 – Jarlax 2015-01-09 22:45:24

您可以使用單調隊列（對任意k值的O（n））實現線性時間複雜度。這個想法如下：

讓我們保持雙對數值（值，位置）。最初，它是空的。
當新元素到達時，請執行以下操作：當前元素的位置超出範圍（小於i - K）時，彈出它。雖然back元素的值小於新元素，但請彈出它。最後，將一對（當前元素，它的位置）推到deque的後面。
當前位置的答案是雙側的前置元素。

每個元素只添加到deque中一次，最多刪除一次。因此，時間複雜度是線性的，並且不依賴於K.這個解決方案是最優的，因爲只是讀取輸入是O（n）。

來源

2015-01-09 22:59:43 kraskevich

這是一個很好的答案。該deque的最大大小是k + 1吧？這也意味着它可以通過圓形陣列高效地實現。 – 2015-01-10 01:06:48

@Anonymous是的，它是k + 1. – kraskevich 2015-01-10 05:18:34

@Anonymous True，或者使用Python的內置['deque']（https://docs.python.org/2/library/collections.html#collections.deque）類。 – augurar 2015-01-17 10:04:50

大熊貓可以做到這一點非常好：

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

來源

2015-01-09 22:43:14 acushner

他要求算法，而不是工具。 – augurar 2015-01-09 22:43:35

他在問如何使它適用於大型數據集，這是一個很好的答案。 – acushner 2015-01-09 22:45:41

@acushner我想Augurar的解釋。這個問題被標記爲「算法」，這表明問題是要求算法而不是庫函數。 – 2015-01-10 01:13:57

嘗試使用heap達到降低最大操作的複雜性，從O(K)到O(logK)時間。

添加第一(-tps[i]) *，i in range(0,k)和輸出(-heap[0])每次
下一個Nk個號碼，你應該在堆中添加tps[i]刪除tps[i-k]和打印(-heap[0])

總的來說你得到一個Ø （N log（K））算法，而你現在使用的是O（N * K）。如果K不小，這將非常有用。

*由於堆的實現將堆[0]中的min（堆）作爲一個不變量，因此如果添加-value，-heap[0]將是您想要的max(heap)。

來源

2015-01-09 22:51:00 pankgeorg

這是更好但不是最優的，您可以爲此操作實現分期O（1）複雜性。（請參閱[ILoveCoding的答案]（http://stackoverflow.com/a/27870655/2572431）） – augurar 2015-01-09 23:28:19

Python FInd過去k項中的最大數字

回答

相關問題