В практике разработки на платформе 1С:Предприятие часто возникает задача объединения документов в логические группы. Одной из специфических и сложных вариаций этой задачи является ситуация, когда связи между документами (например, заказами) заданы не ссылочным типом, а обычным строковым полем, где номера связанных документов перечислены через запятую. Ситуация осложняется тем, что номера могут указываться без префиксов и лидирующих нулей, а сами связи могут быть транзитивными (если заказ А связан с Б, а Б с В, то все три заказа — А, Б и В — должны попасть в одну группу).
В данной статье мы разберем, как построить производительный алгоритм для решения этой задачи, проанализируем подходы теории графов и реализуем решение на языке 1С.
Представим, что у нас есть массив заказов. В каждом заказе есть поле НомераСопутствующихЗаказов. Нам необходимо разбить исходный массив на несколько подмассивов, каждый из которых будет содержать только взаимосвязанные заказы. Рассмотрим примеры:
Основная сложность заключается в нормализации номеров. Номер в базе может выглядеть как КТ000000031, а в строке связи — просто как 31. Нам потребуется механизм сопоставления этих значений.
Прежде чем приступать к поиску связей, мы должны привести все данные к единому формату. Использовать прямой поиск подстроки (СтрНайти) крайне не рекомендуется, так как номер "9" может быть найден в номере "19" или "90".
Разберем, как правильно подготовить данные. Мы создадим соответствие, где ключом будет «чистый» номер (без префикса и нулей), а значением — ссылка на документ. Для этого воспользуемся следующим подходом:
// Пример приведения номера к формату базы данных
НомерДляПоиска = СокрЛП(НомерИзСтроки);
ДлинаНомераВБД = 11; // Например, стандартная длина для данного типа документа
Префикс = "КТ";
КоличествоНулей = ДлинаНомераВБД - СтрДлина(НомерДляПоиска) - СтрДлина(Префикс);
ПолныйНомер = Префикс + Прав("0000000000" + НомерДляПоиска, КоличествоНулей + СтрДлина(НомерДляПоиска));
Однако более универсальным способом будет хранение «коротких» номеров в объекте Соответствие, чтобы быстро получать ссылку по строковому представлению из поля связи.
С точки зрения информатики, наша задача — это поиск компонент связности в неориентированном графе. Каждый заказ — это узел графа, а связь, указанная в строке — это ребро графа.
Проанализируем эффективный алгоритм реализации. Вместо того чтобы многократно перебирать массив, мы выполним следующие шаги:
СоответствиеНомеров (КороткийНомер -> Ссылка).СоответствиеСвязей, где для каждой ссылки будет храниться массив ссылок, на которые она указывает (исходя из парсинга строки).Рассмотрим готовую функцию, которая принимает массив структур или строк таблицы значений и возвращает массив массивов со сгруппированными ссылками. Мы будем использовать вспомогательную ТаблицаЗначений для отслеживания принадлежности заказа к конкретной группе (индексу связи).
Функция РазбитьЗаказыНаГруппы(МассивСтрок)
ТаблицаСвязей = Новый ТаблицаЗначений;
ТаблицаСвязей.Колонки.Добавить("Заказ");
ТаблицаСвязей.Колонки.Добавить("ИндексГруппы"); // Числовой идентификатор группы
СоответствиеНомеров = Новый Соответствие;
СвязиЗаказа = Новый Соответствие;
// Шаг 1: Индексация номеров для быстрого поиска
Для Каждого Стр Из МассивСтрок Цикл
Реквизиты = ОбщегоНазначения.ЗначенияРеквизитовОбъекта(Стр.Документ, "Номер, НомераСопутствующихЗаказов");
// Очищаем номер от префикса (допустим, первые 2 символа) и нулей
ЧистыйНомер = СокрЛП(Сред(Реквизиты.Номер, 3));
Пока Лев(ЧистыйНомер, 1) = "0" Цикл
ЧистыйНомер = Сред(ЧистыйНомер, 2);
КонецЦикла;
СоответствиеНомеров.Вставить(ЧистыйНомер, Стр.Документ);
СвязиЗаказа.Вставить(Стр.Документ, Реквизиты.НомераСопутствующихЗаказов);
КонецЦикла;
// Шаг 2: Группировка
ТекущийИндекс = 0;
Для Каждого Стр Из МассивСтрок Цикл
Документ = Стр.Документ;
// Проверяем, не распределен ли уже этот заказ в какую-то группу
СтрокаГруппы = ТаблицаСвязей.Найти(Документ, "Заказ");
Если СтрокаГруппы = Неопределено Тогда
ТекущийИндекс = ТекущийИндекс + 1;
РаспределитьВГруппу(Документ, ТекущийИндекс, ТаблицаСвязей, СоответствиеНомеров, СвязиЗаказа);
КонецЕсли;
КонецЦикла;
// Шаг 3: Сборка результата
// Проходим по ТаблицаСвязей и формируем массив массивов
// ... (код сворачивания таблицы по ИндексуГруппы)
Возврат Результат;
КонецФункции
Если количество заказов в массиве исчисляется тысячами, использование таблицы значений с постоянным поиском (Найти) может замедлить работу. В этом случае мы рекомендуем применить алгоритм DSU (Disjoint Set Union).
Суть алгоритма заключается в том, что для каждого элемента мы храним ссылку на «родителя». Изначально каждый заказ — сам себе родитель. Когда мы находим связь между Заказом 1 и Заказом 2, мы выполняем операцию Union(Заказ1, Заказ2), которая делает родителя Заказа 1 родителем Заказа 2. В конце работы алгоритма достаточно один раз проверить родителей для всех элементов: те, у кого общий родитель, принадлежат одной группе.
Преимущества DSU в 1С:
Соответствие, где Ключ — Ссылка, Значение — РодительскаяСсылка.Разберем несколько нюансов, которые могут «сломать» ваш алгоритм в реальных условиях:
СтрЗаменить(ИсходнаяСтрока, Символы.НПП, "").VBScript.RegExp для извлечения всех последовательностей цифр из строки.ЗначенияРеквизитовОбъекта в цикле — плохая практика. Проанализируем ситуацию: лучше один раз выбрать данные всех заказов из массива одним запросом, поместив их во временную таблицу.Выясним причину, почему именно этот алгоритм считается оптимальным. Он минимизирует количество обращений к базе данных и использует структуру Соответствие, которая в 1С реализована как хеш-таблица, обеспечивающая поиск за константное время O(1). Это позволяет эффективно обрабатывать транзитивные зависимости любой вложенности без риска переполнения стека, который мог бы возникнуть при наивной рекурсии.
Таким образом, комбинируя предварительную индексацию номеров и эффективный обход графа связей, мы получаем надежный инструмент для автоматизации бизнес-логики связанных документов.