如何在python中使独特的嵌套字典列表

Question

我有以下嵌套字典列表:

[{'permission': 'full',
  'permission_type': 'allow',
  'trustee': {'id': 'SID:S-1-5-32-545',
              'name': 'Users',
              'type': 'group'}},
 {'permission': 'full',
  'permission_type': 'allow',
  'trustee': {'id': 'SID:S-1-5-32-545',
              'name': 'Users',
              'type': 'group'}},
 {'permission': 'full',
  'permission_type': 'allow',
  'trustee': {'id': 'SID:S-1-5-32-544',
              'name': 'Administrators',
              'type': 'group'}}]

我想让它独一无二,并尝试了不同的建议但没有成功.有人可以帮助它在python 2.6中独一无二吗？上面的数据中没有关键/唯一字段.我希望得到以下结果(列表中的一个成员作为完整副本被删除):

[{'permission': 'full',
  'permission_type': 'allow',
  'trustee': {'id': 'SID:S-1-5-32-545',
              'name': 'Users',
              'type': 'group'}},
 {'permission': 'full',
  'permission_type': 'allow',
  'trustee': {'id': 'SID:S-1-5-32-544',
              'name': 'Administrators',
              'type': 'group'}}]

Answer 1

你需要跟踪你是否已经看过字典.不幸的是,字典不可删除,并且不跟踪顺序,因此您需要将字典转换为可清除的字典.一个frozenset()键值对(作为元组)会做,但是你需要递归地展平:

def set_from_dict(d):
    return frozenset(
        (k, set_from_dict(v) if isinstance(v, dict) else v)
        for k, v in d.iteritems())

这些frozenset()对象表示足以跟踪唯一项的字典值:

seen = set()
result = []
for d in inputlist:
    representation = set_from_dict(d)
    if representation in seen:
        continue
    result.append(d)
    seen.add(representation)

这将保留输入列表的原始顺序,减去重复项.如果您使用的是Python 2.7及更高版本,OrderedDict那么这里会有所帮助,但您使用的是Python 2.6,因此我们需要稍微详细一点.

上述方法花费O(N)时间,每个输入字典一步,因为针对集合的测试仅花费O(1)恒定时间.

演示:

>>> inputlist = [{'permission': 'full',
...   'permission_type': 'allow',
...   'trustee': {'id': 'SID:S-1-5-32-545',
...               'name': 'Users',
...               'type': 'group'}},
...  {'permission': 'full',
...   'permission_type': 'allow',
...   'trustee': {'id': 'SID:S-1-5-32-545',
...               'name': 'Users',
...               'type': 'group'}},
...  {'permission': 'full',
...   'permission_type': 'allow',
...   'trustee': {'id': 'SID:S-1-5-32-544',
...               'name': 'Administrators',
...               'type': 'group'}}]
>>> def set_from_dict(d):
...     return frozenset(
...         (k, set_from_dict(v) if isinstance(v, dict) else v)
...         for k, v in d.iteritems())
... 
>>> seen = set()
>>> result = []
>>> for d in inputlist:
...     representation = set_from_dict(d)
...     if representation in seen:
...         continue
...     result.append(d)
...     seen.add(representation)
... 
>>> from pprint import pprint
>>> pprint(result)
[{'permission': 'full',
  'permission_type': 'allow',
  'trustee': {'id': 'SID:S-1-5-32-545', 'name': 'Users', 'type': 'group'}},
 {'permission': 'full',
  'permission_type': 'allow',
  'trustee': {'id': 'SID:S-1-5-32-544',
              'name': 'Administrators',
              'type': 'group'}}]