Реализация метода НайтиСтроки для ДанныеФормыДерево

Как известно, у объекта ДанныеФормыДерево и ДанныеФормыКоллекцияЭлементовДерева нет метода быстрого поиска. Для обычных «прямых» коллекций, являющихся отображениями таблиц значений, есть хотя бы метод НайтиСтроки, а для деревьев и этого нет. Что порой бывает неудобно, т.к. вынуждает извращаться. Извращений обычно два — либо данные формы кидаются на сервер, там превращаются в ДеревоЗначений, где поиск по вложенности есть, либо обходятся тупым перебором с рекурсией. Оба способа не очень быстрые и весьма ресурсозатратные, если дерево достаточно большое, т.е. и в высоту, и по ширине (по количеству веток на каждом уровне). Всякие фокусы с xml ещё медленнее, поэтому их не рассматриваем.

Итак, наша задача — реализовать функционал, аналогичный НайтиСтроки, т.е. функцию, получающую на вход указание конкретной коллекции (на форме их может быть несколько) и структуру отбора, где ключи — имена реквизитов коллекции, а значения — поисковые значения любого сериализуемого типа. На выходе должен получиться либо пустой массив, если ничего не найдено, либо массив объектов ДанныеФормыЭлементДерева, т.е. ветки дерева. Понятно, что поиск по значениям типа вложенных коллекций, двоичных данных и всяких там картинок мы не рассматриваем.

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

Рассмотрим общий случай неупорядоченного дерева, с произвольной высотой, с разным количеством узлов/рёбер (шириной) на каждом уровне и с возможно повторяющимися значениями в каждом узле. По условиям задачи, нужны ветви (узлы). Казалось бы, каждую ветку однозначно характеризует идентификатор, уникальное числовое значение, по возрастанию присваиваемое в момент программного или ручного заполнения дерева, и удобный метод НайтиПоИдентификатору позволяет оперировать ветками, но, как показывает опыт, после ряда манипуляций (например, выгрузки в дерево и обратной загрузки БЕЗ изменения состава) эти идентификаторы «сбрасываются», что сводит их полезность как ключей на нет. Будем оперировать собственно ветками, как внутренними указателями на объекты, которые существуют в контексте формы, пока форма работает. Заметим, что при различных клиент-серверных манипуляциях с формой эти указатели не портятся (выражаясь иначе, это ByRefernce, а не ByValue). В принципе, если у вас пертурбаций с деревом и формой не происходит, или если фирма 1С допилит этот момент, то можно будет оперировать и идентификаторами веток.
Теперь, каждой ветке надо сопоставить ключ, уникальный в пределах сочетания значений всех разыскиваемых полей. Так, все ветки с одинаковым набором значений разыскиваемых полей должны получить одинаковые ключи. В общем случае разыскиваемых полей несколько (хоть все реквизиты коллекции), в частном — всего один.

Остановимся подробнее на реализации поиска. Самым быстрым общим объектом для поиска является Соответствие. Оно кэшируется, оно не особенно медленно заполняется и чрезвычайно быстро возвращает значения по произвольным ключам. Замечу, кстати, что соответствие прекрасно позволяет в качестве ключа запихнуть другую коллекцию — структуру или массив, но получить по такому ключу значение не удастся, т.к. 1С пытается получать по внутренним ссылкам. Итак, соответствие. Будем хранить в ключах соответствия уникальные указания на сочетания значений разыскиваемых полей, а в значениях соответствия — массивы веток как ДанныеФормыЭлементДерева.

Для поиска по одному реквизиту можно упростить задачу, и хранить в соответствии значение, в т.ч. пустое, любого допустимого типа. Для нескольких надо использовать составной ключ, а им может быть строка. Эта строка составляется из сериализованных значений разыскиваемых полей через разделитель. Можно применять разные способы (от Строка(знч.УникальныйИдентификатор()) до XDTO). Важно запомнить порядок, в котором сериализованные значения полей расположены в ключе, т.к. НайтиСтроки на вход принимает структуру, где поля поиска и их значения могут быть перечислены в любом порядке.

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

Собственно поиск прост — по переданной поисковой структуре строится ключ (либо сразу берётся одиночное значение, если поле поиска одно), и по этому ключу из соответствия получается массив веток, т.е. объектов ДанныеФормыЭлементДерева.

Применённый метод непривередлив к удалению из дерева. Но, конечно, при любом изменении значения имеющихся веток или при добавлении новых веток на любых уровнях, необходима переиндексация. Как и когда организовать это — вопрос, решаемый разработчиком в рамках конкретной задачи.

Теперь самое интересное, производительность. Сразу оговорюсь, мне было некогда делать полномасштабные тесты, поэтому разок-другой погонял, замерил и успокоился. Поскольку работаем только на клиенте, то наличие и качество сервера роли не играют, я вообще делал это на файловой базе. Так вот, согласно замерам производительности, разовая индексация занимает 1.301386, и вызов поиска по 2 полям (одно строковое и одно ссылочное) занимают 0.0016, тогда как рекурсивный обход всех веток, поиск перебором, занял 3.8827 секунды чистого времени. Разница налицо. Разумеется, если дерево часто меняется, то накладные расходы на индексацию выше, но даже однократный поиск уже оправдывает приложенные усилия.

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

// Эту переменную необходимо вставить в модуль
&НаКлиенте
Перем ДанныеДляПоискаВДеревьях;

// Эту область необходимо вставить в модуль
#Область ПоискВДанныхФормыДерево

