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

При работе с данными в 1С часто возникает задача преобразования возрастающего числового массива в набор непрерывных диапазонов. Например, массив чисел 1, 3, 4, 5, 7, 8, 9, 10 необходимо представить в виде таблицы:

НачалоДиапазона    КонецДиапазона
1            1
3            5
7            10

Эта задача является классической для программирования, и существует несколько подходов к ее решению, каждый со своими преимуществами и недостатками. Мы рассмотрим три основных метода: итеративный (линейный проход), рекурсивный (метод "разделяй и властвуй") и SQL-подход.

1. Итеративный подход (Линейный проход)

Наиболее простой и часто рекомендуемый способ решения данной задачи — это однократный линейный проход по уже отсортированному массиву. Этот метод отличается своей прямолинейностью, эффективным использованием памяти и предсказуемой производительностью.

Принцип работы:

1. Мы начинаем с первого элемента массива, который становится начальной точкой нового диапазона (Старт) и его конечной точкой (Стоп).
2. Далее мы последовательно перебираем каждый следующий элемент массива.
3. На каждом шаге проверяем, является ли текущий элемент следующим по порядку от предыдущего элемента диапазона (то есть, ТекущийЭлемент == Стоп + 1).
4. Если элементы следуют подряд, это означает, что текущий диапазон продолжается, и мы обновляем его конечную точку (Стоп = ТекущийЭлемент).
5. Если находится разрыв (то есть, ТекущийЭлемент != Стоп + 1), это сигнализирует о завершении текущего непрерывного диапазона. Мы фиксируем его начало (Старт) и конец (Стоп) в результирующей таблице или массиве. Затем мы начинаем новый диапазон, устанавливая Старт и Стоп равными текущему элементу.
6. После завершения прохода по всему массиву, не забываем зафиксировать последний сформированный диапазон.

Пример реализации на 1С:

В этом примере мы используем два вспомогательных массива — МассивСтарт и МассивСтоп — для сбора начал и концов диапазонов соответственно. В реальных задачах можно сразу добавлять строки в ТаблицаЗначений или другую структуру.

&НаСервере
Процедура РазбитьМассивЛинейно(МассивДанных, ТаблицаРезультата)
    // Очищаем ТаблицуРезультата перед началом
    ТаблицаРезультата.Очистить();
    Если МассивДанных.Количество() = 0 Тогда
        Возврат;
    КонецЕсли;

    НачалоДиапазона = МассивДанных[0];
    КонецДиапазона  = МассивДанных[0];

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

    // Добавляем последний диапазон после завершения цикла
    СтрокаТаблицы = ТаблицаРезультата.Добавить();
    СтрокаТаблицы.НачалоДиапазона = НачалоДиапазона;
    СтрокаТаблицы.КонецДиапазона = КонецДиапазона;
КонецПроцедуры

&НаСервере
Процедура КомандаНаСервереЛинейно()
    // Пример создания массива данных
    МассивДанных = Новый Массив();
    МассивДанных.Добавить(1);
    МассивДанных.Добавить(3);
    МассивДанных.Добавить(4);
    МассивДанных.Добавить(5);
    МассивДанных.Добавить(7);
    МассивДанных.Добавить(8);
    МассивДанных.Добавить(9);
    МассивДанных.Добавить(10);
    МассивДанных.Добавить(12);

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

    РазбитьМассивЛинейно(МассивДанных, ТаблицаРезультата);

    // Вывод результата для проверки
    Для Каждого СтрокаТЗ Из ТаблицаРезультата Цикл
        Сообщить(СтрШаблон("Начало: %1, Конец: %2", СтрокаТЗ.НачалоДиапазона, СтрокаТЗ.КонецДиапазона));
    КонецЦикла;
КонецПроцедуры

Преимущества:

1. Простота и понятность: Алгоритм легко читается, понимается и отлаживается.
2. Предсказуемая производительность: Временная сложность составляет O(N), где N — количество элементов в массиве. Каждый элемент массива проверяется только один раз.
3. Эффективное использование памяти: Не требует дополнительных ресурсов стека для рекурсивных вызовов.
4. Кэш-дружественность: Последовательный доступ к элементам массива хорошо согласуется с работой кэша процессора, что может давать прирост скорости на больших массивах.

Недостатки:

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

2. Рекурсивный подход (Метод "разделяй и властвуй")

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

Принцип работы:

