Nano Hash - криптовалюты, майнинг, программирование

Как создать дерево из списка поддеревьев?

Представьте, что у нас есть куча подтекстов, которые выглядят так:

subtree1 = {
    "id": "root",
    "children": [
        {
            "id": "file",
            "caption": "File",
            "children": []
        },
        {
            "id": "edit",
            "caption": "Edit",
            "children": []
        },
        {
            "id": "tools",
            "caption": "Tools",
            "children": [
                {
                    "id": "packages",
                    "caption": "Packages",
                    "children": []
                }
            ]
        },
        {
            "id": "help",
            "caption": "Help",
            "children": []
        },
    ]
}

subtree2 = {
    "id": "root",
    "children": [
        {
            "id": "file",
            "caption": "File",
            "children": [
                {"caption": "New"},
                {"caption": "Exit"},
            ]        
        }
    ]
}

subtree3 = {
    "id": "root",
    "children": [
        {
            "id": "edit",
            "children": [
                {"caption": "Copy"},
                {"caption": "Cut"},
                {"caption": "Paste"},
            ]
        },
        {
            "id": "help",
            "children": [
                {"caption": "About"},
            ]
        }
    ]
}

subtree4 = {
    "id": "root",
    "children": [
        {
            "id": "edit",
            "children": [
                {
                    "id": "text",
                    "caption": "Text",
                    "children": [
                        { "caption": "Insert line before" },
                        { "caption": "Insert line after" }
                    ]
                }
            ]
        }
    ]
}

Я пытаюсь понять, как закодировать функцию merge, например, сделать что-то вроде этого:

tree0 = merge(subtree1, subtree2)
tree0 = merge(tree0, subtree3)
tree0 = merge(tree0, subtree4)

будет производить:

tree0 = {
    "id": "root",
    "children": [
        {
            "id": "file",
            "caption": "File",
            "children": [
                {"caption": "New"},
                {"caption": "Exit"},
            ]   
        },
        {
            "id": "edit",
            "caption": "Edit",
            "children": [
                {"caption": "Copy"},
                {"caption": "Cut"},
                {"caption": "Paste"},
                {
                    "id": "text",
                    "caption": "Text",
                    "children": [
                        { "caption": "Insert line before" },
                        { "caption": "Insert line after" }
                    ]
                }
            ]
        },
        {
            "id": "tools",
            "caption": "Tools",
            "children": [
                {
                    "id": "packages",
                    "caption": "Packages",
                    "children": []
                }
            ]
        },
        {
            "id": "help",
            "caption": "Help",
            "children": [
                {"caption": "About"},
            ]
        },
    ]
}

но делать что-то вроде этого:

tree1 = merge(subtree1, subtree2)
tree1 = merge(tree1, subtree4)
tree1 = merge(tree1, subtree3)

будет производить:

tree1 = {
    "id": "root",
    "children": [
        {
            "id": "file",
            "caption": "File",
            "children": [
                {"caption": "New"},
                {"caption": "Exit"},
            ]   
        },
        {
            "id": "edit",
            "caption": "Edit",
            "children": [
                {
                    "id": "text",
                    "caption": "Text",
                    "children": [
                        { "caption": "Insert line before" },
                        { "caption": "Insert line after" }
                    ]
                },
                {"caption": "Copy"},
                {"caption": "Cut"},
                {"caption": "Paste"},
            ]
        },
        {
            "id": "tools",
            "caption": "Tools",
            "children": [
                {
                    "id": "packages",
                    "caption": "Packages",
                    "children": []
                }
            ]
        },
        {
            "id": "help",
            "caption": "Help",
            "children": [
                {"caption": "About"},
            ]
        },
    ]
}

Другими словами, загрузка поддеревьев в одном и том же порядке всегда будет создавать одно и то же дерево, но если вы используете один и тот же список поддеревьев в другом порядке, вы не гарантируете создание одного и того же дерева (поскольку дочерние списки могут быть расширены в другом порядке).

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

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