// Вспомогательная рекурсивная, вызывается из ИндексироватьДерево
&НаКлиенте
Процедура ИндексироватьВетку(рВетка,мИмёнПолей,соотДанных)
Если ТипЗнч(ДанныеДляПоискаВДеревьях)<>Тип("Структура") Тогда
ДанныеДляПоискаВДеревьях=Новый Структура;
КонецЕсли;
//
Если ТипЗнч(рВетка)=Тип("Строка") Тогда
// по имени коллекции получаем её саму
рИмяКоллекции=рВетка;
рВетка=ЭтаФорма[рВетка];
Иначе
рИмяКоллекции="";
КонецЕсли;
//
Если ПустаяСтрока(рИмяКоллекции) и мИмёнПолей.Количество()>1 Тогда
// инициализируем хранение порядка полей в ключе
соотПолей=Новый Соответствие;
Для й=0 По мИмёнПолей.Количество()-1 Цикл
соотПолей.Вставить(мИмёнПолей[й],й);
КонецЦикла;
соотДанных.Вставить("ПоляИндексаПоиска",соотПолей);
КонецЕсли;
//
Для каждого рПодветка Из рВетка.ПолучитьЭлементы() Цикл
ОбработкаПрерыванияПользователя();
Если мИмёнПолей.Количество()=1 Тогда // используем простой ключ
рКлючПолей=рПодветка[мИмёнПолей.Получить(0)];
Иначе // создаём составной ключ
рКлючПолей=""; разд="";
Для каждого рИмяПоля Из мИмёнПолей Цикл
знчПоля=рПодветка[рИмяПоля];
рКлючПолей=рКлючПолей+разд+СериализаторXDTO.XMLСтрока(знчПоля); разд="#";
КонецЦикла;
КонецЕсли;
// добавляем текущую ветку к имеющимся
рИмеющееся=соотДанных.Получить(рКлючПолей);
Если рИмеющееся=Неопределено Тогда рИмеющееся=Новый Массив КонецЕсли;
рИмеющееся.Добавить(рПодветка);
соотДанных.Вставить(рКлючПолей,рИмеющееся);
// идём глубже
ИндексироватьВетку(рПодветка,мИмёнПолей,соотДанных);
КонецЦикла;
//
// помещаем в общее хранение
Если не ПустаяСтрока(рИмяКоллекции) Тогда
ДанныеДляПоискаВДеревьях.Вставить(рИмяКоллекции,соотДанных);
КонецЕсли;
КонецПроцедуры

// Пример вызова индексации (надо вызывать при добавлении новых веток)
&НаКлиенте
Процедура ИндексироватьДерево(Команда)
соотИ=Новый Соответствие;
мИмёнПолей=Новый Массив;
мИмёнПолей.Добавить("СсылкаНаТовар");
мИмёнПолей.Добавить("НазваниеТовара");
ИндексироватьВетку("дДанных",мИмёнПолей,соотИ); // основная рабочая
ПоказатьПредупреждение(,"Индексация завершена!");
КонецПроцедуры

&НаКлиенте
Функция ПостроитьКлючПолей(рСтруктура,соотПолей)
Если рСтруктура.Количество()=1 Тогда
Для каждого киз Из рСтруктура Цикл рКлючПолей=киз.Значение КонецЦикла;
Иначе
// получаем правильный порядок значений полей в индексе
спПолей=Новый СписокЗначений;
Для каждого киз Из рСтруктура Цикл
спПолей.Добавить(соотПолей.Получить(киз.Ключ),СериализаторXDTO.XMLСтрока(киз.Значение));
КонецЦикла;
спПолей.СортироватьПоЗначению();
рКлючПолей=""; разд="";
Для каждого знч Из спПолей Цикл
рКлючПолей=рКлючПолей+разд+знч.Представление; разд="#";
КонецЦикла;
КонецЕсли;
Возврат рКлючПолей;
КонецФункции

&НаКлиенте
Функция НайтиСтрокиДерева(рИмяКоллекции,отб)
рПустышка=Новый Массив;
Если ТипЗнч(ДанныеДляПоискаВДеревьях)<>Тип("Структура") Тогда Возврат рПустышка КонецЕсли;
соотДанных=Неопределено;
Если не ДанныеДляПоискаВДеревьях.Свойство(рИмяКоллекции,соотДанных) Тогда Возврат рПустышка КонецЕсли;
Если ТипЗнч(соотДанных)<>Тип("Соответствие") Тогда Возврат рПустышка КонецЕсли;
// строим ключ согласно порядку индексации
Если отб.Количество()>1 Тогда
соотПолей=соотДанных.Получить("ПоляИндексаПоиска");
Если ТипЗнч(соотДанных)<>Тип("Соответствие") Тогда Возврат рПустышка КонецЕсли;
Иначе
соотПолей=Неопределено;
КонецЕсли;
рКлючПолей=ПостроитьКлючПолей(отб,соотПолей);
Если ПустаяСтрока(рКлючПолей) Тогда Возврат рПустышка КонецЕсли;
// собственно ищем
Возврат соотДанных.Получить(рКлючПолей);
КонецФункции

#КонецОбласти

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

В приложенной обработке — пример, на котором, в т.ч., проводилось тестирование. Для теста строилась простейшая выборка по номенклатуре и повторялась согласно переменным-ограничителям. Дерево получилось равновесное, но это не играет особенной роли.

P.S. И всё-таки странно: почему разработчики платформы не реализовали такой поиск сами?..

В