Как рассчитать вытеснение периодов по приоритетам в 1С?

Задача расчета фактического периода действия записей с учетом их приоритетов — классическая задача для разработчиков 1С. В типовых конфигурациях (например, в «1С:Зарплата и управление персоналом») этот механизм реализован на уровне платформы через регистры расчета и механизм вытеснения. Однако в реальной практике часто возникает необходимость воспроизвести этот алгоритм вручную на чистом SQL/запросе 1С или в коде программного модуля. Это требуется при проектировании кастомных систем планирования, учете занятости оборудования, бронировании или разработке нетиповых подсистем KPI.

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

---

Метод 1. Расчет вытеснения через календарную таблицу дат (в запросе)

Рассмотрим подход, который предложил автор темы. Он базируется на «развертывании» каждого периода в набор отдельных дней, выборе победителя (максимального приоритета) для каждого дня и последующем «склеивании» смежных дней обратно в непрерывные интервалы. Этот метод идеально подходит для небольших интервалов времени (например, в пределах одного года для одного сотрудника).

Разберем алгоритм по шагам:

1. Генерация последовательности дат. Создаем временную таблицу, содержащую каждую уникальную дату внутри интересующего нас общего периода действия. Сделать это в запросе 1С можно с помощью соединения реальных таблиц (например, производственного календаря или системного каталога метаданных) или через генерацию числовой последовательности.
2. Соединение дат с периодами. Выполняем левое соединение таблицы дат с нашей исходной таблицей периодов по условию: дата из календаря должна находиться между датой начала и датой окончания исходного периода.
3. Определение победителя для каждой даты. Используем группировку по конкретной дате и находим запись с максимальным приоритетом (например, через функцию МАКСИМУМ(Приоритет)).
4. Восстановление интервалов (нормализация). Полученную таблицу «Дата — Период с макс. приоритетом» необходимо свернуть обратно в интервалы «ДатаНачала — ДатаОкончания». Для этого мы находим точки изменения периодов (когда для даты $T$ период один, а для даты $T+1$ — уже другой или отсутствует) и связываем их.

Посмотрим на пример реализации первого этапа (получение плоской таблицы победителей по дням) в запросе 1С:

// Шаг 1. Получаем все дни расчетного периода (ВТ_Календарь)
// Шаг 2. Соединяем дни с периодами и выбираем максимальный приоритет на каждый день
ВЫБРАТЬ
    Календарь.Дата КАК ДатаКалендаря,
    МАКСИМУМ(ИсходныеПериоды.Приоритет) КАК МаксПриоритет
ПОМЕСТИТЬ ВТ_МаксимальныеПриоритеты
ИЗ
    ВТ_Календарь КАК Календарь
    ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ_ИсходныеПериоды КАК ИсходныеПериоды
        ПО Календарь.Дата МЕЖДУ ИсходныеПериоды.ДатаНачала И ИсходныеПериоды.ДатаОкончания
ГРУППИРОВАТЬ ПО
    Календарь.Дата;

// Шаг 3. Определяем, какому именно периоду принадлежал этот максимальный приоритет
ВЫБРАТЬ
    МаксПриоритеты.ДатаКалендаря,
    Минимум(ИсходныеПериоды.СсылкаНаПериод) КАК ВыигравшийПериод
ПОМЕСТИТЬ ВТ_ДниСПобедителями
ИЗ
    ВТ_МаксимальныеПриоритеты КАК МаксПриоритеты
    ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ_ИсходныеПериоды КАК ИсходныеПериоды
        ПО МаксПриоритеты.ДатаКалендаря МЕЖДУ ИсходныеПериоды.ДатаНачала И ИсходныеПериоды.ДатаОкончания
        И МаксПриоритеты.МаксПриоритет = ИсходныеПериоды.Приоритет
ГРУППИРОВАТЬ ПО
    МаксПриоритеты.ДатаКалендаря;

Преимущества метода: Высокая наглядность, простота отладки промежуточных данных. Запрос легко писать и читать.

Недостатки: Низкая производительность на больших объемах. Если рассчитывается период в 5 лет для 10 000 сотрудников, промежуточная таблица разрастется до десятков миллионов строк, что приведет к перегрузке tempdb и зависанию СУБД.

---

Метод 2. Оптимизированный запрос без детального календаря (по уникальным границам)

Чтобы избежать генерации миллионов строк для каждого дня, проанализируем более профессиональный подход. Периоды меняют свое состояние только в точках своих границ (даты начала и окончания). Следовательно, нет необходимости проверять каждый день между ними.

Рассмотрим алгоритм оптимизированного запроса:

