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

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

5 голосов
/ 01 октября 2010

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

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

17 голосов
/ 01 октября 2010

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

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

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

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

6 голосов
/ 01 октября 2010

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.

6 голосов
/ 01 октября 2010

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

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