if __name__ == '__main__':
    from collections import defaultdict

    subtree1 = {
        "id": "root",
        "children": [
            {
                "id": "file",
                "caption": "File",
                "children": []
            },
            {
                "id": "edit",
                "caption": "Edit",
                "children": []
            },
            {
                "id": "tools",
                "caption": "Tools",
                "children": [
                    {
                        "id": "packages",
                        "caption": "Packages",
                        "children": []
                    }
                ]
            },
            {
                "id": "help",
                "caption": "Help",
                "children": []
            },
        ]
    }

    subtree2 = {
        "id": "root",
        "children": [
            {
                "id": "file",
                "caption": "File",
                "children": [
                    {"caption": "New"},
                    {"caption": "Exit"},
                ]
            }
        ]
    }

    subtree3 = {
        "id": "root",
        "children": [
            {
                "id": "edit",
                "children": [
                    {"caption": "Copy"},
                    {"caption": "Cut"},
                    {"caption": "Paste"},
                ]
            },
            {
                "id": "help",
                "children": [
                    {"caption": "About"},
                ]
            }
        ]
    }

    subtree4 = {
        "id": "root",
        "children": [
            {
                "id": "edit",
                "children": [
                    {
                        "id": "text",
                        "caption": "Text",
                        "children": [
                            {"caption": "Insert line before"},
                            {"caption": "Insert line after"}
                        ]
                    }
                ]
            }
        ]
    }

    lst = [
        subtree1,
        subtree2,
        subtree3,
        subtree4
    ]

    def traverse(node, path=[]):
        yield node, tuple(path)

        for c in node.get("children", []):
            path.append(c.get("id", None))
            yield from traverse(c)
            path.pop()

    # Levels & Hooks
    dct_levels = defaultdict(list)
    dct_hooks = defaultdict(list)
    for subtree in lst:
        for n, p in traverse(subtree):
            if p not in dct_levels[len(p)]:
                dct_levels[len(p)].append(p)
            dct_hooks[p].append(n)

    print(dct_levels)
    print(dct_hooks[("file",)])

    # Merge should happen here
    tree = {
        "id": "root",
        "children": []
    }

    for level in range(1, max(dct_levels.keys()) + 1):
        print("populating level", level, dct_levels[level])

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

python tree
05.05.2019

Ответы:


1

Протестировано с вашими примерами на Python 3.5.

from copy import deepcopy


def merge(x: dict, y: dict) -> dict:
    'Merge subtrees x y, and return the results as a new tree.'
    return merge_inplace(deepcopy(x), y)


def merge_inplace(dest: dict, src: dict) -> dict:
    'Merge subtree src into dest, and return dest.'

    # perform sanity checks to make the code more rock solid
    # feel free to remove those lines if you don't need
    assert dest.get('id'), 'Cannot merge anonymous subtrees!'
    assert dest.get('id') == src.get('id'), 'Identity mismatch!'

    # merge attributes
    dest.update((k, v) for k, v in src.items() if k != 'children')

    # merge children
    if not src.get('children'):  # nothing to do, so just exit
        return dest
    elif not dest.get('children'):  # if the children list didn't exist
        dest['children'] = []  # then create an empty list for it

    named_dest_children = {
        child['id']: child
        for child in dest['children']
        if 'id' in child
    }
    for child in src['children']:
        if 'id' not in child:  # anonymous child, just append it
            dest['children'].append(child)
        elif child['id'] in named_dest_children:  # override a named subtree
            merge_inplace(named_dest_children[child['id']], child)
        else:  # create a new subtree
            dest['children'].append(child)
            named_dest_children[child['id']] = child
    return dest
11.05.2019
  • Этот ответ действительно хорош, и я думаю, что его уже можно использовать в реальных сценариях... Есть небольшой случай, когда я не уверен, каким должен быть вывод, проверьте test2 в этом код... Если я не ошибаюсь, в Sublime, когда элемент тот же идентификатор переопределит новые атрибуты, в этом коде элемент root/preferences в конечном итоге будет иметь "caption": "NewPreferences" и "commnad": "do_something". Я еще раз проверю Sublime, чтобы быть уверенным, но я думаю, что это то, что произойдет. Тем не менее, действительно хороший ответ, +1 11.05.2019
  • @BPL Я отредактировал ответ, чтобы переопределить атрибуты - их можно было скопировать в однострочнике, просто если в них не разрешены поддеревья. 12.05.2019

    • 2

    Вы можете использовать itertools.groupby с рекурсией:

    from itertools import groupby
def merge(*args):
   if len(args) < 2 or any('id' not in i for i in args):
      return list(args)
   _d = [(a, list(b)) for a, b in groupby(sorted(args, key=lambda x:x['id']), key=lambda x:x['id'])]
   return [{**{j:k for h in b for j, k in h.items()}, 'id':a, 'children':merge(*[i for c in b for i in c['children']])} for a, b in _d]

    Через args это решение рассматривает каждый переданный словарь как член списка children. Это сделано для того, чтобы учесть возможность того, что в merge могут быть переданы два или более словарей, которые имеют разные id, то есть {'id':'root', 'children':[...]} и {'id':'root2', 'children':[...]}. Таким образом, это решение вернет список [{'id':'root', 'children':[...]}, {'id':'root2', 'children':[...]}], поскольку отдельные id не обеспечивают возможности для сопоставления. Таким образом, в контексте вашей текущей проблемы вам необходимо использовать индексирование для доступа к единственному возвращаемому элементу результирующего списка: объединенному dict с id 'root':

    import json
