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

24.07.16

Разработка - Инструментарий разработчика

Быстро, просто, удобно. Только на клиенте. Для любых деревьев значений на форме. Восполняем пробел платформы.

Скачать файлы

Наименование Файл Версия Размер
ДеревоБылоТакое
.epf 9,29Kb
12
.epf 9,29Kb 12 Скачать

Как известно, у объекта ДанныеФормыДерево и ДанныеФормыКоллекцияЭлементовДерева нет метода быстрого поиска. Для обычных "прямых" коллекций, являющихся отображениями таблиц значений, есть хотя бы метод НайтиСтроки, а для деревьев и этого нет. Что порой бывает неудобно, т.к. вынуждает извращаться. Извращений обычно два - либо данные формы кидаются на сервер, там превращаются в ДеревоЗначений, где поиск по вложенности есть, либо обходятся тупым перебором с рекурсией. Оба способа не очень быстрые и весьма ресурсозатратные, если дерево достаточно большое, т.е. и в высоту, и по ширине (по количеству веток на каждом уровне). Всякие фокусы с 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. И всё-таки странно: почему разработчики платформы не реализовали такой поиск сами?..

В 

Оптимизация НаКлиенте ДанныеФормыДерево дерево значений поиск в дереве быстрый поиск

См. также

Infostart Toolkit: Инструменты разработчика 1С 8.3 на управляемых формах

Инструментарий разработчика Роли и права Запросы СКД Платформа 1С v8.3 Управляемые формы Запросы Система компоновки данных Конфигурации 1cv8 Платные (руб)

Набор инструментов программиста и специалиста 1С для всех конфигураций на управляемых формах. В состав входят инструменты: Консоль запросов, Консоль СКД, Консоль кода, Редактор объекта, Анализ прав доступа, Метаданные, Поиск ссылок, Сравнение объектов, Все функции, Подписки на события и др. Редактор запросов и кода с раскраской и контекстной подсказкой. Доработанный конструктор запросов тонкого клиента. Продукт хорошо оптимизирован и обладает самым широким функционалом среди всех инструментов, представленных на рынке.

13000 руб.

02.09.2020    119908    656    389    

701

Infostart PrintWizard

Пакетная печать Печатные формы Инструментарий разработчика Платформа 1С v8.3 Запросы 1С:Зарплата и кадры бюджетного учреждения 1С:Конвертация данных 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 Платные (руб)

Инструмент, позволяющий абсолютно по-новому взглянуть на процесс разработки печатных форм. Благодаря конструктору можно значительно снизить затраты времени на разработку печатных форм, повысить качество и "прозрачность" разработки, а также навести порядок в многообразии корпоративных печатных форм.

18000 руб.

06.10.2023    7007    20    6    

37

Infostart УДиФ: Управление данными и формами

Инструменты администратора БД Инструментарий разработчика Роли и права Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

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

10000 руб.

10.11.2023    3243    10    1    

31

SALE! 30%

PowerTools

Инструментарий разработчика Инструменты администратора БД Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Россия Платные (руб)

Универсальный инструмент программиста для администрирования конфигураций. Сборник наиболее часто используемых обработок под единым интерфейсом.

3600 2520 руб.

14.01.2013    177340    1070    0    

846

Многопоточность. Универсальный «Менеджер потоков» 2.1

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

Восстановление партий или взаиморасчетов, расчет зарплаты, пакетное формирование документов или отчетов - теперь все это стало доступнее. * Есть желание повысить скорость работы медленных алгоритмов! Но... * Нет времени думать о реализации многопоточности? * о запуске и остановке потоков? * о поддержании потоков в рабочем состоянии? * о передаче данных в потоки и как получить ответ из потока? * об организации последовательности? Тогда ЭТО - то что надо!!!

5000 руб.

07.02.2018    99202    239    97    

296

[ЕХТ] Фреймворк для Расширений 1С

Инструментарий разработчика Платформа 1С v8.3 Управляемые формы Платные (руб)

"Фреймворк для Расширений 1С" это универсальное и многофункциональное решение, упрощающее разработку и поддержку создаваемых Расширений. Поставляется в виде комплекта из нескольких Расширений с открытым исходным кодом. Работает в любых Конфигурациях в режиме Управляемого приложения с режимом совместимости 8.3.12 и выше без необходимости внесения изменений в Конфигурацию.

3000 руб.

27.08.2019    17909    6    8    

38

1С HTML Шаблоны / HTML Templates

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

Быстрая и удобная обработка для работы с шаблонами HTML. Позволяет легко и быстро формировать код HTML.

2040 руб.

27.12.2017    27945    3    10    

14

Выполнение произвольного кода или запроса с параметрами через Web-сервис (замена COM-подключений)

Инструментарий разработчика Обмен между базами 1C Платформа 1С v8.3 Платные (руб)

В процессе работы в 1С часто возникает потребность получить данные из другой базы.  Обычно это делается через COM-соединение, и время выполнения запроса при этом оставляет желать лучшего. В данной публикации представлено универсальное решение, позволяющее практически моментально выполнить произвольный код или запрос с параметрами в другой информационной базе через Web-сервис.

2400 руб.

24.09.2019    23486    15    15    

31
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Steelvan 302 25.07.16 09:12 Сейчас в теме
Открытые ветки сворачиваются ?
2. Yashazz 4707 25.07.16 10:02 Сейчас в теме
(1) Steelvan, не очень понял. Сворачивание - визуальный эффект, а речь о поиске.
3. kapustinag 25.07.16 14:11 Сейчас в теме
Кстати, есть, мне кажется, и другое применение такого индексирования.

Была у меня недавно задача, где визуальное представление было в виде дерева, но было много функций, выполняемых над полями, которые (функции) никак не зависели от иерархической структуры - то есть их можно было бы просто в цикле выполнять, если бы была такая возможность. А вместо этого приходилось рекурсивно дерево обходить.

Думаю, изложенный здесь алгоритм помог бы.
4. Yashazz 4707 25.07.16 16:02 Сейчас в теме
(3) kapustinag, да, возможно. Это для многих действий с "труднообходимой" коллекцией применимо; и не обязательно даже с деревом, кстати.
5. ётун 25.07.16 18:00 Сейчас в теме
За использование буквы "ё" в коде я бы расстреливал через повешенье
6. Yashazz 4707 25.07.16 19:27 Сейчас в теме
(5) ётун, а за использование в ник-неймах?)))
7. ётун 25.07.16 19:32 Сейчас в теме
(6) А за использование в никах и логинах бы поощрял премией.

Не помните вы знаменитую функцию 7.7 "Счётчик", ох не помните...
8. Yashazz 4707 25.07.16 21:41 Сейчас в теме
(7) ётун,
Не помните вы знаменитую функцию 7.7 "Счётчик", ох не помните...
Это я-то не помню? Батенька, я свои первые оригинальные конфы на 7.5 писал, ага.
Оставьте свое сообщение