1. Проверка непрерывности диапазона: Создается вспомогательная функция ДиапазонНепрерывен. Эта функция определяет, является ли заданный по индексам участок массива непрерывным. Вместо полного перебора всех элементов внутри диапазона, она использует "хак":
   1. Мы получаем значения первого (ПервыйЭлемент) и последнего (ПоследнийЭлемент) элементов из массива по их индексам (ИндексПервогоЭлемента и ИндексПоследнегоЭлемента).
   2. Вычисляем "размер диапазона по значениям": РазмерДиапазона = ПоследнийЭлемент - ПервыйЭлемент.
   3. Вычисляем "размер диапазона по индексам": РазмерДанных = ИндексПоследнегоЭлемента - ИндексПервогоЭлемента.
   4. Если РазмерДанных = РазмерДиапазона, это означает, что каждый элемент в этом диапазоне последовательно увеличивается на 1, и диапазон является непрерывным. Возвращаем Истина.
   5. В противном случае (если РазмерДанных != РазмерДиапазона) диапазон содержит разрывы, и функция возвращает Ложь.
2. Рекурсивное разбиение массива: Основная рекурсивная процедура РазбитьМассив принимает весь массив, начальный и конечный индексы текущего подмассива и таблицу для записи результатов.
   1. Если ДиапазонНепрерывен возвращает Истина, это означает, что текущий участок массива полностью непрерывен. Мы фиксируем его начало и конец в ТаблицаРезультата.
   2. Для оптимизации и объединения смежных диапазонов, алгоритм пытается найти в ТаблицаРезультата уже добавленный диапазон, который заканчивается на один элемент меньше, чем текущий НачалоДиапазона. Если такой диапазон найден, его КонецДиапазона обновляется, чтобы включить текущий диапазон. Если нет, добавляется новая строка.
   3. Если диапазон не непрерывен, он делится пополам (СерединаДиапазона), и рекурсивно вызывается РазбитьМассив для каждой половины: от ПервыйЭлемент до СерединаДиапазона и от СерединаДиапазона + 1 до ПоследнийЭлемент.

Пример реализации на 1С:

&НаСервере
Функция ДиапазонНепрерывен(МассивДанных,ИндексПервогоЭлемента,ИндексПоследнегоЭлемента)
    Если ИндексПервогоЭлемента = ИндексПоследнегоЭлемента Тогда
        Возврат Истина; // Один элемент всегда непрерывен
    КонецЕсли;
    ПервыйЭлемент=МассивДанных[ИндексПервогоЭлемента];
    ПоследнийЭлемент=МассивДанных[ИндексПоследнегоЭлемента];
    РазмерДиапазона=ПоследнийЭлемент-ПервыйЭлемент;
    РазмерДанных=ИндексПоследнегоЭлемента-ИндексПервогоЭлемента;
    Возврат РазмерДанных=РазмерДиапазона;
КонецФункции

&НаСервере
Процедура РазбитьМассив(МассивДанных,ПервыйЭлементИндекс,ПоследнийЭлементИндекс, ТаблицаРезультата)
    Если ПервыйЭлементИндекс > ПоследнийЭлементИндекс Тогда
        Возврат;
    КонецЕсли;

    Если ДиапазонНепрерывен(МассивДанных,ПервыйЭлементИндекс,ПоследнийЭлементИндекс) Тогда
        НачалоДиапазона=МассивДанных[ПервыйЭлементИндекс];
        КонецДиапазона=МассивДанных[ПоследнийЭлементИндекс];
        
        // Попробуем объединить диапазон с предыдущим
        // ВАЖНО: для корректного поиска "КонецДиапазона-1" необходимо, 
        // чтобы ТаблицаРезультата была отсортирована по "КонецДиапазона"
        // или использовать другую стратегию объединения.
        // Индекс по "КонецДиапазона" ускоряет поиск.
        СтрокаТаблицы = ТаблицаРезультата.Найти(НачалоДиапазона-1,"КонецДиапазона");
        Если СтрокаТаблицы = Неопределено Тогда
            СтрокаТаблицы = ТаблицаРезультата.Добавить();
            СтрокаТаблицы.НачалоДиапазона = НачалоДиапазона;
        КонецЕсли;
        СтрокаТаблицы.КонецДиапазона = КонецДиапазона;
        Возврат;
    КонецЕсли;

    // Если диапазон не непрерывен, делим его пополам
    СерединаИндекса = Цел((ПоследнийЭлементИндекс-ПервыйЭлементИндекс)/2)+ПервыйЭлементИндекс;
    РазбитьМассив(МассивДанных,ПервыйЭлементИндекс,СерединаИндекса, ТаблицаРезультата);
    РазбитьМассив(МассивДанных,СерединаИндекса+1,ПоследнийЭлементИндекс, ТаблицаРезультата);    
