扁平化包含列表的字典中的字典（深度2）

Question

我在努力理解这个问题，但感觉有点复杂。

在我的Python脚本中，我有一个字典，里面又包含了字典和列表。（其实结构更复杂，但这一层不在这个问题讨论范围内。）我想把这些内容压缩成一个长长的列表，同时把所有的字典键都扔掉。

也就是说，我想把

{1: {'a': [1, 2, 3], 'b': [0]},
 2: {'c': [4, 5, 1], 'd': [3, 8]}}

转换成

[1, 2, 3, 0, 4, 5, 1, 3, 8]

我可能可以设置一个映射-归约的方式，遍历外层字典的每个项目，从每个子字典中构建一个子列表，然后把所有子列表连接在一起。

但这样对于大数据集来说似乎效率不高，因为中间会产生一些临时的数据结构（子列表），最后又要丢掉。有没有办法一次性完成这个操作呢？

如果没有，我也乐意接受一个两层的实现方式……我的映射-归约技术有点生疏了！

更新：对于那些感兴趣的人，下面是我最终使用的代码。

请注意，虽然我在上面要求输出一个列表，但我真正需要的是一个排序后的列表；也就是说，压缩后的输出可以是任何可以排序的可迭代对象。

def genSessions(d):
    """Given the ipDict, return an iterator that provides all the sessions,
    one by one, converted to tuples."""
    for uaDict in d.itervalues():
        for sessions in uaDict.itervalues():
            for session in sessions:
                yield tuple(session)

...

# Flatten dict of dicts of lists of sessions into a list of sessions.
# Sort that list by start time
sessionsByStartTime = sorted(genSessions(ipDict), key=operator.itemgetter(0))
# Then make another copy sorted by end time.
sessionsByEndTime = sorted(sessionsByStartTime, key=operator.itemgetter(1))

再次感谢所有帮助过我的人。

[更新：将 nthGetter() 替换为 operator.itemgetter()，感谢 @intuited.]

Answer 1

一个递归函数可能会有效：

def flat(d, out=[]):
 for val in d.values():
  if isinstance(val, dict):
    flat(d, out)
  else:
    out+= val

如果你用以下内容尝试：

>>> d = {1: {'a': [1, 2, 3], 'b': [0]}, 2: {'c': [4, 5, 6], 'd': [3, 8]}}
>>> out = []
>>> flat(d, out)
>>> print out
[1, 2, 3, 0, 4, 5, 6, 3, 8]

请注意，字典是没有顺序的，所以列表的顺序是随机的。

你也可以在循环结束时 return out，而不需要用列表作为参数来调用这个函数。

def flat(d, out=[]):
 for val in d.values():
  if isinstance(val, dict):
    flat(d, out)
  else:
    out+= val
 return out

调用方式为：

my_list = flat(d)

Answer 2

我希望你明白，在字典中看到的任何顺序都是偶然的——这个顺序只是因为在屏幕上显示时，必须选择某种顺序，但根本没有任何保证。

关于不同子列表合并时的顺序问题，

[x for d in thedict.itervalues()
   for alist in d.itervalues()
   for x in alist]

这个方法可以做到你想要的效果，而且没有任何效率上的浪费，也不需要中间的列表。

Answer 3

编辑: 重新阅读了原问题，并调整了答案，假设所有非字典的内容都是需要展开的列表。

如果你不确定字典的层级有多深，建议使用递归函数。@Arrieta 已经在这里 发布 了一个递归函数，可以生成一个包含非字典值的列表。

这个函数是一个生成器，它会逐个返回字典树中的非字典值：

def flatten(d):
    """Recursively flatten dictionary values in `d`.

    >>> hat = {'cat': ['images/cat-in-the-hat.png'],
    ...        'fish': {'colours': {'red': [0xFF0000], 'blue': [0x0000FF]},
    ...                 'numbers': {'one': [1], 'two': [2]}},
    ...        'food': {'eggs': {'green': [0x00FF00]},
    ...                 'ham': ['lean', 'medium', 'fat']}}
    >>> set_of_values = set(flatten(hat))
    >>> sorted(set_of_values)
    [1, 2, 255, 65280, 16711680, 'fat', 'images/cat-in-the-hat.png', 'lean', 'medium']
    """
    try:
        for v in d.itervalues():
            for nested_v in flatten(v):
                yield nested_v
    except AttributeError:
        for list_v in d:
            yield list_v

这个文档测试会把生成的迭代器传给 set 函数。这样做可能是你想要的，因为正如马特利先生所指出的，字典中的值没有固定的顺序，所以没有必要记录它们被找到的顺序。

如果你想记录每个值出现的次数，使用 set 会丢失这些信息。如果你想跟踪这些信息，可以把 flatten(hat) 的结果传给其他函数，而不是 set。在 Python 2.7 中，那个其他函数可以是 collections.Counter。为了兼容一些较旧的 Python 版本，你可以自己写一个函数，或者（虽然效率会稍低）把 sorted 和 itertools.groupby 结合起来使用。