Преобразование массива структур в дерево значений. Представление массива подчиненных друг другу "объектов" в иерархическом виде без использования рекурсии

07.11.17

Разработка - Математика и алгоритмы

Задача преобразовать массив некоторых структур в дерево значений возникла, когда я получил JSON от сервиса о структуре папок пользователя. А именно строка JSON была получена через API Google Drive, когда пользователю предлагается выбрать одну из его папок. При преобразовании JSON у меня получился массив структур, в которых есть некоторый ключ уникальности и ключ родителя-структуры. Предлагаю ознакомиться с алгоритмом не использующую рекурсию, который достаточно быстро создает дерево значений, для последующего показа пользователю.

Скачать файлы

Наименование Файл Версия Размер
Преобразование JSON в ДеревоЗначений.
.epf 11,48Kb
23
.epf 1.0.0 11,48Kb 23 Скачать

Для чего эта публикация;

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

 

Итак, на входе мы имеем JSON, полученный от сервера Google, с помощью API DRIVE. А также желание отобразить пользователю его же папки, но в форме 1С.

Входящие данные - строку JSON вида: И желаемый результат, который нужно показать пользователю
[{
"ID": "MDH8HMBK",
"Title": "Стулья"
},
{
"ID": "JK8YYNCDZ",
"Title": "Табуреты",
"Parent": "MDH8HMBK"
},
{
"ID": "VXU4HUNBBE",
"Title": "Табуреты деревянные",
"Parent": "JK8YYNCDZ"
},
{
"ID": "3AE7MZZMV4",
"Title": "Табуреты металические",
"Parent": "JK8YYNCDZ"
},
….
]

Из строки json такого вида мы с легкостью можем получить массив структур, с которым и будем работать. Для отображения на форме нам из массива нужно получить дерево значений. Бродя по просторам Инфостарт нашел только одно решение (извините, возможно плохо искал) : Пример преобразования дерева значений в таблицу значений и обратно в 1Cv8. Но автор использует в качестве Ключей и КлючейСвязи числовые значения. Также все это происходит в ТаблицаЗначений , где есть внутренние методы сортировки и поиска. В структурах же этого нету. Конечно, первой же идеей было воспользоваться промежуточным вспомогательным объектом ТаблицаЗначений, в котором и определить эти ключи. Но это решение мне не нравится - оно заберет вычислительные ресурсы. Также мне не нравится использование рекурсии в таких задачах - привет Стиву Макконелу и его отношению к рекурсии. Тем более рекурсия снова же достаточно много кушает ресурсов.

Если мы не хотим использовать ТаблицуЗначений, значит в нашем распоряжении есть неизменный спутник массива - цикл обхода массива. И жаль, но обходить придется несколько раз. Это тоже меня не устраивает, поэтому количество обходов нужно сократить до минимума.

Для последующего объяснения алгоритма я воспользуюсь несколько упрощенными начальными данными: пускай это будет массив структур, в каждой из которых будет по два свойства "Родитель" и "Наименование" (Ключ и КлючСвязи соответсвенно). Причем эти свойства будут содержать в себе непосредственно наименования наших отображаемых данных:

И так, первое что мы делаем это создаем ДеревоЗначений, добавляем нужные колонки и создаем корневые строки. Для этого нужно пройти по всему массиву и посмотреть заполнено ли у каждой структуры свойство "Родитель". И если не заполнено, тогда добавить в дерево как корневой элемент;

	МассивДанных = ПолучитьМассивСтруктур();	

	ДеревоРезультат = Новый ДеревоЗначений;
	ДеревоРезультат.Колонки.Добавить("Наименование");
	КоличествоЭлементов = МассивДанных.Количество(); //Для кэша, и понадобиться нам 
	
	Для Сч = 0 По КоличествоЭлементов - 1 Цикл
		ЭлементДанных = МассивДанных[сч];
		Если Не ЗначениеЗаполнено(ЭлементДанных.Родитель) Тогда
			СтрокаДЗ = ДеревоРезультат.Строки.Добавить();
			СтрокаДЗ.Наименование = ЭлементДанных.Наименование;
		КонецЕсли;
	КонецЦикла;

