如何高效地在defaultdict中進行反向查找？

Question

在發佈這個問題之前，我做了一些搜索，似乎有幾種不同的方法來完成這一點。

但是，什麼是目前（使用Python 3）來搜索基於在defaultdict看起來（東西）的特定價值的關鍵是這樣的最有效的方式：我想找到所有

defaultdict(list, 
      {'a': [[2, 3], [1, 2]], 
      'b': [[5, 6]], 
      'w': [[]], 
      'x': [[9]], 
      'z': [[5, 6]]}) 

鍵的值爲6.一種解決方法是編寫一個嵌套的for循環，該循環遍歷關鍵值defaultdict的值，但我相信有更好的方法來實現這一點。

Answer 1

您可以使用chain.from_iterable從itertools模塊這樣的例子：

from itertools import chain 

a = defaultdict(list, 
      {'a': [[2, 3], [1, 2]], 
      'b': [[5, 6]], 
      'w': [[]], 
      'x': [[9]], 
      'z': [[5, 6]]}) 

keys = [k for k, v in a.items() if 6 in chain.from_iterable(v)] 
print(keys) 

或者，在更緊湊的方式，你可以定義你的defaultdict的價值觀做了查找功能：

def get_keys(a, key=6): 
    return [k for k, v in a.items() if key in chain.from_iterable(v)] 

keys = get_keys(a) 
print(keys) 

輸出：

['b', 'z'] 

Answer 2

如果你正在做幾個查找（和in the comments you said你打算做幾件），這可能是有用的實際創建逆轉defauldict：

from collections import defaultdict 

inp = defaultdict(list, {'a': [[2, 3], [1, 2]], 'b': [[5, 6]], 'w': [[]], 'x': [[9]], 'z': [[5, 6]]}) 

res = defaultdict(set) 

for key, vallist in inp.items(): 
    for valsublist in vallist: 
     for val in valsublist: 
      res[val].add(key) 

然後就是訪問res做查找。

例如：

>>> res[6] 
{'z', 'b'} 

>>> res[2] 
{'a'} 

你總是需要遍歷所有在您所有的defaultdicts值的項目（這需要O(n)其中n是所有值列出了所有項目的數量）。但是在字典中查找關鍵字（主要是）O(1)。所以如果你打算做幾個查詢，說k，然後多次迭代需要O(n*k)，但將它轉換爲另一個字典將只有O(n + k)。至少假設set.add操作是O(1)，應該是這種情況（除了一些 - 非常罕見的病態病例）。