Создание алгоритма рекурсивного слияния объектов в JavaScript с циклическими зависимостями

Введение

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

Цель данной научной статьи заключается в представлении алгоритма и методики слияния объектов с различными видами зависимостей. Объекты с циклическими зависимостями, могут стать источником бесконечной рекурсии при использовании классических методов слияния. В статье представлен эффективный способ обработки таких зависимостей, который лишён проблем бесконечной рекурсии и генерирующий результат слияния без внешних ссылок на другие объекты.

Метод, описанный в данной статье, использует кэширование и словарь для слияния объектов и обеспечения корректной обработки циклических ссылок. Он предоставляет практическое решение для объединения сложных структур данных с учетом их внутренних зависимостей. Предложенный алгоритм позволяет эффективно решать задачи объединения данных в современных информационных системах, где важно обеспечить целостность и корректность обработки зависимостей между объектами.

Основная часть

Определение

Будем называть объектом с циклическими зависимостями такой объект, который имеет в своём составе на любом уровне ссылку на объект, который принадлежит структуре исходного объекта (см. рис. 1) [1].

Рис. 1. Объект с циклическими зависимостями

Два объекта будем называть объектами с перекрёстными зависимостями, если хотя бы один из них имеет в своём составе на любом уровне ссылку на объект, который принадлежит структуре второго объекта (см. рис. 2).

Рис. 2. Объекты с перекрёстными зависимостями

Два объекта будем называть объектами с циклическими перекрёстными зависимостями, если они являются объектами с перекрёстными зависимостями и оба являются объектами с циклическими зависимостями (см. рис. 3).

Рис. 3. Объекты с циклическими перекрёстными зависимостями

Задача слияния двух или нескольких объектов без циклических зависимостей не является сложной. Для решения такого класса задач достаточно создать рекурсивную функцию слияния [2].

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

При наличии в объектах перекрёстных зависимостей возникает вторая сложность: никакие ссылки в результирующем объекте слияния не должны указывать исходные объекты. Мы должны создавать копии таких объектов, чтобы избежать мутации аргументов функции слияния. Такие ссылки должны указывать на дочерние объекты результирующего объекта слияния. Именно поэтому на рисунках 4, 5 и 6 в составе результата содержатся копии исходных объектов [3].

Рис. 4. Слияние с объектом с циклическими зависимостями

Рис. 5. Слияние объектов с перекрёстными зависимостями

Рис. 6. Слияние объектов с циклическими перекрёстными зависимостями

Стоит отдельно отметить, что задача слияния n различных объектов вне зависимости от наличия или отсутствия в них циклических ссылок легко разбивается на n-1 задачу последовательного слияния объектов между собой с результатом предыдущего слияния (см. рис. 7). Таким образом для решения исходной задачи достаточно решить задачу слияния двух объектов с циклическими зависимостями.

Рис. 7. Задача слияния n объектов

Постановка задачи

Таким образом перед нами стоит следующая задача: из нескольких входных объектов получить один результирующий объект слияния, состоящий из полей входных объектов. Входные объекты могут иметь любую структуру, в том числе циклические и перекрёстные зависимости.

Реализуем JavaScript функцию слияния со следующей сигнатурой:

function merge(result, args, cache, objects)

Таблица

Описание аргументов функции слияния merge

Функция merge ничего не возвращает, а результат слияния объектов сохраняется в переменной result.

Описание алгоритма

1. Обработка особых случаев: входной массив пустой, входной массив имеет один элемент, входной массив не является массивом, убрать пустые (null и undefined) элементы из входного массива args.
2. Сохранить в “словарь объектов” objects каждый аргумент из args, если его там ещё нет. Ключом в словаре будет сам объект из массива args, а значением – уникально сгенерированный идентификатор id. Это нужно для того, чтобы если мы в дальнейшем встретим внутри объектов из массива args объект из словаря objects, то не создавали новые объекты и не разрушали циклические зависимости, а использовали имеющиеся объекты в словаре objects [4].
3. В кэше cache будем хранить результат слияния входных аргументов args. Ключ этого кэша - строка, уникальным образом идентифицирующая входной массив args (например идентификаторы id объектов из массива args сцепленные символом “:”). Значениям кэша будет являться объект result, с единственным полем “value”, значением которого будет являться результат слияния. Использование такой структуры объекта result позволяет мутировать его содержимое, при передаче его в качестве аргумента в функцию слияния. Мы сразу можем передать на вход функции слияния такой объект result, изначально инициализировав его пустым объектом. Впоследствии этот объект будет наполняться данными и эти данные будут “обновляться” и в объекте кэша [5].
4. Этап слияния:

4.1. Проверить есть ли в кэше результат слияния? Если да, то вернуть данные из кэша.

4.2. В первую очередь необходимо запомнить в локальное множество keys ключи первого уровня всех объектов из args.

4.3. Инициализируем объект result “пустым" значением: { value: undefined }

4.4. Для каждого ключа key из keys мы находим значение value из массива args.

4.5. Рекурсивно вызываем функцию слияния merge с values в качестве входного массива объектов и создаём новый локальный result. После рекурсивного вызова функции слияния сохраняем локальный result в глобальный result.

В результате работы предложенного алгоритма мы получим объединённый объект со всеми полями объектов из массива аргументов. Использование кэша cache и словаря objects позволяет правильным образом обрабатывать циклические и перекрёстные зависимости, избежать ссылок на исходные объекты, чтобы результат был полностью самодостаточным. Все циклические ссылки будут указывать на поля результирующего объекта. Также в данном алгоритме не возникает бесконечных циклов, так как используется кэш и результат циклической ссылки будет браться из него.

Заключение

В данной научной статье представлен алгоритм и методика слияния объектов с циклическими и перекрёстными зависимостями. Работа с объектами, содержащими сложные внутренние связи, представляет вызовы для разработчиков программного обеспечения и предложенный алгоритм призван решить эти вызовы.

Применение классических рекурсивных методов слияния для объектов с циклическими зависимостями может привести к проблемам бесконечной рекурсии. Предложенный алгоритм, основанный на использовании кэша, позволяет эффективно обрабатывать циклические зависимости, избегая бесконечных циклов и обеспечивая создание результатов слияния без ссылок на внешние объекты.

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

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

1. Akinjide Bankole, Circular Reference in JavaScript [Электронный ресурс] - URL: https://www.akinjide.me/2018/circular-reference-in-javascript (дата обращения: 20.07.2020)
2. David Walsh, JavaScript Deep Merge [Электронный ресурс] - URL: https://davidwalsh.name/javascript-deep-merge (дата обращения: 20.07.2020)
3. Pragmatic Maciej, Data mutation in functional JavaScript [Электронный ресурс] - URL: https://dev.to/macsikora/data-mutation-in-functional-javascript-1h97 (дата обращения: 20.07.2020)
4. Prashant Yadav, How to merge objects in javascript [Электронный ресурс] - URL: https://learnersbucket.com/examples/interview/how-to-merge-objects-in-javascript (дата обращения: 20.07.2020)
5. Потапов Д. Р. Обзор алгоритмов кэширования для использования в самоадаптирующихся контейнерах данных / Д. Р. Потапов // Информатика: проблемы, методы, технологии: Материалы XX Международной научно-методической конференции, Воронеж, 13–14 февраля 2020 года / Под редакцией А.А. Зацаринного, Д.Н. Борисова. – Воронеж: "Научно-исследовательские публикации" (ООО "Вэлборн"), 2020. – С. 1273-1282. – EDN RUHDWI.