在字典中查找混合类型值的重复项

Question

我想识别字典中的重复值并将其分组。为此，我为我的数据集构建了一个伪哈希（最好阅读 signature），如下所示：

from pickle import dumps
taxonomy = {}
binder = defaultdict(list)
for key, value in ds.items():
    signature = dumps(value)
    taxonomy[signature] = value
    binder[signature].append(key)

有关具体用例，请参阅此。

不幸的是我意识到如果下面的语句是True:

>>> ds['key1'] == ds['key2']
True

这个不再总是 True：

>>> dumps(ds['key1']) == dumps(ds['key2'])
False

我注意到两个字典的转储输出的键顺序不同。如果我 copy/paste ds['key1'] 和 ds['key2'] 的输出到新词典中，我可以使比较成功。

作为一种矫枉过正的替代方案，我可以递归遍历我的数据集并将 dict 个实例替换为 OrderedDict:

import copy
def faithfulrepr(od):
    od = od.deepcopy(od)
    if isinstance(od, collections.Mapping):
        res = collections.OrderedDict()
        for k, v in sorted(od.items()):
            res[k] = faithfulrepr(v)
        return repr(res)
    if isinstance(od, list):
        for i, v in enumerate(od):
            od[i] = faithfulrepr(v)
        return repr(od)
    return repr(od)

>>> faithfulrepr(ds['key1']) == faithfulrepr(ds['key2'])
True

我很担心这种幼稚的做法，因为我不知道我是否涵盖了所有可能的情况。

我可以使用哪些其他（通用）替代品？

Answer 1

第一件事是删除对 deepcopy 的调用，这是您的瓶颈：

def faithfulrepr(ds):
    if isinstance(ds, collections.Mapping):
        res = collections.OrderedDict(
            (k, faithfulrepr(v)) for k, v in sorted(ds.items())
        )
    elif isinstance(ds, list):
        res = [faithfulrepr(v) for v in ds]
    else:
        res = ds
    return repr(res)

然而 sorted 和 repr 有其缺点：

您无法真正比较自定义类型；
您不能对不同类型的键使用映射。

所以第二件事是摆脱faithfulrepr并与__eq__比较对象：

binder, values = [], []
for key, value in ds.items():
    try:
        index = values.index(value)
    except ValueError:
        values.append(value)
        binder.append([key])
    else:
        binder[index].append(key)
grouped = dict(zip(map(tuple, binder), values))

在字典中查找混合类型值的重复项

Find duplicates for mixed type values in dictionaries

python

hash

dictionary

pickle