Достаточно часто встречаются задачи поиска одинаковых элементов справочников и других объектов данных - поиск дублей данных. Обычно критерии поиска достаточно простые - содержат один или несколько полей из "шапки" элемента метаданных. Но иногда условия бывают сложными - выполнить поиск с учетом совпадения полей в табличных частях, например, найти одинаковые ресурсные спецификации, у которых номенклатура в рецептуре совпадает.
Когда данных у нас тысячи или сотни тысяч, то алгоритм поиска в лоб путем перебора будет достаточно длительной операцией. И в этом случае требуется более производительный механизм, особенно, когда хочется искать дубли практически онлайн. Возникает вопрос: "А как можно решить подобную задачу?".
И в этой статье я хочу рассказать об одном таком алгоритме, который использует хеширование данных для поиска в прикладных задачах на языке 1С.
Структура статьи:
- стандартный алгоритм поиска
- алгоритм с использование хеширования
- замечания к алгоритму хеширования
- еще один вариант использования
- заключение
Стандартный алгоритм поиска - простая задача
Сначала рассмотрим простую задачу нахождения одинаковых элементов данных справочников номенклатуры при заведении новой карточки элемента. У нас есть критерий поиска соответствия по равенству артикула, тогда мы можем написать достаточно простой запрос для поиска наличия дублей в алгоритме перед записью:
//...
Запрос = Новый Запрос();
Запрос.Текст = "ВЫБРАТЬ
| Номенклатура.Ссылка КАК Ссылка
|ИЗ
| Справочник.Номенклатура КАК Номенклатура
|ГДЕ
| Номенклатура.Артикул = &Артикул
| И НЕ Номенклатура.ПометкаУдаления";
Запрос.УстановитьПараметр("Артикул",Артикул);
РезультатЗапроса = Запрос.Выполнить();
Отказ = НЕ РезультатЗапроса.Пустой();
//...
Усложненная задача - алгоритм с использованием хеширования (hash функции)
Теперь усложним задачу. Мы хотим при заведении новой ресурсной спецификации проверять, а существуют ли спецификации с подобным составом материалов. Иными словами, если совпадает состав сырья и количество на одну единицу продукции, то скорее всего мы пытаемся создать дубль.
Рис. Пример задачи поиска дублей по справочнику ресурсные спецификации
Теперь при попытке написать запрос, то мы должны будем решить достаточно сложную задачу - мы должны будем сравнить табличную часть без учета порядка строк по равенству сырья и равенству количества. Писать подобный запрос мы не будем, а будем использовать механизм сравнения хешированием.
С одним из примеров использования подобного алгоритма можно ознакомиться, если почитать про работу оператора соединения хешированием - hash_join в различных СУБД.
Для реализации этого алгоритма под задачи нахождения дублей нам потребуется выполнить следующие вещи:
- Добавить новый строковый реквизит и назвать его hash_ключ (не забываем его проиндексировать)
- Создать функцию для вычисления этого ключа перед записью
- При поиске дублей мы получим hash_ключ создаваемого элемента и выполним запрос поиска в таблице спецификаций
Думаю, что с задачей добавления нового реквизита и его индексирования мы справимся без проблем, поэтому опустим этот момент.
Функцию создания ключа при записи элемента можно описать следующим образом:
Процедура ПередЗаписью(Отказ)
// ...
hash_Ключ = ПолучитьHashКлюч(ЭтотОбъект);
// ...
КонецПроцедуры
Функция ПолучитьHashКлюч(Источник,СортировкаСтрок=Истина)
КлючевыеПоляШапки="ОсновноеИзделиеНоменклатура,ОсновноеИзделиеХарактеристика";
КлючевыеПоляТабличнойЧастиМатериалы = "Номенклатура,Характеристика,КоличествоУпаковок";
// 1. Формируем описание объекта поиска
МассивСтруктур = Новый Массив;
// по шапке
ПолучитьМассивСтруктурОбъекта(Источник,МассивСтруктур,СтрРазделить(КлючевыеПоляШапки,","));
// по материалам
МассивЧастей = СтрРазделить(КлючевыеПоляТабличнойЧастиМатериалы,",");
Если СортировкаСтрок=Истина Тогда
ТаблицаТЧ = Источник.МатериалыИУслуги.Выгрузить();
ТаблицаТЧ.Сортировать(КлючевыеПоляТабличнойЧастиМатериалы);
Иначе
ТаблицаТЧ = Источник.МатериалыИУслуги;
КонецЕсли;
Для Каждого стр из ТаблицаТЧ Цикл
ПолучитьМассивСтруктурОбъекта(стр,МассивСтруктур,МассивЧастей);
КонецЦикла;
// 2. Преобразуем в XML
ЗаписьXML = Новый ЗаписьXML;
ЗаписьXML.УстановитьСтроку();
СериализаторXDTO.ЗаписатьXML(ЗаписьXML,МассивСтруктур);
// 3. Формируем хеш
Хешировавние = Новый ХешированиеДанных(ХешФункция.SHA512);
Хешировавние.Добавить(ЗаписьXML.Закрыть());
Возврат Хешировавние.ХешСумма;
КонецФункции
Процедура ПолучитьМассивСтруктурОбъекта(Источник,ТаблицаСравнения,МассивЧастей)
Для каждого рек из МассивЧастей Цикл
ТаблицаСравнения.Добавить(Новый Структура("Реквизит,Значение",рек,Источник[рек]));
КонецЦикла;
КонецПроцедуры
Рассмотрим кратко логику работы алгоритма:
- Сначала мы получаем данные по ключам, которые будем использовать для сравнения. Эти данные сохраняются в массиве структур.
Обратите внимание! Мы используем опцию сортировки строк табличной части, благодаря этому достигается независимость алгоритма от положения строк. - Следующим шагом мы преобразуем полученную таблицу в xml текст
- И от этого текста мы получаем hash значение, которое в дальнейшем используется как ключ сравнения.
Рис. Порядок строк может меняться
Функция проверки на дубли получится такой-же простой, как и вариант выше:
//...
Запрос = Новый Запрос();
Запрос.Текст = "ВЫБРАТЬ
| РС.Ссылка КАК Ссылка
|ИЗ
| Справочник.РесурсныеСпецификации КАК РС
|ГДЕ
| РС.hash_ключ = &hash_ключ
| И НЕ РС.ПометкаУдаления";
Запрос.УстановитьПараметр("hash_ключ",ПолучитьHashКлюч(ЭтотОбъект));
РезультатЗапроса = Запрос.Выполнить();
Отказ = НЕ РезультатЗапроса.Пустой();
//...
В качестве альтернативного варианта использования алгоритма, можно рассмотреть создание обработки по поиску дублей в уже существующих данных (поиск дублей для одного элемента). Ниже приведен снимок экранной формы этой обработки.
Рис. Пример использования алгоритма - обработка сравнения
Замечания к алгоритму
Ограничения применения. Данный алгоритм работает по равенству, иными словами вы можете искать только при условии равно. Если у вас встречаются комбинации с условием "ИЛИ", тогда вам придется бить алгоритм на части. А вот при условии больше или меньше он не умеет работать совсем.
Также обращаю ваше внимание, что алгоритм "жесткий", а не вероятностный, т.е. дает ответ на вопрос соответствия - только да или нет.
Быстродействие. За счет того что новый реквизит проиндексирован и он один, поиск будет работать очень быстро. А вот при использовании типового алгоритма вам потребуется написать достаточно сложный запрос (вероятно пакет запросов) и для вероятной быстрой работы проиндексировать большинство полей при использовании, что не всегда является возможным (особенно если мы не хотим снимать с поддержки типовую конфигурацию) и рациональным (наличие большого количества индексов не только приносит пользу, но и вред) и не всегда помогает.
Коллизии. При использования алгоритма существует небольшая вероятность создания одинакового hash-ключа для двух разных элементов, поэтому после определения потенциальных дублей, рекомендуется провести дополнительную проверку на совпадение данных сопоставлением элементов вручную. Поэтому можно добавить небольшое дополнение - функцию сравнения массивов структур совпавших элементов.
Еще один алгоритм
Рассмотрим еще один алгоритм хеширования, когда выполняется неявное преобразование для разработчика самой платформой 1С. Возможно вы уже догадались что речь идет про один из видов универсальных коллекций значений - Соответствие.
Давайте рассмотрим некоторую простую, но показательную задачу. Пусть нам требуется создать некоторый список с дублями контрагентов. Мы хотим найти контрагентов с одинаковыми ИНН+КПП.
Замечание! Такой алгоритм мы достаточно часто используем при загрузке сырых данных из внешних источников, таких как например Excel.
Алгоритм действий следующий:
- создадим новое соответствие
- загрузим данные в какую-нибудь коллекцию данных, таблицу значений и т.п.
- перебираем в цикле данные и помещаем в соответствие значения, когда ключ у нас получается из требуемого условия
Процедура НайтиДублиКонтрагентовНаСервере()
// 1. Формируем новую коллекцию
ДублиКонтрагентов = Новый Соответствие;
// 2. Получим данные
Запрос = Новый Запрос;
Запрос.Текст = "ВЫБРАТЬ
| Контрагенты.ИНН КАК ИНН,
| Контрагенты.КПП КАК КПП,
| Контрагенты.Ссылка КАК Ссылка
|ИЗ
| Справочник.Контрагенты КАК Контрагенты";
Выборка = Запрос.Выполнить().Выбрать();
// 3. Ищем дубли
Пока Выборка.Следующий() Цикл
Ключ = Выборка.ИНН+"/"+Выборка.КПП;
МассивДублей = ДублиКонтрагентов.Получить(Ключ);
Если МассивДублей=Неопределено Тогда
МассивДублей = Новый Массив();
ДублиКонтрагентов.Вставить(Ключ,МассивДублей);
КонецЕсли;
МассивДублей.Добавить(Выборка.Ссылка);
КонецЦикла;
// 4. Обработка (загружаем в таблицу с колонками - Ключ, Количество и СписокЗначений)
ТаблицаДублейКонтрагентов.Очистить();
Для каждого эл из ДублиКонтрагентов Цикл
стр_н = ТаблицаДублейКонтрагентов.Добавить();
стр_н.Ключ = эл.Ключ;
стр_н.Количество = эл.Значение.Количество();
стр_н.СписокЗначений.ЗагрузитьЗначения(эл.Значение);
КонецЦикла;
КонецПроцедуры
Рис. Пример обработки поиска дублей с помощью универсальной коллекции - соответствие
Заключение
Мы рассмотрели основную идею и подход, практическое использование остается за Вами и зависит от конкретной ситуации. Вариации же рассмотренного алгоритма довольно успешно применяется на практике. Фактически рассмотренный подход достаточно быстрый и простой для реализации, подходит для тех случаев, когда использование альтернативных решений не целесообразно.
