Извлечь набор значений листьев, найденных во вложенных диктантах и ​​списках, исключая None - PullRequest
Новая
       47

Извлечь набор значений листьев, найденных во вложенных диктантах и ​​списках, исключая None

2 голосов
/ 21 января 2020

У меня есть вложенная структура, читаемая из YAML, которая состоит из вложенных списков и / или вложенных диктовок или их сочетания на разных уровнях вложенности. Можно предположить, что структура не содержит никаких рекурсивных объектов.

Как извлечь из нее только листовые значения? Кроме того, я не хочу никакого значения None. Значения листьев содержат строки, и это все, что мне нужно. Можно использовать рекурсию, учитывая, что максимальная глубина структуры недостаточно велика, чтобы превышать пределы рекурсии стека. Генератор также мог бы подойти.

Существуют аналогичные вопросы, которые имеют дело со сглаживающими списками или диктовками, но не смесь обоих. В качестве альтернативы, если сгладить диктат, они также возвращают сглаженные ключи, которые мне на самом деле не нужны, и рискуют конфликтами имен.

Я пытался more_itertools.collapse, но его примеры показывают его только работать со вложенными списками, а не со списком слов и списков.

Примеры входных данных 

struct1 = {
    "k0": None,
    "k1": "v1",
    "k2": ["v0", None, "v1"],
    "k3": ["v0", ["v1", "v2", None, ["v3"], ["v4", "v5"], []]],
    "k4": {"k0": None},
    "k5": {"k1": {"k2": {"k3": "v3", "k4": "v6"}, "k4": {}}},
    "k6": [{}, {"k1": "v7"}, {"k2": "v8", "k3": "v9", "k4": {"k5": {"k6": "v10"}, "k7": {}}}],
    "k7": {
        "k0": [],
        "k1": ["v11"],
        "k2": ["v12", "v13"],
        "k3": ["v14", ["v15"]],
        "k4": [["v16"], ["v17"]],
        "k5": ["v18", ["v19", "v20", ["v21", "v22", []]]],
    },
}

struct2 = ["aa", "bb", "cc", ["dd", "ee", ["ff", "gg"], None, []]]

Ожидаемые выходные данные 

struct1_leaves = {f"v{i}" for i in range(23)}
struct2_leaves = {f"{s}{s}" for s in "abcdefg"}

Ответы [ 3 ]

2 голосов
/ 21 января 2020

Другая возможность заключается в использовании генератора с рекурсией: 

struct1 = {'k0': None, 'k1': 'v1', 'k2': ['v0', None, 'v1'], 'k3': ['v0', ['v1', 'v2', None, ['v3'], ['v4', 'v5'], []]], 'k4': {'k0': None}, 'k5': {'k1': {'k2': {'k3': 'v3', 'k4': 'v6'}, 'k4': {}}}, 'k6': [{}, {'k1': 'v7'}, {'k2': 'v8', 'k3': 'v9', 'k4': {'k5': {'k6': 'v10'}, 'k7': {}}}], 'k7': {'k0': [], 'k1': ['v11'], 'k2': ['v12', 'v13'], 'k3': ['v14', ['v15']], 'k4': [['v16'], ['v17']], 'k5': ['v18', ['v19', 'v20', ['v21', 'v22', []]]]}}
def flatten(d):
   for i in getattr(d, 'values', lambda :d)():
      if isinstance(i, str):
         yield i
      elif i is not None:
         yield from flatten(i)

print(set(flatten(struct1)))

Выход: 

{'v10', 'v9', 'v8', 'v7', 'v0', 'v18', 'v16', 'v1', 'v21', 'v11', 'v14', 'v15', 'v12', 'v13', 'v4', 'v2', 'v5', 'v20', 'v6', 'v19', 'v3', 'v22', 'v17'}

struct2 = ["aa", "bb", "cc", ["dd", "ee", ["ff", "gg"], None, []]]
print(set(flatten(struct2)))

Выход: 

{'cc', 'ff', 'dd', 'gg', 'bb', 'ee', 'aa'}
1 голос
/ 21 января 2020

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

from typing import Any, Set


def leaves(struct: Any) -> Set[Any]:
    """Return a set of leaf values found in nested dicts and lists excluding None values."""
    # Ref: https://stackoverflow.com/a/59832594/
    values = set()

    def add_leaves(struct_: Any) -> None:
        if isinstance(struct_, dict):
            for sub_struct in struct_.values():
                add_leaves(sub_struct)
        elif isinstance(struct_, list):
            for sub_struct in struct_:
                add_leaves(sub_struct)
        elif struct_ is not None:
            values.add(struct_)

    add_leaves(struct)
    return values

Кредит: предложение по Переполнение кучи

1 голос
/ 21 января 2020

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

from typing import Any, Set


def leaves(struct: Any) -> Set[Any]:
    """Return a set of leaf values found in nested dicts and lists excluding None values."""
    # Ref: https://stackoverflow.com/a/59832362/
    values = set()
    if isinstance(struct, dict):
        for sub_struct in struct.values():
            values.update(leaves(sub_struct))
    elif isinstance(struct, list):
        for sub_struct in struct:
            values.update(leaves(sub_struct))
    elif struct is not None:
        values.add(struct)
    return values
...