Python 3.x：如何比较两个包含字典的列表，其中顺序不重要？

Question

我有一些嵌套的字典，可能包含其他字典或列表。我需要能够比较这些字典的列表（或集合），以展示它们是否相等。

列表的顺序不一定是固定的。通常情况下，我会将列表转换为一个集合，但由于其中也包含字典值，所以这样做是不可行的。

a = {'color': 'red'}
b = {'shape': 'triangle'}
c = {'children': [{'color': 'red'}, {'age': 8},]}

test_a = [a, b, c] 
test_b = [b, c, a]

print(test_a == test_b)  # False
print(set(test_a) == set(test_b))  # TypeError: unhashable type: 'dict'

有没有好的方法来展示test_a和test_b的内容相同？

- Abe Clark

---

内部列表是否统一？或者它们的元素也可以是任意顺序吗？它们是否嵌套超过两个级别（即，包含的元素和列表本身可以包含其他列表和字典）- 或者您正在比较的所有列表元素都是浅层的？ - jsbueno

@uoɥʇʎPʎzɐɹC：比你想象的要复杂，如果你想让它高效而不脆弱。 - user2357112

你是怎么得到这么不同的格式的？ - Padraic Cunningham

@jsbueno 是的，元素可以是任意顺序，它们也可以包含其他列表或字典。 - Abe Clark

@PadraicCunningham 在测试套件中比较两个无序的 XML 文档。 - Abe Clark

Answer 1

你可以使用简单的循环来检查一个列表中的每个元素是否在另一个列表中：

def areEqual(a, b):
    if len(a) != len(b):
        return False

    for d in a:
        if d not in b:
            return False
    return True

- m_callens

---

你也应该检查另一个方向。 - Ohad Eytan

考虑 a=[1] 和 b=[1,2]，你的函数返回 True。 - Ohad Eytan

用 [a, b, c] 和 [a, b, c, d] 进行测试，你就会看到 :) - Cabu

谢谢，这对我提供的示例确实有意义。在我的实际场景中，可能会有更深层次的嵌套数组，这会使得这种方法无法工作（因为顺序很重要）。 - Abe Clark

无论如何，我正在考虑使用“sorted”提出的解决方案 - 但是这些不起作用，因为（1）列表具有异构元素，而且（2）人们不能轻松地对“dicts”本身进行排序。所以，是的，这是一个好答案，可以解决问题！ - jsbueno

Answer 2

我建议编写一个函数，将任何Python对象转换为可排序的内容，并按照顺序排列其内容（如果有的话）。如果我们称之为canonicalize，我们可以使用它来比较嵌套对象。

canonicalize(test_a) == canonicalize(test_b)

这是我编写的一个“规范化”函数的尝试：

canonicalize

def canonicalize(x):
    if isinstance(x, dict):
        x = sorted((canonicalize(k), canonicalize(v)) for k, v in x.items())
    elif isinstance(x, collections.abc.Iterable) and not isinstance(x, str):
        x = sorted(map(canonicalize, x))
    else:
        try:
            bool(x < x) # test for unorderable types like complex
        except TypeError:
            x = repr(x) # replace with something orderable
    return x

这将适用于大多数Python对象。它不适用于异构项列表，包含自身的容器（这将导致函数达到递归限制），也不适用于float('nan')（其比较行为奇怪，因此可能会破坏任何包含它的容器的排序）。

这段代码可能对于非可迭代、无序对象做出错误操作，如果它们没有一个描述其值的所有数据（例如由==测试的内容）的repr函数。我选择了repr，因为它适用于任何类型的对象，并且可能是正确的（例如，它适用于complex）。对于具有类似构造函数调用的repr的类，它应该也能正常工作。对于继承了object.__repr__并输出类似于<Foo object at 0xXXXXXXXX>的repr的类，它至少不会崩溃，尽管对象将按标识比较而不是值。我认为没有真正通用的解决方案，如果你期望在数据中找到某些类无法使用repr，可以添加一些特殊情况。

- Blckknght

Answer 3

在这种情况下，它们是相同的字典，因此您可以比较 ID（docs）。请注意，如果您引入了一个新的值相同的dict，它仍将被视为不同。即d = {'color': 'red'}将被视为与a不相等。

sorted(map(id, test_a)) == sorted(map(id, test_b))

正如@jsbueno所指出的那样，您可以使用kwarg key来完成这个操作。

sorted(test_a, key=id) == sorted(test_b, key=id)

- Alex

---

抱歉，实际情况下我比较的不是相同的字典，而是两个具有相同内容的字典。谢谢。 - Abe Clark

除了不能解决问题外，这种使用“sorted”的方式是不正确的，除非你真的想要ID - 你应该使用key参数来排序，而不是在源列表上使用map。 - jsbueno

Answer 4

