Свести словарь словарей (2 уровня глубиной) списков в Python

Я пытаюсь обернуть мой мозг вокруг этого, но он недостаточно гибок.

В моем скрипте 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]

Я мог бы, вероятно, настроить map-Reduce, чтобы перебирать элементы внешнего словаря для создания подсписка из каждого поддиректория, а затем объединять все подсписки вместе.

Но это кажется неэффективным для больших наборов данных из-за промежуточных структур данных (подсписков), которые будут выброшены. Есть ли способ сделать это за один проход?

За исключением этого, я был бы рад принять двухуровневую реализацию, которая работает... моя карта-уменьшение ржавая!

Обновление: для тех, кто заинтересован, ниже приведен код, который я в итоге использовал.

Обратите внимание, что, хотя я попросил список для вывода, мне действительно нужен был отсортированный список; т. е. результат выравнивания может быть любым итеративным, который можно отсортировать.

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.]

Источник

3 ответа

Решение

edit: перечитайте оригинальный вопрос и переработанный ответ, чтобы предположить, что все словари не являются списками, которые должны быть сведены.

В тех случаях, когда вы не уверены, насколько далеко зашли словари, вам следует использовать рекурсивную функцию. @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

Doctest передает полученный итератор set функция. Скорее всего, это то, что вам нужно, поскольку, как указывает г-н Мартелли, нет никакого внутреннего порядка значений словаря, и, следовательно, нет причин отслеживать порядок, в котором они были найдены.

Вы можете отслеживать количество вхождений каждого значения; эта информация будет потеряна, если вы передадите итератор set, Если вы хотите отследить это, просто передайте результат flatten(hat) к какой-то другой функции вместо set, В Python 2.7 эта другая функция может быть collections.Counter, Для совместимости с менее развитыми питонами вы можете написать свою собственную функцию или (с некоторой потерей эффективности) объединить sorted с itertools.groupby,

Источник

Я надеюсь, вы понимаете, что любой заказ, который вы видите в диктовке, является случайным - он существует только потому, что при отображении на экране нужно выбирать какой-то заказ, но нет абсолютно никакой гарантии.

Сетка проблем с упорядочением среди различных списков подписчиков,

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

делает то, что вы хотите, без какой-либо неэффективности или промежуточных списков.

Источник

Рекурсивная функция может работать:

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)
Источник
Другие вопросы по тегам