我的目標是在一個大的串列串列中有效地找到包含某個值的元素的索引（讓我們以 100 萬個條目為例，每個條目是一個由 3 個元素組成的串列）：
例如，讓我們拿清單a
a = [[0,1,2],[0,5,6],[7,8,9]]
我想檢索包含值 0 的元素的索引，因此我的函式將回傳0,1
我的第一次嘗試如下：
def any_identical_value(elements,index):
for el in elements:
if el == index:
return True
return False
def get_dual_points(compliant_cells, index ):
compliant = [i for i,e in enumerate(compliant_cells) if any_identical_value(e,index)]
return compliant
result = get_dual_points(a,0)
該解決方案可以正常作業，但對于大量串列來說效率非常低。特別是我的目標是執行一些查詢，即主串列中值的總數，因此n_queries = len(a)*3，在上面的示例中為 9。
這里有2個問題：
- 串列是完成這項任務的良好資料結構嗎？
- 有沒有更高效的演算法解決方案？
uj5u.com熱心網友回復：
您可以一次性散列所有索引（單O(N)次通過），這樣您就可以及時回答查詢O(1)。
from collections import defaultdict
d = defaultdict(list)
a = [[0,1,2],[0,5,6],[7,8,9]]
queries = [0,1]
for i in range(len(a)):
for element in a[i]:
d[element].append(i)
for x in queries:
print(d[x])
# prints
# [0, 1]
# [0]
uj5u.com熱心網友回復：
這是一個建議的演算法：在串列串列上迭代一次，以構建一個將每個唯一元素映射到它所屬子串列的所有索引的字典。
使用這種方法，構建字典所需的時間與串列串列中的元素總數成正比。然后每個查詢都是恒定時間的。
這需要一個串列的字典：
def dict_of_indices(a):
d = {}
for i,l in enumerate(a):
for e in l:
d.setdefault(e, []).append(i)
return d
a = [[0,1,2],[0,5,6],[7,8,9]]
d = dict_of_indices(a)
print( d[0] )
# [0, 1]
uj5u.com熱心網友回復：
您可以創建一個字典，將一個值映射到一組行索引。然后，對于每個查詢，您可以簡單地查找該值，如果它在 2D 串列中的任何位置都不存在，則回傳一個空集：
from itertools import product
a = [[0,1,2],[0,5,6],[7,8,9]]
values = {}
for row, col in product(range(len(a)), range(len(a[0]))):
value_at_index = a[row][col]
values.setdefault(value_at_index, set()).add(row)
print(values.get(0, set()))
這輸出：
{0, 1}
如果您事先知道每個子串列中的元素是唯一的，那么您可以將字典更新行更改為：
values.setdefault(value_at_index, []).append(row)
并將.get()呼叫更改為：
values.get(0, [])
保持輸出中索引的順序。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/464737.html
下一篇：這個演算法是如何實作滑動視窗的？