КонецПроцедуры

&НаСервере
Процедура КомандаНаСервереРекурсивно()
    // Пример создания массива данных
    МассивДанных = Новый Массив();
    МассивДанных.Добавить(1);
    МассивДанных.Добавить(3);
    МассивДанных.Добавить(4);
    МассивДанных.Добавить(5);
    МассивДанных.Добавить(7);
    МассивДанных.Добавить(8);
    МассивДанных.Добавить(9);
    МассивДанных.Добавить(10);
    МассивДанных.Добавить(12);

    ТаблицаРезультата = Новый ТаблицаЗначений;
    ТаблицаРезультата.Колонки.Добавить("НачалоДиапазона");
    ТаблицаРезультата.Колонки.Добавить("КонецДиапазона");
    ТаблицаРезультата.Индексы.Добавить("КонецДиапазона"); // Для ускорения поиска в Найти()

    РазбитьМассив(МассивДанных,0,МассивДанных.Количество()-1,ТаблицаРезультата);

    // Для проверки корректности объединения, если диапазоны не отсортированы при добавлении
    // то их нужно будет отсортировать или переобъединить после всех рекурсивных вызовов
    ТаблицаРезультата.Сортировать("НачалоДиапазона Возр");

    // Вывод результата для проверки
    Для Каждого СтрокаТЗ Из ТаблицаРезультата Цикл
        Сообщить(СтрШаблон("Начало: %1, Конец: %2", СтрокаТЗ.НачалоДиапазона, СтрокаТЗ.КонецДиапазона));
    КонецЦикла;
КонецПроцедуры

Преимущества:

1. Быстрое определение непрерывных блоков: Для массивов, которые в основном непрерывны (то есть содержат очень мало разрывов или вообще их не содержат), данный подход может быть очень быстрым, поскольку он "пропускает" большие непрерывные участки за O(log N) операций для каждого такого участка.
2. Относительно небольшая глубина рекурсии: Для массива в 100 000 элементов максимальная глубина рекурсии составляет всего около 18 уровней, что в большинстве случаев не приводит к переполнению стека.

Недостатки:

1. Накладные расходы рекурсии: Каждый рекурсивный вызов создает новый контекст в стеке вызовов, что может приводить к дополнительным временным и оперативным накладным расходам, особенно в случае большого количества разрывов (когда массив делится многократно).
2. Сложность понимания и отладки: Код рекурсивного алгоритма часто менее интуитивен для понимания и отладки по сравнению с линейным проходом.
3. Объединение диапазонов: Механизм объединения диапазонов с помощью ТаблицаРезультата.Найти(НачалоДиапазона-1,"КонецДиапазона") требует поддержания индекса и может быть не самым оптимальным, если Найти выполняется часто.
4. Производительность в худшем случае: Если каждый элемент массива является отдельным диапазоном (например, 1, 3, 5, 7), алгоритм будет делить массив до уровня отдельных элементов, что приведет к производительности, сравнимой с линейным проходом, но с дополнительными накладными расходами рекурсии.

3. SQL-подход

Если ваши числовые данные уже хранятся в базе данных или могут быть легко переданы туда (например, через временную таблицу), для решения задачи разбиения на диапазоны можно эффективно использовать SQL-запросы. Этот подход особенно мощный для очень больших объемов данных, поскольку позволяет использовать оптимизации СУБД для сортировки и обработки.

Принцип работы:

1. Подготовка данных: Мы помещаем все исходные числа в временную таблицу (например, втЧисла), предварительно отсортированную по возрастанию.
2. Определение правых границ диапазонов: Мы ищем все числа, которые являются "правыми границами" непрерывных диапазонов. Правая граница — это число, для которого в массиве нет следующего по порядку числа (текущее_число + 1). Для этого мы используем ЛЕВОЕ СОЕДИНЕНИЕ таблицы втЧисла саму с собой, ищем элементы втЧислаСлева.ТекЧисло + 1 = втЧислаСправа.ТекЧисло. Если для какого-то втЧислаСлева.ТекЧисло не находится соответствующего втЧислаСправа.ТекЧисло (то есть втЧислаСправа.ТекЧисло ЕСТЬ NULL), это значит, что втЧислаСлева.ТекЧисло является правой границей диапазона. Результаты помещаются во временную таблицу втГраницы.
3. Определение левых границ и группировка: После того как у нас есть все правые границы, мы можем определить левые границы и сгруппировать диапазоны. Для каждого числа из исходного массива (втЧисла.ТекЧисло) мы ищем минимальную правую границу из втГраницы.ТекЧислоСлева, которая больше или равна этому числу. Эта минимальная правая граница будет "правым ограничителем" для всех чисел в текущем диапазоне. Затем мы группируем данные по этим правым ограничителям и находим минимальное число (МИНИМУМ(втДляСвертки.ТекЧисло)), которое будет являться левой границей диапазона.

