有沒有辦法使用O（1）中的一個鍵獲取值時間

我正在爲應用程序建模數據，並決定選擇字典作爲我的數據結構。但數據中的每一行都有多個鍵。所以，我創建了多個鍵映射字典的每一行，是這樣的：有沒有辦法使用O（1）中的一個鍵獲取值時間

>>> multiKeyDict = {} 
>>> multiKeyDict[('key1','key2','key3')] = 'value1' 
>>> multiKeyDict.get(('key1','key2','key3')) 
'value1'

現在我必須與爲O key1（1）時間檢索所有的值。從我的研究，我知道我能做到：

使用this包來完成這項工作，但不知道這是否是O（1）
搜索鍵作爲這裏建議：https://stackoverflow.com/a/18453567/4085019

我也打開任何更好的數據結構，而不是使用字典。

來源

2017-03-09 PseudoAj

沒有，沒有。 –

您提到的軟件包會將鍵列表映射到相同的值。如果我正確理解你的問題，你想要更多某種層次結構？ –

爲什麼不製作2個字典？ 1如'{ 'KEY1'：[ 'VALUE1'， '值2']}'和一個像'{ '值1'：[ 'KEY1'， 'KEY2']}' –

您沒有多個密鑰。就Python字典而言，只有一個鍵，一個元組對象。除了O（N）線性時間之外，您不能搜索元組的元素。

如果你的鑰匙都是獨一無二的，只需要添加每個鍵單獨：

multiKeyDict['key1'] = multiKeyDict['key2'] = multiKeyDict['key3'] = 'value1'

現在你有3個按鍵全部引用一個值。值對象在這裏不重複，只有它的引用。

您找到的multi_key_dict包使用中間映射將給定的組成鍵映射到組合鍵，然後映射到該值。這也給你O（1）搜索，同樣的限制，每個組成鍵必須是唯一的。

如果你的密鑰不獨特的，那麼你需要映射每個鍵到另一個容器中，然後保存值，就像一組例如：

for key in ('key1', 'key2', 'key3): 
    multiKeyDict.setdefault(key, set()).add(value)

現在找了一個鍵爲您提供了一套所有關鍵參考值。

如果您需要也可以組合鍵，那麼您可以添加其他引用與這些組合。關鍵值配對相對便宜，都只是參考。鍵和值對象本身不重複。

來源

2017-03-09 14:51:56

'key1'可能有多個值，我不想將值映射到每個鍵，因爲它不會隨數據擴展 – PseudoAj

@PseudoAj：那麼您沒有適合散列表的數據，並且卡住了通過線性搜索這個數據結構。這同樣適用於你找到的'multi_key_dict'包。 –

是的，這也是我的感覺...... – PseudoAj

另一種可能性是對共享關鍵組件的行對象列表建立索引。如果共享任何特定鍵值的行數很少，這將非常有效。（假設行對象有鍵訪問爲row.key1,row.key2等，這不是一個非常相關的細節）。未經測試的代碼：

index = {} 
for row in rows: 
    index.setdefault(row.key1, []).append(row) 
    index.setdefault(row.key2, []).append(row) 
    index.setdefault(row.key3, []).append(row)

，然後查找匹配，比如說行，key2和key3

candidates = index[ key2] 
if len(index[key3]) < len(candidates): 
    candidates = index[key3] # use key3 if it offers a better distribution 
results = [] 
for cand in candidates: 
    if cand.key2 == key2 and cand.key3 == key3: # full test is necessary! 
     results.append(cand)

來源

2017-03-09 15:24:22 nigel222

有沒有辦法使用O（1）中的一個鍵獲取值時間

回答

相關問題