tree0 = merge(subtree1, subtree2)[0]
tree0 = merge(tree0, subtree3)[0]
tree0 = merge(tree0, subtree4)[0]
print(json.dumps(tree0, indent=4))

    Выход:

    {
  "id": "root",
  "children": [
    {
        "id": "edit",
        "caption": "Edit",
        "children": [
            {
                "caption": "Copy"
            },
            {
                "caption": "Cut"
            },
            {
                "caption": "Paste"
            },
            {
                "id": "text",
                "caption": "Text",
                "children": [
                    {
                        "caption": "Insert line before"
                    },
                    {
                        "caption": "Insert line after"
                    }
                ]
            }
        ]
    },
    {
        "id": "file",
        "caption": "File",
        "children": [
            {
                "caption": "New"
            },
            {
                "caption": "Exit"
            }
        ]
    },
    {
        "id": "help",
        "caption": "Help",
        "children": [
            {
                "caption": "About"
            }
        ]
    },
    {
        "id": "tools",
        "caption": "Tools",
        "children": [
            {
                "id": "packages",
                "caption": "Packages",
                "children": []
            }
        ]
      }
   ]
}
    11.05.2019
  • Не все должно быть в гольф. Строка из 132 символов (без учета отступа) с пониманием списка из 5 циклов for, в котором есть рекурсия и только односимвольные имена переменных. Это просто ужасная практика, которая приводит к неподдерживаемому коду. 14.05.2019
  • Спасибо за ответ, причина, по которой я не подтвердил / не наградил этот ответ, заключалась в том, что Arnie97 сначала предоставил хорошее решение, и сообщество решило, что это лучший ответ ... У ruohola есть точка зрения, хотя я люблю компактный умный код, и это определенно так. .. так вот, +1 ;) 15.05.2019

    • 3

    Ручное кодирование для слияния документов/объектов JSON может быть не оптимальным решением. СУХОЙ!
    Я использовал genson, jsonschema и jsonmerge здесь пакеты для слияния.

    genson создает схему JSON из документов экземпляра JSON.
    jsonschema проверяет документы экземпляра JSON с помощью схемы JSON.
    jsonmerge объединяет объекты/документы JSON, расширяя схему JSON.

    Давайте сначала создадим схему JSON из экземпляров JSON.

    trees = (subtree1, subtree2, subtree3, subtree4)
schema_builder = genson.SchemaBuilder()
for tree in trees:
    schema_builder.add_object(tree)

schema = schema_builder.to_schema()

    Теперь укажите стратегию слияния.

    schema['properties']['children']['mergeStrategy'] = 'arrayMergeById'
schema['properties']['children']['items']['properties']['children']['mergeStrategy'] = 'append'

    Стратегия arrayMergeById объединяет объекты по свойству id объекта. append стратегия собирает объекты в массив.
    Вот полный код;

    import genson
import jsonmerge
import jsonschema

subtree1 = {
    "id":
    "root",
    "children": [
        {
            "id": "file",
            "caption": "File",
            "children": []
        },
        {
            "id": "edit",
            "caption": "Edit",
            "children": []
        },
        {
            "id": "tools",
            "caption": "Tools",
            "children": [{
                "id": "packages",
                "caption": "Packages",
                "children": []
            }]
        },
        {
            "id": "help",
            "caption": "Help",
            "children": []
        },
    ]
}

subtree2 = {
    "id":
    "root",
    "children": [{
        "id": "file",
        "caption": "File",
        "children": [
            {
                "caption": "New"
            },
            {
                "caption": "Exit"
            },
        ]
    }]
}

subtree3 = {
    "id":
    "root",
    "children": [{
        "id":
        "edit",
        "children": [
            {
                "caption": "Copy"
            },
            {
                "caption": "Cut"
            },
            {
                "caption": "Paste"
            },
        ]
    }, {
        "id": "help",
        "children": [
            {
                "caption": "About"
            },
        ]
    }]
}

subtree4 = {
    "id":
    "root",
    "children": [{
        "id":
        "edit",
        "children": [{
            "id":
            "text",
            "caption":
            "Text",
            "children": [{
                "caption": "Insert line before"
            }, {
                "caption": "Insert line after"
            }]
        }]
    }]
}

trees = (subtree1, subtree2, subtree3, subtree4)
schema_builder = genson.SchemaBuilder()
for tree in trees:
    schema_builder.add_object(tree)

schema = schema_builder.to_schema()
print("Validating schema...", end='')
for tree in trees:
    jsonschema.validate(tree, schema)
print(' done')
schema['properties']['children']['mergeStrategy'] = 'arrayMergeById'
schema['properties']['children']['items']['properties']['children']['mergeStrategy'] = 'append'

merger = jsonmerge.Merger(schema=schema)
tree = merger.merge(subtree1, subtree2)
tree = merger.merge(tree, subtree3)
tree = merger.merge(tree, subtree4)
print(tree)
    16.05.2019
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..