Пример реализации SQL-запроса:

Предполагается, что у нас есть временная таблица втЧисла с одной колонкой ТекЧисло, содержащая исходный отсортированный массив.

// Шаг 1: Создаем временную таблицу втГраницы для хранения правых границ диапазонов
ВЫБРАТЬ втЧислаСлева.ТекЧисло КАК ТекЧислоСлева
ПОМЕСТИТЬ втГраницы
ИЗ втЧисла КАК втЧислаСлева
    ЛЕВОЕ СОЕДИНЕНИЕ втЧисла КАК втЧислаСправа
    ПО (втЧислаСлева.ТекЧисло + 1 = втЧислаСправа.ТекЧисло)
ГДЕ втЧислаСправа.ТекЧисло ЕСТЬ NULL
;
////////////////////////////////////////////////////////////////////////////////
// Шаг 2: Определяем левые и правые границы итоговых диапазонов
ВЫБРАТЬ
    МИНИМУМ(втДляСвертки.ТекЧисло) КАК НачалоДиапазона,
    втДляСвертки.ТекЧислоСлева КАК КонецДиапазона
ИЗ    (ВЫБРАТЬ втЧисла.ТекЧисло, МИНИМУМ(втГраницы.ТекЧислоСлева) КАК ТекЧислоСлева
    ИЗ втЧисла КАК втЧисла
    ВНУТРЕННЕЕ СОЕДИНЕНИЕ втГраницы КАК втГраницы ПО втЧисла.ТекЧисло <= втГраницы.ТекЧислоСлева
    СГРУППИРОВАТЬ ПО втЧисла.ТекЧисло) КАК втДляСвертки
СГРУППИРОВАТЬ ПО втДляСвертки.ТекЧислоСлева
УПОРЯДОЧИТЬ ПО НачалоДиапазона

Преимущества:

1. Высокая производительность для данных в СУБД: Если данные уже находятся в базе данных, SQL-запрос может быть очень быстрым, так как использует встроенные оптимизации СУБД, индексы и параллельную обработку.
2. Компактность кода: Решение может быть выражено довольно лаконично.
3. Масштабируемость: Подходит для работы с очень большими объемами данных, которые не помещаются в оперативную память приложения.

Недостатки:

1. Требуется передача данных в СУБД: Если исходный массив находится в памяти 1С, его необходимо сначала передать в базу данных (например, через параметр запроса в виде ТаблицаЗначений), что само по себе является накладными расходами.
2. Сложность SQL-запроса: Понимание и отладка сложных SQL-запросов, особенно с оконными функциями или множественными соединениями, может быть сложнее для некоторых разработчиков.
3. Зависимость от СУБД: Производительность и синтаксис могут немного различаться в разных СУБД.

Общие рекомендации и сравнение подходов

Выбор оптимального алгоритма зависит от нескольких факторов:

1. Объем массива: Для небольших массивов (до нескольких тысяч элементов) разница в производительности между подходами будет незначительной, и можно выбирать наиболее читаемый код.
2. Плотность массива:
   • Если массив почти всегда непрерывен с очень редкими разрывами, рекурсивный подход может быть теоретически быстрее за счет быстрого "пропуска" больших непрерывных участков.
   • Если массив содержит много разрывов или полностью состоит из отдельных элементов, линейный проход будет более эффективным и предсказуемым из-за меньших накладных расходов.
3. Расположение данных:
   • Если данные уже находятся в базе данных, SQL-подход является очень мощным и рекомендованным.
   • Если данные находятся в памяти приложения 1С, предпочтительнее использовать один из программных подходов (итеративный или рекурсивный).
4. Читаемость и поддерживаемость кода: В большинстве практических задач простота и легкость понимания кода являются ключевыми факторами. Линейный итеративный алгоритм обычно выигрывает по этому параметру.
5. Ограничения среды: В 1С важно учитывать накладные расходы на рекурсию и глубину стека, хотя для типичных задач с "многотысячными" массивами (например, до 100 000 элементов) глубина рекурсии будет приемлемой.

Заключение:

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

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