1. 首頁
  2. 問答
  3. 爲什麼關鍵字搜索比通過python字典進行迭代更快

爲什麼關鍵字搜索比通過python字典進行迭代更快

2017-03-01 48 views
1

我並沒有從根本上理解爲什麼在字典中搜索關鍵字比遍歷字典關鍵字來查找匹配關鍵字更快。我想象一下當在python中搜索一個類似key in dict的密鑰時，後臺代碼將遍歷鍵來查找匹配項。那麼爲什麼手動使用for i in dict: key == i之類的東西會更慢呢？爲什麼關鍵字搜索比通過python字典進行迭代更快

來源

2017-03-01 The Nightman

+0

「我想，尋找與在dict'後臺代碼像'鍵蟒蛇一個鍵時，將通過按鍵來迭代來尋找匹配」 - [你想象的錯（HTTPS：/ /en.wikipedia.org/wiki/Hash_table）。 – user2357112

+0

[排序和搜索]（https://www.amazon.com/dp/0201896850）。通過適當選擇算法和數據結構，您可以找到log（n）或更少的內容。 – jww

+1

另請參閱[這裏]（http://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table）和其他許多關於如何實現字典/集合查詢的問題性能。 – TigerhawkT3

回答

3

因爲python中的字典是使用散列表實現的。想象一下類似於關係數據庫中的索引，這使得關鍵的查找操作更快。

Reference

來源

2017-03-01 01:10:50 JavoSN

3

你想象得不對：搜索單個鍵使用散列函數，因此它是間接引用（兩步計算）到內存中所需的位置。將其視爲數組形式的參考

array[hash_function(key)]

來源

2017-03-01 01:08:31 Prune

相關問題

 相關問題