Дано: Справочник. У него есть табличная часть в которой ссылки на элементы этого же справочника.
Эти элементы (из тч элементов 1-го уровня) ссылаются на другие элементы этого же справочника и т.д....
Вопросы:
1) Как определить максимальную вложенность?
2) Как проверить "зацикленность" (ссылки "по кругу")?
З.Ы. Известные мне решения меня не устраивают по ряду причин. Ищу свежие идеи...
цикливания нет, то не больше количества элементов в данном справочнике.
Вроде и очевидная вещь, но лично мне - буквально "открыли глаза".
Одно из моих "недовольств" известных мне решений - определение количества итераций...
Т.е. КоличествоИтераций <= КоличествоЭлементов
(5) так это запрос с зашивкой определенного уровня вложенности,
а в теме уровень произвольный, максимально возможный, т.е. неограниченный!
в настоящем СКЛ такой перебор можно было сделать в хранимой процедуре, где на вход подаются результаты запроса СКЛ
все это в процедуре СУБД
в 1С (пока) нет доступа/работы с хранимыми процедурами,
остается только цикл
но практике особо уж большая вложенность (да больше 10) уже очень редко встречается
но даже до 20-30 уровневой вложенности все-же можно оформить в вашем запросе
(11) ну если база у вас с СКЛ, то через механизм АДО (СОМ объект) и к хранимой процедуре,
которая будет вам возвращать таблицу/иерархию, ну или какие вам там результаты нужы...
тогда мы не можем легко получить количество отцов первого уровня и количество бездетных сыновей.
1. для получения максимальной глубины достаточно рассмотреть глубину родословной бездетных сыновей, а если стоит запрет на смену отцовства и фиксировать глубину в некоторый ресурс, то максимум по этому ресурсу и есть максимальная глубина вложенности.
2. Если проверяя глубину родословной переходя от сына к отцу и т.д. дойдете до себя же, того с которого начали, то это признак зацикленности.
ЗЫ: Регистр сведений можно использовать только для построения модели. С ним нагляднее. А потом запросы переделать на отношения из других структур
19.
user1220551
22.12.21 02:13 Сейчас в теме+0.5 $m
Дисклеймер: В коде ниже есть много страшных вещей: Условие "НЕ В (ВЫБРАТЬ,,)" и прочие ужасные вещи. Самому больно смотреть, но, имеет место быть.
Идея. Использовать рекурсивный менеджер временных таблиц. Найти всех матерей всех возможных дочерей и на этапе какого-то зацикливания, указать на цепочку из 2ух элементов зацикливания. Результат, количество временных таблиц, которое укажет нам на максимальную длину цепочки.
&НаСервере
Процедура ПроверкаВложенностиНаСервере()
МенеджерВременныхТаблиц = Новый МенеджерВременныхТаблиц;
РекФункция(МенеджерВременныхТаблиц);
Сообщить(МенеджерВременныхТаблиц.Таблицы.Количество());
ТЗ = ТаблицаПарЦиклов(МенеджерВременныхТаблиц);
МенеджерВременныхТаблиц = Неопределено;
КонецПроцедуры
&НаСервере
Процедура РекФункция(МенеджерВременныхТаблиц, КолвоИтераций = 20)
КолвоВремТаблиц = МенеджерВременныхТаблиц.Таблицы.Количество();
Запрос = Новый Запрос;
Если КолвоВремТаблиц = 0 Тогда
Запрос.Текст = ТекстОсновногоЗапроса();
Иначе
Запрос.Текст = ТекстРекурсивногоЗапроса();
КонецЕсли;
ВтИерархияПред = "ВтИерархия" + (КолвоВремТаблиц - 1);
ВтИерархияТек = "ВтИерархия" + КолвоВремТаблиц;
////////////////
Запрос.МенеджерВременныхТаблиц = МенеджерВременныхТаблиц;
Запрос.Текст = СтрЗаменить(Запрос.Текст, "ВтИерархияПред", ВтИерархияПред);
Запрос.Текст = СтрЗаменить(Запрос.Текст, "ВтИерархияТек", ВтИерархияТек);
МассивОбъединения = Новый Массив;
Для Ит = 1 По КолвоВремТаблиц Цикл
МассивОбъединения.Добавить(ДополнитьОбъединением(Ит));
КонецЦикла;
Запрос.Текст = СтрЗаменить(Запрос.Текст, "%ТекстОбъединения%", СтрСоединить(МассивОбъединения, " ОБЪЕДИНИТЬ ВСЕ "));
Запрос.Выполнить();
Если НЕ МенеджерВременныхТаблиц.Таблицы[КолвоВремТаблиц].ПолучитьДанные().Пустой() Тогда
РекФункция(МенеджерВременныхТаблиц, КолвоИтераций);
КонецЕсли;
КонецПроцедуры
//ВЫБОР всех пар Мать-Дочь. Первоначальные данные.
Функция ТекстОсновногоЗапроса()
Возврат "ВЫБРАТЬ
| ВтИерархияТек.Ссылка = ВтИерархияТек.Дочь КАК Зациклен,
| МойСправочник.Ссылка КАК Мать,
| ЕСТЬNULL(ВтИерархияТек.Дочь, ЗНАЧЕНИЕ(Справочник.МойСправочник.)) КАК Дочь
|ПОМЕСТИТЬ ВтИерархияТек
|ИЗ
| Справочник.МойСправочник.Дочери КАК ВтИерархияТек
| ЛЕВОЕ СОЕДИНЕНИЕ Справочник.МойСправочник КАК МойСправочник
| ПО ВтИерархияТек.Ссылка = МойСправочник.Ссылка
|ГДЕ
| ВтИерархияТек.Дочь <> ЗНАЧЕНИЕ(Справочник.МойСправочник.ПустаяСсылка)";
КонецФункции
Функция ТекстРекурсивногоЗапроса()
Возврат "ВЫБРАТЬ РАЗЛИЧНЫЕ
| ВтИерархияТек.Дочь = ВтИерархия.Мать КАК Зациклен,
//Если зациклена, то пару первый и последний элемент цикла, обзываем зацикливанием
| ВЫБОР КОГДА ВтИерархияТек.Дочь = ВтИерархия.Мать ТОГДА ВтИерархияТек.Мать ИНАЧЕ ВтИерархия.Мать КОНЕЦ КАК Мать,
| ВтИерархияТек.Дочь КАК Дочь
|ПОМЕСТИТЬ ВтИерархияТек
|ИЗ
| ВтИерархияПред КАК ВтИерархияТек
| ВНУТРЕННЕЕ СОЕДИНЕНИЕ (ВЫБРАТЬ
| МАКСИМУМ(ВтИерархия.Зациклен) КАК Зациклен,
| ВтИерархия.Мать КАК Мать,
| ВтИерархия.Дочь КАК Дочь
| ИЗ
| (%ТекстОбъединения%) КАК ВтИерархия
|
| СГРУППИРОВАТЬ ПО
| ВтИерархия.Мать,
| ВтИерархия.Дочь) КАК ВтИерархия
//Выбор пары мать(метери(матери..))-дочь. Соединением подбираем всех бабушек (Если мать = дочь, тогда мать матери = бабушка)
| ПО ВтИерархияТек.Мать = ВтИерархия.Дочь
//Не подбираем матерей, которые буду дочерьми своих дочерей (Отсеиваем парадоксы)
| И НЕ ВтИерархия.Зациклен
|ГДЕ
| НЕ (ВтИерархия.Мать, ВтИерархияТек.Дочь) В (ВЫБРАТЬ РАЗЛИЧНЫЕ ВтИерархия.Мать, ВтИерархия.Дочь ИЗ (%ТекстОбъединения%) КАК ВтИерархия)
| И НЕ ВтИерархияТек.Зациклен";
КонецФункции
//Берем всевозможные варианты циклов.
Функция ДополнитьОбъединением(Ит)
Возврат СтрЗаменить("ВЫБРАТЬ
| ВтИерархия.Зациклен КАК Зациклен,
| ВтИерархия.Мать КАК Мать,
| ВтИерархия.Дочь КАК Дочь
|ИЗ
| ВтИерархия КАК ВтИерархия", "ВтИерархия", "ВтИерархия" + (Ит - 1))
КонецФункции
Функция ТаблицаПарЦиклов(МенеджерВременныхТаблиц)
Запрос = Новый Запрос("ВЫБРАТЬ РАЗЛИЧНЫЕ
| ВтИерархия.Мать КАК Мать,
| ВтИерархия.Дочь КАК Дочь
|ИЗ
| (%ТекстОбъединения%) КАК ВтИерархия
|ГДЕ
| ВтИерархия.Зациклен");
Запрос.МенеджерВременныхТаблиц = МенеджерВременныхТаблиц;
МассивОбъединения = Новый Массив;
Для Ит = 1 По МенеджерВременныхТаблиц.Таблицы.Количество() Цикл
МассивОбъединения.Добавить(ДополнитьОбъединением(Ит));
КонецЦикла;
Запрос.Текст = СтрЗаменить(Запрос.Текст, "%ТекстОбъединения%", СтрСоединить(МассивОбъединения, " ОБЪЕДИНИТЬ ВСЕ "));
Возврат Запрос.Выполнить().Выгрузить();
КонецФункции
Показать
К сожалению, для большого объема данных, данная часть, очень сильно кладёт быстродействие:
НЕ (ВтИерархия.Мать, ВтИерархияТек.Дочь) В (ВЫБРАТЬ РАЗЛИЧНЫЕ ВтИерархия.Мать, ВтИерархия.Дочь ИЗ (%ТекстОбъединения%) КАК ВтИерархия)
. Можно попробовать как-нибудь обойти.
И, надо еще где-то подшаманить. Думаю, или как раз это медленное условие. Запрос съедает цепочку, она сворачивается.
Например abcde на 2jй проходке вернет цепочки ac bd ce. а на 3ей ad be ae. и вот как раз ae и съело следующую цепочку. Отсюда и глубина будет неправильной.
Думаю, эту часть надо переписать, чтобы продлевать цепочки по одному элементу, но при этом учитывать, зацикленность.
(ВЫБРАТЬ
| МАКСИМУМ(ВтИерархия.Зациклен) КАК Зациклен,
| ВтИерархия.Мать КАК Мать,
| ВтИерархия.Дочь КАК Дочь
| ИЗ
| (%ТекстОбъединения%) КАК ВтИерархия
|
| СГРУППИРОВАТЬ ПО
| ВтИерархия.Мать,
| ВтИерархия.Дочь)
(22)
Выбираются все подчиненные. Запоминаются в ТЗ.
Для них - выбираются все подчиненные и проверка что уже есть в ТЗ. Текущие + в ТЗ.
(используется промежуточная ТЗ - итог предыдущей выборки)
и так да Максимального количества итераций ( у меня 20 - проверял "ручками" - максимум вложений = 12)
Из категории "паранойя": Итоговая ТЗ + колонка "Количество" все =1. Сворачивается по Статье, сумма "Количество", если >1 признак зацикливания...
Из категории "паранойя": Итоговая ТЗ + колонка "Количество" все =1. Сворачивается по Статье, сумма "Количество", если >1 признак зацикливания...
А какие колонки в ТЗ? Родитель, подчиненный? или только подчиненный? В ситуации когда есть элемент а, у него подчиненные элементы b и с. А у них, в свою очередь подчиненный элемент f. Цикла нет. Но f будет в ТЗ 2 раза. Ошибочного результата цикла не будет?
Переписал запросы (оптимизировал) Для базы, где имеется 8000+ на первом уровне связей, максимальной цепочкой в 14 элементов и 4000+ различных зацикленных цепочек алгоритм выполнялся около 5 секунд.
&НаСервере
Процедура ПроверкаВложенностиНаСервере()
МенеджерВременныхТаблиц = Новый МенеджерВременныхТаблиц;
РекФункция(МенеджерВременныхТаблиц);
Сообщить(МенеджерВременныхТаблиц.Таблицы.Количество()-1);
ТЗ = ТаблицаПарЦиклов(МенеджерВременныхТаблиц);
МенеджерВременныхТаблиц = Неопределено;
КонецПроцедуры
&НаСервере
Процедура РекФункция(МенеджерВременныхТаблиц, КолвоИтераций = 20)
КолвоВремТаблиц = МенеджерВременныхТаблиц.Таблицы.Количество();
Запрос = Новый Запрос;
Если КолвоВремТаблиц = 0 Тогда
Запрос.Текст = ТекстОсновногоЗапроса();
Иначе
Запрос.Текст = ТекстРекурсивногоЗапроса();
КонецЕсли;
ВтИерархияПред = "ВтИерархия" + (КолвоВремТаблиц - 1);
ВтИерархияТек = "ВтИерархия" + КолвоВремТаблиц;
////////////////
Запрос.МенеджерВременныхТаблиц = МенеджерВременныхТаблиц;
Запрос.Текст = СтрЗаменить(Запрос.Текст, "ВтИерархияПред", ВтИерархияПред);
Запрос.Текст = СтрЗаменить(Запрос.Текст, "ВтИерархияТек", ВтИерархияТек);
МассивОбъединения = Новый Массив;
Для Ит = 1 По КолвоВремТаблиц Цикл
МассивОбъединения.Добавить(ДополнитьОбъединением(Ит, Ит < КолвоВремТаблиц));
КонецЦикла;
Запрос.Текст = СтрЗаменить(Запрос.Текст, "ТекстОбъединения", СтрСоединить(МассивОбъединения, " ОБЪЕДИНИТЬ ВСЕ "));
Запрос.Выполнить();
Если НЕ МенеджерВременныхТаблиц.Таблицы[КолвоВремТаблиц].ПолучитьДанные().Пустой() Тогда
РекФункция(МенеджерВременныхТаблиц, КолвоИтераций);
КонецЕсли;
КонецПроцедуры
//ВЫБОР всех пар Мать-Дочь. Первоначальные данные.
Функция ТекстОсновногоЗапроса()
Возврат "ВЫБРАТЬ
| ВтИерархияТек.Ссылка = ВтИерархияТек.Дочь КАК Зациклен,
| ВтИерархияТек.Ссылка КАК Мать,
| ВтИерархияТек.Дочь КАК Дочь
|ПОМЕСТИТЬ ВтИерархияТек
|ИЗ
| Справочник.МойСправочник.Дочери КАК ВтИерархияТек
|ГДЕ
| ВтИерархияТек.Дочь <> ЗНАЧЕНИЕ(Справочник.МойСправочник.)
|
|ИНДЕКСИРОВАТЬ ПО
| Мать,
| Дочь";
КонецФункции
Функция ТекстРекурсивногоЗапроса()
Возврат "ВЫБРАТЬ
| МАКСИМУМ(ВтИерархия.Зациклен) КАК Зациклен,
| ВтИерархия.Мать КАК Мать,
| ВтИерархия.Дочь КАК Дочь,
| МАКСИМУМ(ВтИерархия.Использовалось)
|ПОМЕСТИТЬ ВтИерархияВрем
|ИЗ
| (ТекстОбъединения) КАК ВтИерархия
|
|СГРУППИРОВАТЬ ПО
| ВтИерархия.Мать,
| ВтИерархия.Дочь
|;
|
|////////////////////////////////////////////////////////////////////////////////
|ВЫБРАТЬ
| МАКСИМУМ(ВтИерархияТек.Зациклен) КАК Зациклен,
| ВтИерархияТек.Мать КАК Мать,
| ВтИерархияТек.Дочь КАК Дочь
|ПОМЕСТИТЬ ВтИерархияТек
|ИЗ
| (ВЫБРАТЬ РАЗЛИЧНЫЕ
| ВтИерархияТек.Дочь = ВтИерархия.Мать КАК Зациклен,
| ВЫБОР
| КОГДА ВтИерархияТек.Дочь = ВтИерархия.Мать
| ТОГДА ВтИерархияТек.Мать
| ИНАЧЕ ВтИерархия.Мать
| КОНЕЦ КАК Мать,
| ВтИерархияТек.Дочь КАК Дочь,
| ЛОЖЬ КАК Использовалось
| ИЗ
| ВтИерархияПред КАК ВтИерархияТек
| ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВтИерархия0 КАК ВтИерархия
| ПО ВтИерархияТек.Мать = ВтИерархия.Дочь
| ГДЕ
| НЕ ВтИерархияТек.Зациклен
|
| ОБЪЕДИНИТЬ ВСЕ
|
| ВЫБРАТЬ
| Ложь,
| ВтИерархияВрем.Мать,
| ВтИерархияВрем.Дочь,
| ВтИерархияВрем.Использовалось
| ИЗ
| ВтИерархияВрем КАК ВтИерархияВрем) КАК ВтИерархияТек
|
|СГРУППИРОВАТЬ ПО
| ВтИерархияТек.Мать,
| ВтИерархияТек.Дочь
|
|ИМЕЮЩИЕ
| НЕ МАКСИМУМ(ВтИерархияТек.Использовалось)
|;
|
|////////////////////////////////////////////////////////////////////////////////
|УНИЧТОЖИТЬ ВтИерархияВрем";
КонецФункции
//Берем всевозможные варианты циклов.
Функция ДополнитьОбъединением(Ит, Использовалось)
Возврат СтрЗаменить(СтрЗаменить("ВЫБРАТЬ
| ВтИерархия.Зациклен КАК Зациклен,
| ВтИерархия.Мать КАК Мать,
| ВтИерархия.Дочь КАК Дочь,
| &Использовалось КАК Использовалось
|ИЗ
| ВтИерархия КАК ВтИерархия", "ВтИерархия", "ВтИерархия" + (Ит - 1)), "&Использовалось", Формат(Использовалось, "БЛ=ЛОЖЬ; БИ=ИСТИНа"));
КонецФункции
Функция ТаблицаПарЦиклов(МенеджерВременныхТаблиц)
Запрос = Новый Запрос("ВЫБРАТЬ РАЗЛИЧНЫЕ
| ВтИерархия.Мать КАК Мать,
| ВтИерархия.Дочь КАК Дочь
|ИЗ
| (ТекстОбъединения) КАК ВтИерархия
|ГДЕ
| ВтИерархия.Зациклен");
Запрос.МенеджерВременныхТаблиц = МенеджерВременныхТаблиц;
МассивОбъединения = Новый Массив;
Для Ит = 1 По МенеджерВременныхТаблиц.Таблицы.Количество() Цикл
МассивОбъединения.Добавить(ДополнитьОбъединением(Ит, Ложь));
КонецЦикла;
Запрос.Текст = СтрЗаменить(Запрос.Текст, "ТекстОбъединения", СтрСоединить(МассивОбъединения, " ОБЪЕДИНИТЬ ВСЕ "));
Возврат Запрос.Выполнить().Выгрузить();
КонецФункции
А вообще, если дружите с математикой и разбираетесь в синтаксисе других языков (не обязательно) почитайте про "Алгоритм поиска в глубину" и "Поиск цикла в ориентированном графе" на основании него. Я думаю, это будет оптимальный пример решения вашей задачи, если нужна проверка при записи.
Функция ПолучитьРодителя(СправочникСсылка)
Пока НЕ СправочникСсылка.Родитель.Пустая() Цикл
СправочникСсылка = СправочникСсылка.Родитель;
КонецЦикла;
Возврат СправочникСсылка;
КонецФункции
Показать
Фича в том что родитель самого верхнего родителя обязательно будет пустым, или он не верхний, таким образом не важно количество вложений
но в вашей ситуации с зацикливаением можно напоротся на рекурсию :(
(1) Вообще у справочников есть метод ПолноеНаименование(). Я хз насчет оптимальности, потому что реализация методов платформы известна одним только разработчикам, надо делать замеры, смотреть что эффективнее рекурсивный обход или этот метод. Но этот метод просто проще использовать. Делаешь ПолноеНаименование() у каждого элемента и считаешь количество слэшей (если их конечно нет в именах элементов), берешь максимум - вот и максимальный уровень вложенности в 2 строчки.
Зацикленность тоже просто проверить, если есть полные пути, 1с очень быстро работает со строками, алгоритмы поиска и конкатенации строк в 1с на уровне.
(28) Всё конечно хорошо, но в топике вопрос не о подчинении элементов (иерархии) в справочнике, а о ссылках в табличной части элемента на другие элементы того же справочника...
Так что уровень иерархии может быть 1, а ссылки на друг друга - дофига, так что метод ПолноеНаименование() в данном случае абсолютно неприменимо...