在比较其项目时修改字典的有效方法

Question

我有一个字典，其中字符串作为键，集合作为值。这些集合包含整数，这对于字典的不同项目可能是通用的。事实上，我的目标是将每个项目与其余项目进行比较，并在设定值中找到那些共同的数字。一旦找到一对至少在其值集中共享一个数字的项目（比方说，(key1, val1) 和 (key2, val2)），我想向字典中添加一个额外的项目，其键是两者的串联键key1和key2（我不关心顺序），其值是val1和val2中公共数字的集合。此外，val1 和 val2 中的公共数字应从该项目中删除，在最终情况下，这些集合留空，应删除该项目。

详细说明，需要示例：

我有一本这样的字典：

db = {"a": {1}, "b":{1}, "c":{2,3,4}, "d":{2,3}}

我正在寻找一个 returns 像这样的程序：

{"ab": {1}, "c":{4}, "cd": {2,3}}

我实际上有一个解决方案，但我怀疑效率很低，特别是因为我开始为字典的键和值创建两个列表，以便能够进行嵌套循环。也就是说，

db = {"a":{1}, "b":{1}, "c":{2,3,4}, "d":{2,3}}

keys = list(db.keys())
values = list(db.values())
blackList = set() #I plan to add here the indexes to be removed
for i, key in enumerate(keys):
    if i in blackList: continue
    keysToAdd = []
    valuesToAdd = []
    for j in range(i+1,len(keys)):
        if j in blackList: continue
        
        intersect = values[i].intersection(values[j])

        if len(intersect)==0: continue
        
        keysToAdd.append(key+keys[j]) #I don't care about the order
        valuesToAdd.append(intersect)

        values[i] -= intersect
        values[j] -= intersect

        if len(values[j])==0:
            blackList.add(j)

        if len(values[i])==0:
            blackList.add(i)
            break
    #out of j loop
    keys.extend(keysToAdd)
    values.extend(valuesToAdd)

#finally delete elements in the blackList
for i in sorted(blackList, reverse=True):
    del keys[i]
    del values[i]

print(dict(zip(keys, values))) #{"ab": {1}, "c":{4}, "cd":{2,3}} #I don't care about the order

我想知道我的方法是否可以改进，以获得更有效的解决方案（因为我计划有大而复杂的输入指令）。它实际上是一种使用itertools.combinations的方式吗？ - 或者也许是一种完全不同的方法来解决这个问题。提前致谢

Answer 1

我认为您的方法并不过分低效，但至少有一种稍微更快的方法可以实现这一点。我认为这对 defaultdict.

来说是件好事

from collections import defaultdict

def deduplicate(db: dict) -> dict:
    # Collect all keys which each number appears in by inverting the mapping:
    inverse = defaultdict(set)  # number -> keys
    for key, value in db.items():
        for number in value:
            inverse[number].add(key)

    # Invert the mapping again - this time joining the keys:
    result = defaultdict(set)  # joined key -> numbers
    for number, keys in inverse.items():
        new_key = "".join(sorted(keys))
        result[new_key].add(number)
    return dict(result)

使用您的示例进行比较 - 这大约快 6 倍。我不怀疑有更快的方法来实现它！

使用 itertools.combinations 将是一个合理的方法，例如，如果您知道每个数字最多可以出现在 2 个键中。因为这可能会更大 - 您需要迭代不同大小的组合，最终得到更多的迭代。

注1：我在加入新key之前已经对key进行了排序。您提到您不介意顺序 - 但在此解决方案中重要的是键是一致的，以避免 "abc" 和 "bac" 以不同的数字存在。一致的顺序也会让你更容易测试。

注意 2：从黑名单中删除值的步骤对输入有副作用 db - 所以运行你的代码两次使用相同的输入 db 会产生不同的结果。您可以通过执行 deepcopy:

在原始实现中避免这种情况

values = deepcopy(list(db.values())

Answer 2

首先创建一个倒排字典，其中每个值都映射到包含它的键。然后，对于每个值，使用组合来创建包含它的键对并从中构建结果字典：

from itertools import combinations

db = {"a":{1}, "b":{1}, "c":{2,3,4}, "d":{2,3}}

matches = dict() # { value:set of keys }
for k,vSet in db.items():
    for v in vSet: matches.setdefault(v,[]).append(k)

result = dict()  # { keypair:set of values }
for v,keys in matches.items():
    if len(keys)<2:
        result.setdefault(keys[0],set()).add(v)
        continue
    for a,b in combinations(keys,2):
        result.setdefault(a+b,set()).add(v)

print(result) # {'ab': {1}, 'cd': {2, 3}, 'c': {4}}

在比较其项目时修改字典的有效方法

Efficient way to modify a dictionary while comparing its items

python

dictionary

nested

python-3.9