如果两个列表中的元素都是浅层的，那么对它们进行排序，然后比较它们是否相等的想法是可行的。@Alex 的解决方案的问题在于他只使用了“id” - 但如果使用一个能够正确排序字典的函数，事情应该就可以顺利进行：

def sortkey(element):
   if isinstance(element, dict):
         element = sorted(element.items())
   return repr(element)

sorted(test_a, key=sortkey) == sorted(test_b, key=sotrkey) 

我使用repr来包装键，因为它会在比较之前将所有元素转换为字符串，这将避免类型错误，如果不同的元素是无序类型，则几乎肯定会发生 - 如果您正在使用Python 3.x，则几乎肯定会发生。

只是为了明确，如果您的字典和列表本身具有嵌套字典，则应使用@m_callens的答案。如果您的内部列表也是无序的，则可以在键函数中对其进行排序以使其正常工作。

- jsbueno

Answer 5

一个优雅且相对快速的解决方案：

class QuasiUnorderedList(list):
    def __eq__(self, other):
        """This method isn't as ineffiecient as you think! It runs in O(1 + 2 + 3 + ... + n) time, 
        possibly better than recursively freezing/checking all the elements."""
        for item in self:
            for otheritem in other:
                if otheritem == item:
                    break
            else:
                # no break was reached, item not found.
                return False
        return True

这个程序的时间复杂度为 O(1 + 2 + 3 + ... + n)。虽然对于深度较低的字典来说速度较慢，但对于深度较高的字典来说速度更快。

下面是一个更长的代码片段，适用于深度较浅、长度较高的字典。

class FrozenDict(collections.Mapping, collections.Hashable):  # collections.Hashable = portability
    """Adapated from https://dev59.com/wHE85IYBdhLWcg3wl0nF#2704866"""

    def __init__(self, *args, **kwargs):
        self._d = dict(*args, **kwargs)
        self._hash = None

    def __iter__(self):
        return iter(self._d)

    def __len__(self):
        return len(self._d)

    def __getitem__(self, key):
        return self._d[key]

    def __hash__(self):
        # It would have been simpler and maybe more obvious to
        # use hash(tuple(sorted(self._d.iteritems()))) from this discussion
        # so far, but this solution is O(n). I don't know what kind of
        # n we are going to run into, but sometimes it's hard to resist the
        # urge to optimize when it will gain improved algorithmic performance.
        # Now thread safe by CrazyPython
        if self._hash is None:
            _hash = 0
            for pair in self.iteritems():
                _hash ^= hash(pair)
        self._hash = _hash
        return _hash


def freeze(obj):
    if type(obj) in (str, int, ...):  # other immutable atoms you store in your data structure
        return obj
    elif issubclass(type(obj), list):  # ugly but needed
        return set(freeze(item) for item in obj)
    elif issubclass(type(obj), dict):  # for defaultdict, etc.
        return FrozenDict({key: freeze(value) for key, value in obj.items()})
    else:
        raise NotImplementedError("freeze() doesn't know how to freeze " + type(obj).__name__ + " objects!")


class FreezableList(list, collections.Hashable):
    _stored_freeze = None
    _hashed_self = None

    def __eq__(self, other):
        if self._stored_freeze and (self._hashed_self == self):
            frozen = self._stored_freeze
        else:
            frozen = freeze(self)
        if frozen is not self._stored_freeze:
            self._stored_hash = frozen
        return frozen == freeze(other)

    def __hash__(self):
        if self._stored_freeze and (self._hashed_self == self):
            frozen = self._stored_freeze
        else:
            frozen = freeze(self)
        if frozen is not self._stored_freeze:
            self._stored_hash = frozen
        return hash(frozen)


class UncachedFreezableList(list, collections.Hashable):
    def __eq__(self, other):
        """No caching version of __eq__. May be faster.
        Don't forget to get rid of the declarations at the top of the class!
        Considerably more elegant."""
        return freeze(self) == freeze(other)

    def __hash__(self):
        """No caching version of __hash__. See the notes in the docstring of __eq__2"""
        return hash(freeze(self))

测试所有三个（QuasiUnorderedList、FreezableList 和 UncachedFreezableList），看看在你的情况下哪一个更快。我敢打赌它比其他解决方案更快。

- noɥʇʎԀʎzɐɹƆ

---

O(1+2+3+...+n) 时间复杂度为 O(n**2)。同时，QuasiUnorderedList([1, 2]) == [1, 2, 3]，但是你的实现通常比 m_callens 先前发布的实现要慢。 - user2357112

@user2357112 是的，在最坏情况下时间复杂度为 O(n**2)。但是在实践中，1+2+3 是否等于 3**2？ - noɥʇʎԀʎzɐɹƆ

1+2+3>(3**2)/2，通常情况下，1+2+3+...+n==(n**2+n)/2。如果你想争论常数因子，那么你仍然比m_callens发布的更差。 - user2357112