Python - 大列表效率

我有一個函數，unique(a)需要一個數字列表，a，並且只返回每個值中的一個。同時，它維護列表的順序。我還有一個功能，big_list(n)生成len(n)的列表。Python - 大列表效率

爲什麼我改變列表的方向的原因是，當刪除值時，它將它們從原始列表的後面刪除，以便使修改列表在與原始列表進行比較時更加乾淨和易讀。

該函數在我創建的列表的長度相對較小時起作用，但是當我獲得更大的長度時，例如ex爲1,000,000，則執行時間爲FOREVER。

如果任何人都可以通過使我的功能快很多來幫助我，那會很棒！

僅供參考：我需要在函數的某個地方爲我正在處理的任務使用一個集合。我仍然需要從後面刪除列表項。

提前致謝！

def big_list(n) : 
    # Create a list of n 'random' values in the range [-n/2,n/2] 
    return [ randrange(-n//2, n//2) for i in range(n) ] 

def unique(a) : 
    a = a[::-1] 
    b = set(a) 
    for i in b : 
     while a.count(i) != 1 : 
      a.remove(i) 
      a.count(i) 
    a = a[::-1] 
    return a

來源

2014-10-06 Evan Cooper

設置已經是唯一的。它不會包含重複項。即x = set（big_list（10k）），x將不會有重複。 – Claris 2014-10-06 21:46:42

是不是它使時間複雜性成爲最糟糕的例子？ – 2014-10-06 21:47:35

你的算法做了很多額外的工作來移動元素。試想一下：

def unique(a): 
    b = set() 
    r = [] 
    for x in a: 
     if x not in b: 
      r.append(x) 
      b.insert(x) 
    return r

來源

2014-10-06 21:45:23

謝謝！迭代列表時創建新列表通常更好，就像您在示例中做的那樣？ – 2014-10-06 21:54:27

Python在創建新列表時非常高效。另一種做法是做大量'.remove（）'操作，它必須將元素轉移很多，特別是如果你有很多元素需要逐個刪除。 – 2014-10-06 22:04:05

每次調用a.count(i)它遍歷整個列表以計數的出現時間。這是一個O（n）操作，您一遍又一遍地重複。如果考慮外部循環的O（n）運行時間，則總體算法複雜度爲O（n ）。

這不會幫助while循環內有第二個不必要的a.count(i)。這個電話沒有做任何事情，但咀嚼時間。

整個問題都可以在O（n）時間完成。你最好的選擇是完全避免list.count()，並找出如何循環遍歷列表並自己計算元素。如果你聰明，你可以在一次完成所有事情，不需要嵌套循環（或隱式嵌套循環）。

來源

2014-10-06 21:45:51

感謝您的諮詢！ – 2014-10-06 21:55:31

您可以在this address找到「獨特」功能的全面基準。我個人最喜歡的是

def unique(seq): 
    # Order preserving 
    seen = set() 
    return [x for x in seq if x not in seen and not seen.add(x)]

，因爲它是最快的，它保留秩序，同時利用套巧妙。我認爲這是f7，它在評論中給出。

來源

2014-10-06 21:46:32

我曾經看過那個頁面，除了我沒有意識到有一個f7。謝謝！ – 2014-10-06 21:57:28

Python - 大列表效率

回答

相關問題