Так... Начало заложено :). Теперь мы должны взять у каждого корневого элемента значение свойства "Наименование" и найти структуры с этим значением в свойстве "Родитель". Но ведь это несет в себе определенные затраты.

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

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

	
	МассивДанных = ПолучитьМассивСтруктур();

	ДеревоРезультат = Новый ДеревоЗначений;
	ДеревоРезультат.Колонки.Добавить("Наименование");

	КоличествоЭлементов = МассивДанных.Количество(); 
	ИндексОбработки = 0; // Индекс элемента массива, еще не помещенного в дерева значений

	Для Сч = 0 По КоличествоЭлементов - 1 Цикл
		ЭлементДанных = МассивДанных[сч];
		Если Не Заполнено(ЭлементДанных.Родитель) Тогда
			СтрокаДЗ = ДеревоРезультат.Строки.Добавить();
			СтрокаДЗ.Наименование = ЭлементДанных.Наименование;
			
			Если сч = ИндексОбработки Тогда
				ИндексОбработки = ИндексОбработки+1; // Перемещать не нужно
				Продолжить;
			КонецЕсли;
			//Перемещаем обработанный элемент в начало массива и увеличиваем индекс обработки
			МассивДанных[сч] = МассивДанных[ИндексОбработки];
			МассивДанных[ИндексОбработки] = ЭлементДанных;
			ИндексОбработки = ИндексОбработки+1;			
		КонецЕсли;		
	КонецЦикла;

Вот теперь все более в порядке. Нам не нужно производить поиск среди всех элементов, а начинать только с тех, которые не помещены в ДеревоЗначений.

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

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

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

	МассивДанных = ПолучитьМассивСтруктур();

	ДеревоРезультат = Новый ДеревоЗначений;
	ДеревоРезультат.Колонки.Добавить("Наименование");
	КоличествоЭлементов = МассивДанных.Количество(); 
	ИндексОбработки = 0;
	МассивСтрок = Новый Массив(КоличествоЭлементов); // Наш вспомогательный массив 
	//Заполнение корневых элементов
	Для Сч = 0 По КоличествоЭлементов - 1 Цикл
		ЭлементДанных = МассивДанных[сч];
		Если НЕ ЗначениеЗаполнено(ЭлементДанных.Родитель)Тогда
			МассивСтрок[ИндексОбработки] = ДеревоРезультат.Строки.Добавить();
			ЗаполнитьЗначенияСвойств(МассивСтрок[ИндексОбработки],ЭлементДанных);
			
			Если сч = ИндексОбработки Тогда
				ИндексОбработки = ИндексОбработки+1;
				Продолжить;
			КонецЕсли;
			МассивДанных[сч] = МассивДанных[ИндексОбработки];
			МассивДанных[ИндексОбработки] = ЭлементДанных;
			ИндексОбработки = ИндексОбработки+1;
		КонецЕсли;
	КонецЦикла;
	//Поиск дочерних элементов
	Для Сч = 0 По КоличествоЭлементов - 1 Цикл
		Если ИндексОбработки = КоличествоЭлементов ИЛИ Сч = ИндексОбработки  Тогда
				//Если ИндексОбработки достигнет конца массива, нам больше незачем искать дочерние элементы
				// Если Сч станет равным ИндексОбработки, это свидетельствет о зацикленности подчинения
			Прервать;
		КонецЕсли;
		
		КлючПоиска = МассивДанных[сч].Наименование;
		Для Сч2 = ИндексОбработки По КоличествоЭлементов - 1 цикл
			ЭлементДанных = МассивДанных[Сч2];
			Если ЭлементДанных.Родитель = КлючПоиска Тогда
				МассивСтрок[ИндексОбработки] = МассивСтрок[Сч].Строки.Добавить();
				ЗаполнитьЗначенияСвойств(МассивСтрок[ИндексОбработки],ЭлементДанных);
				
				Если Сч2 = ИндексОбработки Тогда
					ИндексОбработки = ИндексОбработки+1;
					Продолжить;
				КонецЕсли;
				МассивДанных[Сч2] = МассивДанных[ИндексОбработки];
				МассивДанных[ИндексОбработки] = ЭлементДанных;
				ИндексОбработки = ИндексОбработки+1;				
			КонецЕсли;			
		КонецЦикла;		
	КонецЦикла;

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

