Python使用集合的最快搜索算法

我正在尋找列表中搜索項目的最快方法。正如我發現在Python中，最好使用set來搜索項目，而不是使用list。所以我用set替換了list。但是，set中的所有項目都是一個對象。我想搜索是否有對象ID等於我想找到的ID。如果是，則返回該對象。Python使用集合的最快搜索算法

我可以在一個簡單的for-loop中做到這一點，但我不知道如果我仍然循環所有元素來找到該項目，怎麼可以改進設置。

def find(allItems, id): 
    for item in allItems: 
     if (item.getId() == id): 
      return item 

from sets import Set 

allItems = Set() 

allItems.add(itemObj) 

find(allItems, 1)

來源

2017-09-24 androidnewbie

使用Python字典：'allItems = {}'。您可以通過'allItems [item.getId（）] = item'添加一個項目。您可以通過'allItems [id]'快速查找它們的ID。 –

你有沒有在['sets']（https://docs.python.org/2/library/sets.html）上看到大的*「從版本2.6開始棄用」*？ 'set'是一個內置的類。但鑑於你的項目必須已經實現了'__hash__'和'__eq__'來放置在一個集合中，所以你不清楚爲什麼你需要明確檢查每個人的ID。你說得對，如果你不能使用散列，它不會比列表更有效 – jonrsharpe

那麼你能展示如何使用字典來搜索它嗎？ – androidnewbie

下面總結了如何使用python dictionary爲例。

def find(allItems, id): 
    return allItems[id] 

def addItem(allItems, item): 
    allItems[item['id']] = item 

# create a python dictionary called `allItems` 
allItems = {} 

# add some items to the dictionary 
item1 = { 'id': 1, 'name': 'James' } 
item2 = { 'id': 2, 'name': 'Susan' } 
addItem(allItems, item1) 
addItem(allItems, item2) 

# now lookup an item by its id 
result = find(allItems, 1) 
print result['name'] # ==> 'James'

如文檔explains，當你想通過自己的ID查找項目字典都不錯。

不同於序列，其是由一系列號碼索引，詞典通過鍵索引...上的詞典的主要操作是存儲與一些關鍵的值和提取給定鍵的值。

這意味着如果您知道物品的「鑰匙」 - 即物品的ID，則可立即找到該物品。沒有必要使用for循環。

來源

2017-09-24 08:40:53

使用python的設置，在那裏你分配IDS

d = { id, id2, id3, .. idN }

然後，你可以簡單地陳述if id in d驗證的元素是集合（不反覆的話）。這個工程的原因是因爲python中的Set像dict's without values（hashtable）一樣實現。這給你O（1）平均會員檢查。

s = set([1, 2, 3, 4, 5]) 

if 1 in s: 
    print 'in!' # in! is printed

弗朗採取這一answer（感謝@ juanpa.arrivillaga）

的CPython的集實現類似虛擬值字典（鍵屬於該組的成員），一些即利用這種缺乏值

或優化（S），另一種選擇是使用有序集合。（這不能與Set做這樣無論是你實現SortedSet類或使用list對象）

一個快速搜索算法是二進制搜索。（bisect module）

您可以使用此算法後您排序您的集合。

來源

2017-09-24 08:28:40 Vinny

這取決於收藏。對於'set'，情況並非如此。 –

@ juanpa.arrivillaga謝謝你指出，你是正確的。 – Vinny

Python使用集合的最快搜索算法

回答

相關問題