如何检查是否一个键/值是用Python

Question

其他地方重复一本字典我有一本字典在python，如：

dict = {'dog':['milo','otis','laurel','hardy'], 
     'cat':['bob','joe'], 
     'milo':['otis','laurel','hardy','dog'], 
     'hardy':['dog'],'bob':['joe','cat']} 

...我想确定是否一个键在字典中存在别处（在其他一些值列表中）。还有其他问题我可以找到，想知道一个项目是否存在于字典中，但这不是我的问题。对于每个值列表中的项目也是如此，以识别ORK中不存在的项目以及它们在字典中的相关值。

在上面的例子中，想法是狗和猫不相同，它们的键/值与来自猫的没有共同之处。理想的情况下，第二个字典将被创建，收集所有与每一个独特的集群相关的那些：

unique.dict = {'cluster1':['dog','milo','otis','laurel','hardy'], 
       'cluster2':['cat','bob','joe'] } 

这是一个后续问题In Python, count unique key/value pairs in a dictionary

Answer 1

看起来这种关系是对称的，但是你的数据不是（例如没有钥匙'otis'）。第一部分涉及使其对称，所以我们从哪里开始并不重要。

（如果你的数据实际上是对称的，那么跳过这一部分。）

的Python 2.7

from collections import defaultdict 

data = {'dog':['milo','otis','laurel','hardy'],'cat':['bob','joe'],'milo':['otis','laurel','hardy','dog'],'hardy':['dog'],'bob':['joe','cat']} 

# create symmetric version of data 
d = defaultdict(list) 
for key, values in data.iteritems(): 
    for value in values: 
     d[key].append(value) 
     d[value].append(key) 

visited = set() 
def connected(key): 
    result = [] 
    def connected(key): 
     if key not in visited: 
      visited.add(key) 
      result.append(key) 
      map(connected, d[key]) 
    connected(key) 
    return result 

print [connected(key) for key in d if key not in visited] 

的Python 3。3

from collections import defaultdict 

data = {'dog':['milo','otis','laurel','hardy'],'cat':['bob','joe'],'milo':['otis','laurel','hardy','dog'],'hardy':['dog'],'bob':['joe','cat']} 

# create symmetric version of data 
d = defaultdict(list) 
for key, values in data.items(): 
    for value in values: 
     d[key].append(value) 
     d[value].append(key) 

visited = set() 
def connected(key): 
    visited.add(key) 
    yield key 
    for value in d[key]: 
     if key not in visited: 
      yield from connected(value) 

print([list(connected(key)) for key in d if key not in visited]) 

结果

[['otis', 'milo', 'laurel', 'dog', 'hardy'], ['cat', 'bob', 'joe']] 

性能

O(n)，其中n是data（键和值的总数在您的情况，17，如果我算正常）。

Answer 2

我取“的价值的其他名单”从字面上来说，意味着它的自己的组中的一个键是OK的。如果没有，那会让事情稍微简单一些，但你应该能够自己调整代码，所以我不会写这两种方式。

如果你坚持使用这种数据结构，你有蛮力去做：

def does_key_exist_in_other_value(d, key): 
    for k, v in d.items(): 
     if k != key and key in v: 
      return True 

你当然可以浓缩到这一个班轮与genexpr和any：

return any(key in v for k, v in d.items() if k != key) 

但是更聪明的做法是使用更好的数据结构。至少使用set而不是列表作为你的值（这不会简化你的代码，但会使它快得多 - 如果你的值中有K个键和V个总元素，它将以O（K）运行，而不是O（KV）

不过说真的，如果你想看看东西，建立一个字典查找东西在：

inv_d = defaultdict(set) 
for key, value in d.items(): 
    for v in value: 
     inv_d[v].add(key) 

而现在，你的代码只是：

def does_key_exist_in_other_value(inv_d, key): 
    return inv_d[key] != {key}