Таким же методом, без использования рекурсии, возможна и обратная процедура. Например вывод ДереваЗначений в сообщения. Только тут  для удобства нужно выводить еще и уровень, потому снова воспользуюсь массивом структур:

	МассивСтрок = Новый Массив;
	КолонкиДЗ = ДеревоЗначений.Колонки;
	Для Каждого СтрокаДЗ из ДеревоЗначений.Строки Цикл
		МассивСтрок.Добавить(СтрокаДЗ);	
	КонецЦикла;
	
	Сч = 0;
	Пока Сч < МассивСтрок.Количество() Цикл
		СтрокаДЗ = МассивСтрок[Сч];
		Отступы = "";
		Для КоличествоОтступов = 1 По СтрокаДЗ.Уровень() Цикл
			Отступы = Отступы + Символы.Таб;
		КонецЦикла;	
		
		СтрокаОтборажения = Отступы;	
		Для Каждого КолонкаДерева из КолонкиДЗ Цикл 
			СтрокаОтборажения = СтрокаОтборажения + Строка(СтрокаДЗ[КолонкаДерева.Имя]) + "| ";
		КонецЦикла;
		Сообщить(СтрокаОтборажения);
		Для Каждого ПодстрокаДЗ из СтрокаДЗ.Строки Цикл
			МассивСтрок.Вставить(Сч+1,ПодстрокаДЗ);
		КонецЦикла;
		Сч = Сч +1;
		
	КонецЦикла;

Интересное замечание, которое было получено в ходе тестирования обработки: если создать у ДереваЗначений колонку "Родитель" или "Parent", то ее никак не будет возможно заполнить, потому что у строки ДереваЗначений есть предопределенное свойство "Родитель" или англоязычный аналог "Parent" .

Прикрепляю обработку для тестирования данного алгоритма. В ней алгоритм имеет более универсальный функционал

Дерево значений деревоЗначений Массив структура JSON рекурсия API google отображение папок

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4417    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7462    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8838    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7804    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. kirillkr 29 07.11.17 11:34 Сейчас в теме
Неужели рекурсия так много съедает ресурсов компьютера, чтобы городить такой велосипед с циклами, сортировками, опять с циклами, опять с циклами и все это в памяти.
ИНТЕГРА; +1 Ответить
2. Arxxximed 34 07.11.17 12:00 Сейчас в теме
(1)в целом использование рекурсии иногда оправдано иногда нет. Например при простом чтении дерева значений рекурсия более оправдана. Я показал Альтернативный метод, при котором не нужно беспокоится о переполнении стека. При построении же дерева в данном случае без сортировки и цикла не обойтись. Искал метод с минимальными обходами массивов.
3. MarryJane 31 08.11.17 00:04 Сейчас в теме
Скажите коллега, а вот можете вы привести сравнительный анализ с рекурсией и без рекурсии. И таблицу например на 100000 строк.
4. kiruha 388 08.11.17 11:31 Сейчас в теме
Как только у пользователя тормозит отображение списка - в 90% случаях - дерево.
Имхо у него платформенная не оптимальная реализация.
Лучше работать уж "массивом структур"
5. Arxxximed 34 08.11.17 12:19 Сейчас в теме
(4)Коллега, не понял про что Вы. Поясните! У кого платформенная реализация? и реализация чего? и почему не оптимальная?
Задача - дать пользователю выбрать одну из его папок. Выбор лучше отобразить в виде иерархии. На входе имеется масссив структур. Подскажите как сделать по другому???
6. kiruha 388 08.11.17 12:37 Сейчас в теме
(5)
Может непонятно написал, я про то что Дерево у 1С (не у вас) - то еще поделие.
На больших объемах данных тормозит отображение ввиде этого дерева.

