В процессе разработки на платформе «1С:Предприятие 8» перед программистом регулярно возникает классическая алгоритмическая задача: определить, пересекаются ли два списка значений. Сценарии могут быть самыми разными — от проверки прав доступа пользователя по списку разрешенных групп до фильтрации товарных позиций в документах по списку исключений. Особую сложность представляет ситуация, когда количество элементов в списках заранее неизвестно: один список может содержать единичные элементы или тысячи позиций, а второй список является относительно небольшим и фиксированным (например, 20–30 элементов).
В этой статье мы подробно проанализируем внутреннее устройство различных коллекций платформы 1С, сопоставим скорость их работы, разберем концепцию временной сложности алгоритмов поиска и выработаем оптимальное решение для нашей задачи.
Для того чтобы выбрать наиболее быстрый инструмент для поиска, нам необходимо разобраться, как работают стандартные коллекции 1С на низком уровне платформы. Производительность поиска в любой коллекции зависит от используемой структуры данных.
Многие начинающие разработчики используют для поиска методы Массив.Найти() или СписокЗначений.НайтиПоЗначению(). Однако важно понимать, что внутри платформы эти методы реализуют обычный последовательный перебор элементов. Если искомый элемент находится в самом конце коллекции или отсутствует вовсе, платформе придется проверить каждый элемент. Временная сложность такого поиска оценивается как линейная — O(N).
На малых объемах данных разница незаметна, но если один из ваших списков разрастется до нескольких тысяч элементов, линейный поиск приведет к критическому падению производительности. Нагрузочные тесты показывают, что на объемах свыше 5 000 элементов линейный поиск начинает кратно проигрывать оптимизированным коллекциям.
Коллекция Соответствие является классической хэш-таблицей. Ключи этой коллекции хэшируются платформой, что позволяет выполнять поиск по ключу за константное время — O(1), независимо от общего количества элементов в коллекции. Это означает, что поиск среди 10 элементов и среди 100 000 элементов в Соответствии займет практически одинаковое, микроскопическое количество времени.
Хотя объект Структура работает так же быстро, как и Соответствие, он имеет жесткое ограничение платформы: ключом структуры может выступать только строка, удовлетворяющая требованиям именования переменных (без пробелов, спецсимволов и не начинающаяся с цифры). Поскольку в нашей задаче элементами списков являются значения ссылочного типа (например, ссылки на справочники СправочникСсылка.Номенклатура или СправочникСсылка.Контрагенты), использовать их в качестве ключей структуры напрямую невозможно. Нам подходит исключительно Соответствие.
Если мы поместим данные в ТаблицаЗначений, добавим колонку и построим по ней индекс с помощью метода ТЗ.Индексы.Добавить(), то поиск методом ТЗ.Найти() будет осуществляться по индексу. Это работает чрезвычайно быстро (близко к O(1)). Однако у этого подхода есть скрытая «ловушка», которую мы разберем ниже.
Проанализируем важнейший нюанс, который часто упускается из виду при проектировании алгоритмов. Нельзя оценивать эффективность решения только по скорости самого поиска. Необходимо учитывать суммарное время выполнения операции, которое складывается из двух составляющих:
Общее время = Время инициализации и заполнения коллекции + Время поиска.
Создание объекта ТаблицаЗначений, добавление в нее колонок, программное заполнение строками, а затем вызов тяжелого платформенного механизма индексации — это ресурсоемкие операции. Если во втором (проверяемом) списке всего 20–30 элементов, накладные расходы на создание индекса в таблице значений полностью перекроют всю выгоду от быстрого поиска. Процесс подготовки коллекции займет больше времени, чем сам поиск по неиндексированному массиву!
Поэтому мы сформулируем ключевое эмпирическое правило для разработчика 1С:
Если суммарное количество элементов во всех коллекциях не превышает 100 единиц, самым быстрым решением будет использование простейших коллекций (массивов) и стандартного перебора в цикле, так как они мгновенно создаются в оперативной памяти.
Существует популярное мнение, что любые операции по обработке данных в 1С эффективнее всего выполнять через запросы. Однако в случае работы с небольшими объемами данных в оперативной памяти это утверждение ошибочно.
Давайте проанализируем, что происходит, когда мы выполняем запрос для сопоставления двух массивов, уже находящихся в памяти:
Все эти шаги создают колоссальные системные задержки (overhead). На малых объемах (десятки или сотни элементов) запрос гарантированно проиграет прямому поиску в оперативной памяти с использованием коллекции Соответствие.
Запрос становится безоговорочным лидером только в двух случаях:
Исходя из условий нашей задачи, мы имеем:
Нам необходимо определить, пересекаются ли они хотя бы по одному элементу. Поскольку Список Б имеет крошечный фиксированный размер, идеальным решением будет использование хэш-таблицы (объекта Соответствие) в качестве фильтра.
Рассмотрим алгоритм по шагам:
Соответствие и заполняем его элементами из Списка Б. В качестве Ключа мы записываем элемент списка (ссылку), а в качестве Значения — булево Истина. Так как элементов всего 20–30, создание и заполнение хэш-таблицы произойдет мгновенно (за доли микросекунды).Для Каждого.Соответствии. Так как поиск по ключу в Соответствии работает со скоростью O(1), эта проверка выполняется мгновенно.Прервать. Нам нет необходимости обходить оставшиеся элементы Списка А, что экономит процессорное время.Давайте посмотрим на практический пример реализации этого алгоритма на языке 1С. Допустим, у нас есть массив целевых складов (Список Б), и нам нужно быстро проверить, содержится ли хотя бы один из них в списке складов к проверке (Список А).
// Предположим, что СписокА и СписокБ - это входящие массивы со ссылками на Справочник.Склады
// Шаг 1: Инициализируем фильтр быстрой хэш-таблицы на основе Списка Б
ФильтрСоответствие = Новый Соответствие;
Для Каждого ЭлементБ Из СписокБ Цикл
ФильтрСоответствие.Вставить(ЭлементБ, Истина);
КонецЦикла;
// Переменная-флаг для фиксации результата проверки
ЕстьПересечение = Ложь;
// Шаг 2: Обходим Список А
Для Каждого ЭлементА Из СписокА Цикл
// Шаг 3: Выполняем сверхбыстрый поиск в Соответствии
Если ФильтрСоответствие[ЭлементА] <> Неопределено Тогда
// Шаг 4: Элемент найден! Устанавливаем флаг и прерываем цикл
ЕстьПересечение = Истина;
Прервать;
КонецЕсли;
КонецЦикла;
Если ЕстьПересечение Тогда
Сообщить("Найдено общее значение между двумя списками!"); Иначе
Сообщить("Списки не пересекаются.");
КонецЕсли;
Проанализируем сильные стороны данного кода. Метод получения значения по ключу ФильтрСоответствие[ЭлементА] вернет Неопределено, если ключ отсутствует в коллекции, и вернет сохраненное значение Истина, если ключ присутствует. Это избавляет нас от написания дополнительных проверок и работает на уровне скомпилированного кода платформы максимально эффективно.
Рассмотрим ситуацию, когда размер Списка Б также может быть велик (например, десятки тысяч элементов). В этом случае заполнение Соответствия вручную в цикле на встроенном языке может стать узким местом из-за низкой скорости выполнения циклов в интерпретируемом коде 1С по сравнению с платформенным кодом C++. Для таких сценариев отлично подойдет использование индексированной ТаблицыЗначений.
Посмотрим, как будет выглядеть реализация этого подхода:
// Создаем Таблицу Значений для индексированного поиска
ТЗ_Фильтр = Новый ТаблицаЗначений;
ТЗ_Фильтр.Колонки.Добавить("Ссылка");
// Быстро заполняем таблицу значениями из Списка Б
// Если СписокБ изначально был Массивом
ТЗ_Фильтр.ЗагрузитьКолонку(СписокБ, "Ссылка");
// Строим индекс по колонке поиска
ТЗ_Фильтр.Индексы.Добавить("Ссылка");
ЕстьПересечение = Ложь;
// Обходим первый список и ищем совпадения в индексированной ТЗ
Для Каждого ЭлементА Из СписокА Цикл
// Метод Найти() по индексированному полю работает чрезвычайно быстро
Если ТЗ_Фильтр.Найти(ЭлементА, "Ссылка") <> Неопределено Тогда
ЕстьПересечение = Истина;
Прервать;
КонецЕсли;
КонецЦикла;
Метод ЗагрузитьКолонку() работает на уровне платформенного кода С++ без использования циклов встроенного языка 1С, что обеспечивает моментальное наполнение таблицы значений даже при наличии сотен тысяч строк. Последующее индексирование подготавливает структуру для быстрого поиска.
Для того чтобы всегда безошибочно выбирать архитектурное решение под конкретные условия задачи, проанализируем следующую сводную таблицу рекомендаций:
Массив.Найти().Соответствие в качестве фильтра для малого списка + цикл по большому списку.ТаблицаЗначений или Соответствие.В или внутреннее соединение ВНУТРЕННЕЕ СОЕДИНЕНИЕ).Применяя данные подходы в своей ежедневной практике разработки, мы гарантируем стабильную и быструю работу прикладных решений 1С даже при неконтролируемом росте объемов обрабатываемых данных.