При разработке алгоритмов сопоставления данных часто возникает задача: имеется одна эталонная таблица значений и массив других таблиц аналогичной структуры. Требуется найти среди них ту, которая на 100% совпадает с образцом по составу и значениям строк. Если таблицы содержат тысячи строк и десятки колонок, прямое построчное сравнение «в лоб» через двойные циклы приводит к критическому падению производительности. Разберем по шагам, как выстроить быстрый и надежный алгоритм поиска совпадений в среде 1С:Предприятие.
Прежде чем запускать ресурсоемкие алгоритмы точного поэлементного сравнения, необходимо максимально сократить число проверяемых таблиц-кандидатов. Для этого используем быстродействующие платформенные проверки, выполняемые в оперативной памяти сервера без обхода строк вручную.
Рассмотрим порядок предварительного отсева:
ТЗ_Эталон.Количество() <> ТЗ_Кандидат.Количество()), таблица сразу отбрасывается.Итог() реализован на уровне скомпилированного ядра платформы и мгновенно вычисляет сумму значений по колонке. Несовпадение итогов хотя бы по одной числовой колонке гарантирует различие таблиц.Колонки.Количество()) и их типов через объект ОписаниеТипов.Посмотрим на пример функции предварительной валидации:
Функция ТаблицыПрошлиБыстрыйФильтр(ТЗ_Эталон, ТЗ_Кандидат, ИменаЧисловыхКолонок)
Если ТЗ_Эталон.Количество() <> ТЗ_Кандидат.Количество() Тогда
Возврат Ложь;
КонецЕсли;
Если ТЗ_Эталон.Колонки.Количество() <> ТЗ_Кандидат.Колонки.Количество() Тогда
Возврат Ложь;
КонецЕсли;
Для Каждого ИмяКолонки Из ИменаЧисловыхКолонок Цикл
Если ТЗ_Эталон.Итог(ИмяКолонки) <> ТЗ_Кандидат.Итог(ИмяКолонки) Тогда
Возврат Ложь;
КонецЕсли;
КонецЦикла;
Возврат Истина;
КонецФункции
Нередко разработчики пытаются применить метод ЗначениеВСтрокуВнутр(), рассчитывая превратить всю таблицу в единую строку и сравнить полученные тексты. Выясним причину, почему такой подход приводит к ошибкам:
ЗначениеВСтрокуВнутр() сериализует не только пользовательские данные, но и внутреннюю метаинформацию объекта платформы, включая уникальные идентификаторы (GUID) колонок. Даже если две таблицы абсолютно одинаковы по значениям строк, строковые представления будут отличаться из-за разных идентификаторов колонок.Для таблиц с большим количеством полей и ссылочных типов надежным и наглядным способом является обработка во временных таблицах запроса. Идея заключается в маркировке строк двух таблиц противоположными числовыми коэффициентами (1 и -1) с последующей группировкой по всем анализируемым полям.
Разберем логику метода:
1.-1.ОБЪЕДИНИТЬ ВСЕ и группируются (сворачиваются) по всем значимым колонкам.СУММА(Метка).1 и -1 взаимно уничтожаются и дают 0. Если в итоговом результате запроса появляется хотя бы одна строка с ненулевой суммой, таблицы не равны.Рассмотрим пример кода для реализации этого алгоритма:
Функция ТаблицыИдентичныЧерезЗапрос(ТЗ1, ТЗ2)
// Создаем рабочие копии для добавления служебных полей
ТЗ_А = ТЗ1.Скопировать();
ТЗ_Б = ТЗ2.Скопировать();
ТЗ_А.Колонки.Добавить("Метка", Новый ОписаниеТипов("Число", Новый КвалификаторыЧисла(2, 0)));
ТЗ_Б.Колонки.Добавить("Метка", Новый ОписаниеТипов("Число", Новый КвалификаторыЧисла(2, 0)));
ТЗ_А.ЗаполнитьЗначения(1, "Метка");
ТЗ_Б.ЗаполнитьЗначения(-1, "Метка");
Запрос = Новый Запрос;
МенеджерВТ = Новый МенеджерВременныхТаблиц;
Запрос.МенеджерВременныхТаблиц = МенеджерВТ;
Запрос.УстановитьПараметр("ТЗ_А", ТЗ_А);
Запрос.УстановитьПараметр("ТЗ_Б", ТЗ_Б);
// Формируем текст запроса
Запрос.Текст =
"ВЫБРАТЬ * ПОМЕСТИТЬ ВТ_А ИЗ &ТЗ_А КАК ТЗ_А;
|ВЫБРАТЬ * ПОМЕСТИТЬ ВТ_Б ИЗ &ТЗ_Б КАК ТЗ_Б;
|
|ВЫБРАТЬ
| ВложенныйЗапрос.Номенклатура КАК Номенклатура,
| ВложенныйЗапрос.Количество КАК Количество,
| ВложенныйЗапрос.Цена КАК Цена,
| ВложенныйЗапрос.Сумма КАК Сумма,
| СУММА(ВложенныйЗапрос.Метка) КАК Разница
|ИЗ
| (ВЫБРАТЬ * ИЗ ВТ_А
| ОБЪЕДИНИТЬ ВСЕ
| ВЫБРАТЬ * ИЗ ВТ_Б) КАК ВложенныйЗапрос
|СГРУППИРОВАТЬ ПО
| ВложенныйЗапрос.Номенклатура,
| ВложенныйЗапрос.Количество,
| ВложенныйЗапрос.Цена,
| ВложенныйЗапрос.Сумма
|ИМЕЮЩИЕ
| СУММА(ВложенныйЗапрос.Метка) <> 0";
Результат = Запрос.Выполнить();
Возврат Результат.Пустой();
КонецФункции
Важное ограничение метода: передача больших таблиц в запрос переносит данные из оперативной памяти сервера 1С на сервер СУБД (в базу tempdb для MS SQL или схему pg_temp для PostgreSQL), что может создавать нагрузку на дисковую подсистему и сеть. Кроме того, все колонки таблиц должны иметь строго определенные типы.
Когда таблиц в списке много, а передавать их все в СУБД накладно, оптимальным решением становится вычисление контрольной хеш-суммы для каждой таблицы значений с использованием встроенного объекта ХешированиеДанных.
Проанализируем алгоритм вычисления стабильного хеша:
ХешированиеДанных с алгоритмом ХешФункция.SHA1.УникальныйИдентификатор()) и добавляются в расчет хеша через метод Добавить().ХешСумма сохраняется как цифровой отпечаток таблицы. Для поиска совпадения достаточно сравнить строковые хеши эталона и кандидатов.Посмотрим на программную реализацию хеширования:
Функция ПолучитьХешТаблицыЗначений(ИсходнаяТЗ, СтрокаКолонокДляСортировки)
// Создаем копию, чтобы не нарушать исходный порядок в рабочей таблице
ТЗ = ИсходнаяТЗ.Скопировать();
ТЗ.Сортировать(СтрокаКолонокДляСортировки);
Хеширование = Новый ХешированиеДанных(ХешФункция.SHA1);
КоличествоКолонок = ТЗ.Колонки.Количество();
Для Каждого Стр Из ТЗ Цикл
Для НомерКолонки = 0 По КоличествоКолонок - 1 Цикл
Значение = Стр[НомерКолонки];
// Формируем стабильное строковое представление значения
Если ЗначениеЗаполнено(Значение) Тогда
Если Справочники.ТипВсеСсылки().СодержитТип(ТипЗнч(Значение))
Или Документы.ТипВсеСсылки().СодержитТип(ТипЗнч(Значение)) Тогда
СтрокаДанных = XMLСтрока(Значение);
Иначе
СтрокаДанных = Строка(Значение);
КонецЕсли;
Иначе
СтрокаДанных = "[ПУСТО]";
КонецЕсли;
Хеширование.Добавить(СтрокаДанных);
КонецЦикла;
КонецЦикла;
Возврат Хеширование.ХешСумма;
КонецФункции
Если сортировка огромной таблицы по множеству колонок занимает слишком много времени, можно выполнить сравнение в памяти с использованием структуры типа хеш-таблицы — объекта Соответствие со средней сложностью поиска O(1).
Разберем логику работы:
Соответствие, где значением является счетчик (количество таких же строк в таблице, что важно при наличии дубликатов).Посмотрим на пример кода:
Функция ТаблицыИдентичныБезСортировки(ТЗ_Эталон, ТЗ_Кандидат)
Если ТЗ_Эталон.Количество() <> ТЗ_Кандидат.Количество() Тогда
Возврат Ложь;
КонецЕсли;
КартаСтрок = Новый Соответствие;
Разделитель = Символ(1);
// Заполняем счетчики по эталону
Для Каждого Стр Из ТЗ_Эталон Цикл
КлючСтроки = "";
Для Каждого Колонка Из ТЗ_Эталон.Колонки Цикл
КлючСтроки = КлючСтроки + XMLСтрока(Стр[Колонка.Имя]) + Разделитель;
КонецЦикла;
ТекущийСчетчик = КартаСтрок[КлючСтроки];
Если ТекущийСчетчик = Неопределено Тогда
КартаСтрок.Вставить(КлючСтроки, 1);
Иначе
КартаСтрок.Вставить(КлючСтроки, ТекущийСчетчик + 1);
КонецЕсли;
КонецЦикла;
// Сверяем кандидата
Для Каждого Стр Из ТЗ_Кандидат Цикл
КлючСтроки = "";
Для Каждого Колонка Из ТЗ_Кандидат.Колонки Цикл
КлючСтроки = КлючСтроки + XMLСтрока(Стр[Колонка.Имя]) + Разделитель;
КонецЦикла;
ТекущийСчетчик = КартаСтрок[КлючСтроки];
Если ТекущийСчетчик = Неопределено Или ТекущийСчетчик <= 0 Тогда
Возврат Ложь; // Найдена лишняя или отсутствующая строка
КонецЕсли;
КартаСтрок.Вставить(КлючСтроки, ТекущийСчетчик - 1);
КонецЦикла;
Возврат Истина;
КонецФункции
Для построения наиболее быстрого конвейера поиска эталона среди массива таблиц объединяйте описанные подходы:
Итог().ХешированиеДанных (если порядок строк зафиксирован или сортировка выполняется быстро) либо поточная сверка через Соответствие в памяти (если таблицы не отсортированы).1 и -1, когда требуется переложить группировку на вычислительные мощности СУБД.