在python中有效地減少列表

所以我有一個85個項目的列表。我想不斷減少這個列表的一半（主要是對項目的二分搜索） - 我的問題是，什麼是減少列表最有效的方式？列表理解將持續創建不理想的列表副本。我想就地刪除我的列表範圍，直到剩下一個元素。在python中有效地減少列表

我不知道這是否是相關的，但我使用collections.deque，而不是一個標準的列表。他們可能或多或少地以相同的方式工作，所以我懷疑這個問題。

2011-06-07 Navin Aggrawal

請張貼代碼。「減少」並不清楚你的意思。 Python有一個內置的'reduce（）'函數，但你的問題似乎不相關。請提供一些代碼來解釋你的意思。 – 2011-06-07 17:32:47

您的意思是「減少」功能意義上的組合相鄰項目？或者你的意思是刪除它們？如果後者，在什麼基礎上刪除項目？ – kindall 2011-06-07 17:36:36

如果你在codereview.stackexchange.com上發佈你的代碼，你會得到很多人建議提高速度的方法。我不確定你在做什麼，但有一個更好的想法（比如通過看代碼），這聽起來像是一種可以避免「減少」列表的技術。 – 2011-06-07 18:35:59

對於僅僅85項，如實，幾乎所有你想使用的任何方法會比速度不夠快了。不要過早優化。

也就是說，根據你實際在做什麼，list可能會比deque更快。 A deque在任一端添加和刪除項目都更快，但不支持切片。

與列表，如果你想複製或刪除項目的一個連續範圍（比如，第42），您可以用切片做到這一點。假設列表的一半在每次通過時被刪除，則將項目複製到新列表的速度要比從現有列表中刪除項目要慢（刪除操作要求將未被刪除的列表的一半移到內存中的「向左」，這將是大約與複製另一半相同的時間成本，但是你並不總是需要這樣做;刪除列表的後半部分將不需要移動任何東西）。

爲了有效地使用deque做到這一點，你會想pop()或popleft()的項目，而不是切片他們（大量的屬性訪問和方法調用，這是在Python相對較貴），而且你必須寫循環控制Python中的操作，這將比本地切片操作慢。

既然你說，這基本上是一個二進制搜索，它可能是實際最快只需找到你想保留，而完全不修改原始容器中的項目，然後返回一個新的容器盛裝的是單個項目。 A list將比deque更快，因爲您將按索引執行大量訪問項目。要在deque中執行此操作，每次訪問某個項目時，Python都需要從頭開始跟蹤鏈接列表，而通過索引訪問項目對於list來說是一個簡單快速的計算。

來源

2011-06-07 18:02:56 kindall

謝謝！我結束了對二進制搜索的描述。 – 2011-06-08 17:45:02

collections.deque通過鏈表實現，因此二進制搜索將是多慢於線性搜索。重新思考你的方法。

來源

2011-06-07 17:33:59

不知道這是你真正需要的，但是：

x = range(100) 
while len(x) > 1: 
    if condition: 
     x = x[:int(len(x)/2)] 
    else: 
     x = x[int(len(x)/2):]

來源

2011-06-07 17:43:17

//操作符強制整數除法，例如。 'len（x）// 2'幾乎等價於int（len（x）/ 2）'。這種類型是強制返回的類型。那是'3 // 2.0''等於1.0 – Dunes 2011-06-07 21:24:43

85個項目甚至不值得我們深思。電腦真的很快。
爲什麼要從列表中刪除範圍，而不是簡單地選擇一個結果？
如果有一個很好的理由，爲什麼你不能這樣做（2）：保留原來的列表，並改變只有兩個指標：你看子列表的開始和結束索引。

來源

2011-06-07 18:22:50

關於前一個問題我比較了許多技術去除給予了謂詞的項目清單。（也就是說，我有一個函數返回True或False是否保留一個特定的項目。）我記得使用列表理解是最快的。事實是，複製真的很便宜。

您可以採取的唯一措施來提高速度取決於您要刪除的項目。但是你沒有提到任何有關這方面的信息，所以我不能提出任何建議。

來源

2011-06-07 18:38:40

列表理解並不便宜，因爲複製很便宜（雖然這是真的），但列表理解很便宜，因爲列表理解在C級上進行循環，它幾乎繞過了Python循環機制的一半。 – 2011-06-08 06:53:24

@賴瑞安，對。但複製是爲什麼大多數人和OP認爲它更昂貴。但是大多數人認爲複印要便宜得多。 – 2011-06-08 15:33:43

在python中有效地減少列表

回答

相關問題