的Python：發現含有X列表

我有數據的類似形式的巨大的名單，1M以上的記錄（雖然這是一個非常簡單的形式）項的指標是：的Python：發現含有X列表

[ 
    {'name': 'Colby Karnopp', 'ids': [441, 231, 822]}, 
    {'name': 'Wilmer Lummus', 'ids': [438, 548, 469]}, 
    {'name': 'Hope Teschner', 'ids': [735, 747, 488]}, 
    {'name': 'Adolfo Fenrich', 'ids': [515, 213, 120]} 
    ... 
]

給定一個id爲735，我想找到Hope Teschner的索引2，因爲給定的id屬於Hope的id列表。什麼是最好的（性能明智）的方式來做到這一點？

感謝您的任何提示。

編輯

也許應該提到這一點，但一個ID 可能出現不止一次。如果一個特定的ID 確實不止一次出現，我希望給定ID的最低索引。

列表中的數據將會頻繁更改，所以我對構建字典感到猶豫不決，因爲字典需要修改/重建每次更新列表，因爲索引是字典中的值 - 即。更改列表中某個項目的位置將需要更新字典中的每個值，其索引大於新更改的索引。

編輯編輯

我只是做了一些基準，似乎重建字典是相當快的甚至超過100萬的記錄。我想我現在會繼續尋求這個解決方案。

來源

2009-12-29 sberry

一般來說，任何能夠提高搜索性能的任何東西都需要你排序，或者創建一個單獨的散列表等等。所以最重要的問題是......你需要訪問多少次這個清單？這是建立一次，並多次訪問？我不是一個蟒蛇開發者，所以我只是在那裏談論普遍性。 – 2009-12-29 17:48:02

拿到第一指標滿足條件（在Python 2.6或更高

最簡單的方法：

next((i for i, d in enumerate(hugelist) if 735 in d['ids']), None)

這給None如果項目不符合條件;更通常，你可以把作爲第二個參數在這種情況下，無論您需要什麼，都可以嵌入next，或者省略第二個參數（在這種情況下，您可以刪除一組括號），如果沒有項目滿足條件的情況下可以獲得StopIteration異常（例如，您知道這種情況是不可能的）

如果您需要在hugelist或其內容的更改之間進行此類操作的次數超過幾次，那麼，如您在對問題的第二次編輯中指出的那樣，建立一個輔助字典（從整數到第一個字典的索引，包含它）是優選的。既然你想要的第一適用的指標，你想向後遍歷（所以命中更接近的hugelist開始將覆蓋那些進一步上） - 例如：

auxdict = {} 
L = len(hugelist) - 1 
for i, d in enumerate(reversed(hugelist)): 
    auxdict.update(dict.fromkeys(d['ids'], L-i))

[你不能使用reversed(enumerate(...，因爲enumerate返回一個迭代器，而不是一個列表，並且reversed被優化爲僅對一個序列參數起作用 - 因此需要L-i]]。

可以其他方式構建auxdict，包括但反轉，例如：

auxdict = {} 
for i, d in enumerate(hugelist): 
    for item in d['ids']: 
    if item not in auxdict: auxdict[item] =i

但這很可能是慢得多，由於在內部循環執行的if數量龐大。直接dict構造函數（以鍵的順序，值對）也可能會比較慢，因爲需要內部循環：

L = len(hugelist) - 1 
auxdict = dict((item, L-i) for i, d in enumerate(reversed(hugelist)) for item in d['ids'])

但是，這些都只是定性的考慮 - 考慮在幾個運行基準您可以在hugelist（在命令行提示符下使用timeit，正如我經常推薦的那樣）的「典型/代表性」示例的值爲度量這些方法的相對速度（以及它們的運行時間與我在這個答案開始時顯示的一個獨立查詢 - 這個比率，加上你期望在連續hugelist變化之間執行的平均查找次數，wi將幫助您選擇整體戰略）。

來源

2009-12-29 18:41:30

從性能上看，如果您有1M條記錄，則可能需要切換到數據庫或不同的數據結構。對於給定的數據結構，這將是一個線性時間操作。你可以創建一個ID來記錄一次，但如果你打算經常這樣做。

來源

2009-12-29 17:42:29 Pace

最好的方法可能是設置一個反向字典（）從ID到名稱。

來源

2009-12-29 17:43:28

兩個或多個字符可以共享相同的ID嗎？如果是這樣，我認爲你需要返回一個索引列表。

如果你想要做一個一次性的搜索，那麼你可以用一個列表理解做到這一點：

>>> x = [ 
... {'name': 'Colby Karnopp', 'ids': [441, 231, 822]}, 
... {'name': 'Wilmer Lummus', 'ids': [438, 548, 469]}, 
... {'name': 'Hope Teschner', 'ids': [735, 747, 488]}, 
... {'name': 'Adolfo Fenrich', 'ids': [515, 213, 120]}, 
     ... 
... ] 

>>> print [idx for (idx, d) in enumerate(x) if 735 in d['ids']] 
[2]

但是，如果你想這樣做了很多，列表不會有太大變化則是創建一個反向索引要好得多：

>>> indexes = dict((id, idx) for (idx,d) in enumerate(x) for id in d['ids']) 
>>> indexes 
{213: 3, 515: 3, 548: 1, 822: 0, 231: 0, 488: 2, 747: 2, 469: 1, 438: 1, 120: 3, 441: 0, 735: 2} 
>>> indexes[735] 
2

注意：上面的代碼假定每個ID都是唯一的。如果有重複項，則使用collections.defaultdict（list）替換字典。

NNB：上面的代碼將索引返回到原始列表中，因爲這是您要求的。但是，除非您想使用索引從列表中刪除它，否則最好返回實際的dict而不是索引。

來源

2009-12-29 18:08:54

如果建索引的頻率低：

創建索引值的查找數組到主列表中，這樣如

lookup = [-1,-1,-1...] 

... 
def addtolookup 
... 

mainlistindex =lookup[myvalue] 
if mainlistindex!=-1: 
name=mainlist[mainlistindex].name

如果frwquency高，考慮排序方法（我認爲這就是Schwartzian變換的答案）。如果您在源列表更改時重建樹的性能遇到更多問題，則可能比使用製造索引獲取數據的性能更好;作爲將數據插入現有列表（關鍵地知道關於其他可能的匹配的id，用於當先前的最佳匹配字符串停止與id關聯時）將比在每個增量上從頭開始構建列表更快。

編輯

這假定你的ID是人口稠密的整數。

爲提高訪問排序列表的性能，可以將它劃分爲400-600個條目的塊，以避免將整個列表反覆向前或向後移動一個或幾個位置，並用二進制算法進行搜索。

來源

2009-12-29 18:23:21 martinr

似乎數據結構不適合其使用。更改列表代價昂貴 - 無論是更改本身（如果您執行任何插入/分隔）以及由此產生的需要重新生成字典，或者每次都進行線性掃描。

現在的問題是：如何更改？

也許不是使用索引（頻繁更改），您可以使用對象，並使用指向對象本身的指針而不是擔心索引？

來源

2009-12-30 17:34:47

的Python：發現含有X列表

回答

相關問題