1. Выбираем все уникальные даты начал и окончаний всех имеющихся периодов. Это дает нам минимальный набор критических точек времени.
2. Соединяем список этих точек «сам с собой» со смещением, чтобы получить элементарные непересекающиеся микроинтервалы [Дата_i, Дата_i+1].
3. Каждый полученный микроинтервал позиционируется внутри исходных периодов (проверяем попадание микроинтервала внутрь границ исходных данных).
4. Для каждого микроинтервала выбираем период с максимальным приоритетом.
5. Объединяем (сворачиваем) идущие подряд микроинтервалы с одинаковым победившим периодом.

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

---

Метод 3. Программный алгоритм нарезки интервалов (в коде 1С)

Если нет жесткого требования выполнять расчет исключительно внутри СУБД, перенос логики в программный код модуля — отличное архитектурное решение. Это разгружает сервер баз данных и позволяет написать понятный код, который легко сопровождать.

Выясним логику эффективного алгоритма «нарезки интервалов» с временной сложностью $O(N^2)$, предложенного разработчиками на форуме:

1. Собираем все граничные даты (все ДатыНачала и все ДатыОкончания из исходных периодов, а также границы расчетного диапазона) в одну таблицу значений или массив.
2. Сортируем полученный список дат по возрастанию и удаляем дубликаты.
3. Строим таблицу элементарных отрезков. Из отсортированных дат $[D_1, D_2, D_3, ..., D_n]$ получаем микропериоды: $[D_1, D_2]$, $[D_2, D_3]$, $[D_3, D_4]$ и так далее. Каждому отрезку присваиваем уникальный индекс.
4. Сортируем исходные периоды по убыванию приоритета (самые важные — первыми).
5. Для каждого исходного периода ищем элементарные отрезки, которые целиком укладываются в его границы:
   • Если отрезок свободен (еще не занят более приоритетным периодом), мы отдаем этот отрезок текущему периоду.
   • Если отрезок уже занят периодом с более высоким приоритетом — текущий период его пропускает (происходит вытеснение).
6. На выходе склеиваем смежные элементарные отрезки, доставшиеся одному и тому же периоду, обратно в цельные интервалы.

Посмотрим на пример программной реализации этого алгоритма:

Функция ВытеснитьПериодыКодом(ИсходныеПериоды, ДатаНачалаИнтервала, ДатаОкончанияИнтервала) Экспорт

    // ИсходныеПериоды - ТаблицаЗначений (Период, ДатаНачала, ДатаОкончания, Приоритет)
    
    // 1. Собираем уникальные граничные даты
    ГраницыДат = Новый ТаблицаЗначений;
    ГраницыДат.Колонки.Добавить("Дата", Новый ОписаниеТипов("Дата"));
    
    Для Каждого Стр Из ИсходныеПериоды Цикл
        // Ограничиваем даты рамками глобального интервала
        ГраницыДат.Добавить().Дата = Макс(Стр.ДатаНачала, ДатаНачалаИнтервала);
        ГраницыДат.Добавить().Дата = Мин(Стр.ДатаОкончания, ДатаОкончанияИнтервала);
    КонецЦикла;
    
    ГраницыДат.Добавить().Дата = ДатаНачалаИнтервала;
    ГраницыДат.Добавить().Дата = ДатаОкончанияИнтервала;
    
    ГраницыДат.Свернуть("Дата");
    ГраницыДат.Сортировать("Дата Возр");
    
    // 2. Создаем элементарные микроинтервалы
    Микроинтервалы = Новый ТаблицаЗначений;
    Микроинтервалы.Колонки.Добавить("ДатаНачала", Новый ОписаниеТипов("Дата"));
    Микроинтервалы.Колонки.Добавить("ДатаОкончания", Новый ОписаниеТипов("Дата"));
    Микроинтервалы.Колонки.Добавить("ПериодПобедитель");
    Микроинтервалы.Колонки.Добавить("Приоритет", Новый ОписаниеТипов("Число"));
    
    Для Индекс = 0 По ГраницыДат.Количество() - 2 Цикл
        НовыйИнтервал = Микроинтервалы.Добавить();
        НовыйИнтервал.ДатаНачала = ГраницыДат[Индекс].Дата;
        НовыйИнтервал.ДатаОкончания = ГраницыДат[Индекс + 1].Дата;
        НовыйИнтервал.Приоритет = -1; // Пока не занят
    КонецЦикла;
    
    // 3. Сортируем исходные периоды по приоритету (по убыванию)
    ИсходныеПериоды.Сортировать("Приоритет Убыв");
    
    // 4. Распределяем микроинтервалы по приоритетам
    Для Каждого ПериодСтрока Из ИсходныеПериоды Цикл
        Для Каждого Интервал Из Микроинтервалы Цикл
            // Проверяем, попадает ли микроинтервал в границы текущего периода
            Если Интервал.ДатаНачала >= ПериодСтрока.ДатаНачала 
               И Интервал.ДатаОкончания <= ПериодСтрока.ДатаОкончания Тогда
                
                // Если интервал еще пуст, отдаем его текущему периоду
                Если Интервал.Приоритет = -1 Тогда
                    Интервал.ПериодПобедитель = ПериодСтрока.Период;
                    Интервал.Приоритет = ПериодСтрока.Приоритет;
                КонецЕсли;
                
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    // 5. Схлопываем смежные интервалы одного периода
    Результат = Новый ТаблицаЗначений;
    Результат.Колонки.Добавить("Период");
    Результат.Колонки.Добавить("ДатаНачала", Новый ОписаниеТипов("Дата"));
    Результат.Колонки.Добавить("ДатаОкончания", Новый ОписаниеТипов("Дата"));
    
    ТекущийПобедитель = Неопределено;
    НачалоТекущегоБлока = '00010101';
    
    Для Каждого Интервал Из Микроинтервалы Цикл
        Если Интервал.Приоритет = -1 Тогда
            // Пустой промежуток, закрываем предыдущий период если он был
            Если ТекущийПобедитель <> Неопределено Тогда
                НоваяСтрока = Результат.Добавить();
                НоваяСтрока.Период = ТекущийПобедитель;
                НоваяСтрока.ДатаНачала = НачалоТекущегоБлока;
                НоваяСтрока.ДатаОкончания = Интервал.ДатаНачала;
                ТекущийПобедитель = Неопределено;
            КонецЕсли;
            Продолжить;
        КонецЕсли;
        
        Если ТекущийПобедитель = Неопределено Тогда
            ТекущийПобедитель = Интервал.ПериодПобедитель;
            НачалоТекущегоБлока = Интервал.ДатаНачала;
        ИначеЕсли ТекущийПобедитель <> Интервал.ПериодПобедитель Тогда
            // Период изменился, фиксируем прошлый
            НоваяСтрока = Результат.Добавить();
            НоваяСтрока.Период = ТекущийПобедитель;
            НоваяСтрока.ДатаНачала = НачалоТекущегоБлока;
            НоваяСтрока.ДатаОкончания = Интервал.ДатаНачала;
            
            // Начинаем новый блок
            ТекущийПобедитель = Интервал.ПериодПобедитель;
            НачалоТекущегоБлока = Интервал.ДатаНачала;
        КонецЕсли;
    КонецЦикла;
    
    // Записываем последний период
    Если ТекущийПобедитель <> Неопределено Тогда
        НоваяСтрока = Результат.Добавить();
        НоваяСтрока.Период = ТекущийПобедитель;
        НоваяСтрока.ДатаНачала = НачалоТекущегоБлока;
        НоваяСтрока.ДатаОкончания = ДатаОкончанияИнтервала;
    КонецЕсли;
    
    Возврат Результат;