В вашем случае объем небольшой, и все ОК сделано.
7. Arxxximed 34 08.11.17 17:07 Сейчас в теме
(6) Обязательно сделаем тесты и сравнительный анализ, как рекомендует (3).
Воообще объемы могут быть и большие, задачи то разные бывают... Кто его знает, может и вздумается какому нибудь пользователю сделать 9000 вложенных папок в своем Google Drive.
8. МихаилМ 08.11.17 17:52 Сейчас в теме
Загрузите данные не в массив структур , а в ТЗ . Из ТЗ построительзапроса умеет делать ДЗ.
Сурикат; +1 Ответить
9. Arxxximed 34 10.11.17 12:18 Сейчас в теме
(8)В публикации это рассматривается. Смысл теряется. Мы тогда создаем дополнительный объект, который жрет память. А потом еще и использование построителя запроса... Это возможно выгодно, когда заранее известно, что объем данных ДЗ маленький. Но снова же, нужно провести сравнительный анализ.

Только вот мне дали замечание , что я изобретаю велосипед с циклами. ТЗ же формируется тоже циклом. А потом построитель будет осуществлять поиск и сортировку. Я же показал как это сделать без промежуточного звена
karimov_m; +1 Ответить
10. karimov_m 05.12.17 15:41 Сейчас в теме
(9) В целом, каждый подход в реализации может быть оправдан. В данном случае - это наглядный пример, т.е. так можно написать и это будет работать стабильно, а главное - код прост как валенок, тяжело в нем сделать ошибку.
С другой стороны рекурсия рекурсии рознь. В общем случае, рекурсию можно разделить на два типа (подхода реализации) - Головную и Концевую. Если используется второй подход, рекурсивный вызов выполняется в конце и является последней строчкой кода метода. Этот метод не использует стек вызовов независимо от глубины рекурсии.
Arxxximed; +1 Ответить
11. burni4 87 25.04.18 16:07 Сейчас в теме
закинул JSON, не работает, зря качал
12. Arxxximed 34 26.04.18 15:23 Сейчас в теме
(11) не понял, какой JSON Вы закидывали, и как по вашему оно должно было отработать?
13. burni4 87 26.04.18 16:03 Сейчас в теме
(12) {
"Comment":"My comment",
"Count":10,
"DiskParam": {
"DB":10.000000,
"DBAngle":1.234000 },
"Range":true,
"Blades":[{
"Caption":"A",
"Value":65},{
"Caption":"B",
"Value":66},
{"Caption":"C","Value":67}],"Slots":[0,1,2]}
к примеру вот такой
14. Arxxximed 34 02.05.18 12:10 Сейчас в теме
(13) с чего вы решили, что вот этот пример , должен разобраться? ))) К чему это? это же вообще не по теме!!
Странно требовать от болида хорошо вспахивать землю, а от трактора большой скорости на трассе.

Купил Porsche. Слишком дорого, и людей мало помещается - зря покупал.
15. burni4 87 02.05.18 12:30 Сейчас в теме
(14) Задача преобразовать массив некоторых структур в дерево значений возникла, когда я получил JSON от сервиса о структуре папок пользователя.

я скинул JSON? JSON, массив структур? массив структур - ваша обработка не смогла это прочитать. Осмелюсь предположить что вот эту часть "Slots":[0,1,2]
Оставьте свое сообщение