在Python中比较具有嵌套列表的字典列表。

9 浏览
0 Comments

在Python中比较具有嵌套列表的字典列表。

我想得到两个具有以下结构的列表的差异：

first_dict = [{"a": "abcd","b":"defg", "c":["fng","xvg"]}, {"a": "stg","b":"klsm", "c":["xzy"]}]
second_dict = [{"a": "abcd","b":"defg", "c":["fng","xvg"]}]

我尝试将集合冻结如下：

i_set = { frozenset(row.items()) for row in first_dict }
a_set = { frozenset(row.items())  for row in second_dict }
result = [dict(i) for i in i_set - a_set]

预期结果：

v = {"a": "stg","b":"klsm", "c":["xzy"]}

因为"c":[]是一个列表，所以我得到了以下错误：

TypeError: unhashable type: 'list'

我查看了类似的答案这里和这里，但它们对我的问题不起作用。

0

2 答案

0 Comments

比较嵌套列表的字典列表是一个常见的问题，通常会出现性能问题。为了解决这个问题，可以使用frozenset和列表推导式来比较两个字典列表。

在给出的示例中，首先定义了两个字典列表first_dict和second_dict。然后使用列表推导式[i for i in first_dict if i not in second_dict]来比较两个列表中是否存在相同的字典。如果存在不同的字典，则返回第一个不同的字典。

另外，如果希望只返回一个不同的字典，可以将列表推导式修改为[i for i in first_dict if i not in second_dict][0]。

为什么使用frozenset？可能是因为性能方面的原因。使用列表推导式进行比较的时间复杂度是二次的，因为in操作的时间复杂度是O(n)，而在嵌套的循环中执行了n次，所以总的时间复杂度是O(n**2)。而使用frozenset进行集合差运算的时间复杂度是线性的，为O(n)。

所以，使用frozenset可以提高比较字典列表的性能。

感谢原作者提供的解决方法，虽然简单但是性能较好。

0
0 Comments

在Python中，比较嵌套列表的字典列表是一个常见的问题。为了提高效率并避免O(n**2)的算法，我们可以使用set和frozenset进行比较。但是，由于列表是不可哈希的，我们需要将其转换为可哈希的类型，比如tuple。

以下是解决该问题的方法：

方法一：

def convert(dictionary):
    return frozenset((key, tuple(value) if isinstance(value, list) else value) for key, value in dictionary.items())
def convert_back(frozset):
    return dict((key, list(value) if isinstance(value, tuple) else value) for key, value in frozset)
i_set = { convert(row) for row in first_dict }
a_set = { convert(row) for row in second_dict }
result = [convert_back(i) for i in i_set - a_set]

上述代码将字典转换为frozenset，并将列表转换为tuple，然后进行集合的比较。最后，将结果转换回原始的字典格式。

方法二：

class HashableDictionaryWithListValues:
    def __init__(self, dictionary):
        converted = frozenset((key, tuple(value) if isinstance(value, list) else value) for key, value in dictionary.items())
        self._hash = hash(converted)
        self._converted = converted
        self.dictionary = dictionary
    def __hash__(self):
        return self._hash
    def __eq__(self, other):
        return self._converted == other._converted
i_set = { HashableDictionaryWithListValues(row) for row in first_dict }
a_set = { HashableDictionaryWithListValues(row) for row in second_dict }
result = [i.dictionary for i in i_set - a_set]

上述代码定义了一个自定义的可哈希字典类，将字典转换为frozenset，并使用自定义类进行集合的比较。最终，返回原始的字典格式。

方法三：

def difference(first, second):
    for item in first:
        if item not in second:
            yield item
result = list(difference(first_dict, second_dict))

上述代码是一种O(n**2)的方法，直接对两个字典列表进行遍历比较，返回差异的部分。

以上是比较嵌套列表的字典列表的几种解决方法。无论是使用set和frozenset转换，还是使用自定义的可哈希类，或者直接进行遍历比较，都可以得到预期的结果。根据具体的需求和数据规模，选择最适合的方法来解决问题。

0