КонецФункции

---

Метод 4. Оптимальный алгоритм «сканирующей линии» (Sweep-line)

Для систем с высокими требованиями к производительности (например, расчет тысяч сотрудников со множеством пересекающихся начислений и документов отсутствия) предыдущий алгоритм может показаться медленным из-за вложенного цикла сравнения. В Computer Science для таких задач разработан классический метод сканирующей линии со сложностью всего $O(N \log N)$.

Давайте разберем его концепт:

1. Преобразуем каждый период в два дискретных события:
   • Событие 1: «Начало периода» (с указанием приоритета, ссылки на период и даты).
   • Событие 2: «Конец периода» (с теми же параметрами).
2. Помещаем все события в один массив и сортируем его строго хронологически по дате события.
3. Создаем список «активных в текущий момент периодов».
4. Начинаем виртуальное движение по отсортированным событиям слева направо (по времени):
   • Если встречаем событие «Начало периода» — добавляем его в список активных.
   • Если встречаем событие «Конец периода» — удаляем его из активных.
   • В каждой точке изменения состава активных периодов мы определяем период с наивысшим приоритетом. Как только этот лидер меняется, мы фиксируем границу и записываем в результат отрезок времени, где побеждал предыдущий лидер.

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

---

Рекомендации по выбору решения

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

• Используйте Метод 1 (Календарь в запросе), если вы пишете простой отчет, где выборка гарантированно ограничена небольшим интервалом (например, расчет за один месяц для конкретного подразделения). Это быстро в реализации и легко переносится между конфигурациями.
• Применяйте Метод 3 (Программную нарезку отрезков), если вы выполняете расчет внутри транзакции проведения документа. Чистый код 1С на таблицах значений в памяти сервера приложений работает стабильно, предсказуемо и не создает лишней нагрузки на блокировки базы данных SQL.
• Для высоконагруженных систем с миллионами записей пишите алгоритм на базе Метода 4 (Сканирующая линия), используя встроенные типы соответствий или индексированные таблицы значений для быстрого извлечения максимума из активных периодов.