Реально написать хитрый запрос

1. sCHTASS 49 11.10.10 22:35 Сейчас в теме
Есть справочник "Справочник". У элементов справочника есть реквизит "Элемент",
который хранит ссылку на другой элемент этого же справочника. Большая часть
элементов связаны по схеме:
Э1 - Э2 - Э3 - ... - ЭN.

Теперь вопрос. Реально ли запросом 1С определить по отдельно выбранному элементу
ЭК все его связи. Другими словами цепочку
ЭК - ЭК+1 - ЭК+2 - ... ЭМ
необходимо представить как таблицу
ЭК ЭК+1
ЭК ЭК+2
...
ЭК ЭМ
По теме из базы знаний
Ответы
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
103. ildarovich 7850 15.11.10 00:04 Сейчас в теме
(1) Разговор ушел в сторону, однако вот решение, точно соответствующее поставленной задаче:
	Запрос = Новый Запрос("Выбрать КОЛИЧЕСТВО(РАЗЛИЧНЫЕ Справочник.Ссылка) КАК ЧислоВершин ИЗ Справочник.Справочник КАК Справочник");
	
	МаксимальнаяДлинаПути = Запрос.Выполнить().Выгрузить()[0].ЧислоВершин; // можно не вычислять каждый раз, а установить "с запасом"
	
	Запрос.МенеджерВременныхТаблиц = Новый МенеджерВременныхТаблиц;
	
	Пролог = 	   "ВЫБРАТЬ РАЗЛИЧНЫЕ
	               |	Справочник.Ссылка КАК НачалоДуги,
	               |	Справочник.Ссылка КАК КонецДуги
	               |ПОМЕСТИТЬ ЗамыканияДлины1
	               |ИЗ
	               |	Справочник.Справочник КАК Справочник
	               |
	               |ОБЪЕДИНИТЬ
	               |
	               |ВЫБРАТЬ
	               |	Справочник.Ссылка,
	               |	Справочник.Элемент
	               |ИЗ
	               |	Справочник.Справочник КАК Справочник
	               |;
	               |";
				   
	Рефрен =      "ВЫБРАТЬ РАЗЛИЧНЫЕ
	               |	ПерваяДуга.НачалоДуги,
	               |	ВтораяДуга.КонецДуги
	               |ПОМЕСТИТЬ ЗамыканияДлины#2
	               |ИЗ
	               |	ЗамыканияДлины#1 КАК ПерваяДуга
	               |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ЗамыканияДлины#1 КАК ВтораяДуга
	               |		ПО ПерваяДуга.КонецДуги = ВтораяДуга.НачалоДуги
				   |;
				   |УНИЧТОЖИТЬ ЗамыканияДлины#1 
	               |;
	               |";
				   
				   
	Эпилог =      "ВЫБРАТЬ
	               |	Дуга.КонецДуги КАК Элемент
	               |ИЗ
	               |	ЗамыканияДлины#2 КАК Дуга
	               |ГДЕ
	               |	Дуга.НачалоДуги = &Ссылка";
				   
	Запрос.Текст = Пролог;
	
	МаксимальнаяДлинаЗамыканий = 1;
	
	Пока МаксимальнаяДлинаЗамыканий < МаксимальнаяДлинаПути Цикл
		
		Запрос.Текст = Запрос.Текст + СтрЗаменить(СтрЗаменить(Рефрен, "#1", Строка(МаксимальнаяДлинаЗамыканий)), "#2", Строка(2 * МаксимальнаяДлинаЗамыканий));
		
		МаксимальнаяДлинаЗамыканий = 2 * МаксимальнаяДлинаЗамыканий
		
	КонецЦикла;
	
	Запрос.Текст = Запрос.Текст + СтрЗаменить(Эпилог, "#2", Строка(МаксимальнаяДлинаЗамыканий)); 
	
	Запрос.УстановитьПараметр("Ссылка", Элемент);
	
	Результат = Запрос.Выполнить().Выгрузить();
Показать

Решение основано на теории графов, а конкретно - методе построения транзитивного замыкания ориентированного графа.
Прилагается тестовая конфигурация, в которой можно быстро сформировать тестовый справочник и проверить работу запроса и скриншот работы конфигурации.
Более подробное описание - в справке к отчету конфигурации.
Метод универсальный, работает на любых ориентированных графах с минимальной коррекцией пролога запроса.
Может применяться и для решения частной задачи разузлования.
Прикрепленные файлы:
walp; awk; IvanGorbunov; +3 Ответить
104. hogik 443 15.11.10 01:35 Сейчас в теме
(103)
"вот решение, точно соответствующее поставленной задаче"(с)
Точная постановка задачи - "...запросом".
Одним запросом. ;-)
Сколько запросов выполняется в Вашем алгоритме?
105. Ish_2 1104 15.11.10 02:10 Сейчас в теме
(103)
Давайте разбираться :
В справочнике имеем первые две записи :
Эл1 - Эл2
Эл2 - ПустоеЗначениеСправочника
...
И далее миллион каких -то пар, не содержащих Эл1 и Эл2.


Мы установили "МаксимальнаяДлинаПути" равную допустим 20 (как это Вы пишите с "запасом"). Интересующий нас элемент - Эл1 .

Пожалуйста, опишите сколько запросов будет сделано к базе , и как будут выглядеть в каждом последовательно выполненном запросе (Рефрен) записи касающиеся Эл1.
110. ildarovich 7850 15.11.10 10:03 Сейчас в теме
(105) Рефрен будет выполняться 5 раз (2 х 2 х 2 х 2 х 2 > 20).
После добавления к записи Э1 -> Э2 записей Э1 -> Э1 и Э2 -> Э2 (всего их станет три), в этой части таблицы ничего меняться не должно.

Я не рассчитывал на пустую ссылку у элемента в данной задаче.
Поэтому записей вида Э2 -> "Пусто" в таблице при решении этой задачи, по-моему, быть не должно.
Но для контроля в "прологе" пакетного запроса, наверное, необходимо задать соответствующее условие.
106. hogik 443 15.11.10 02:44 Сейчас в теме
(103)
Сергей.
Извините.
Я снимаю свой вопрос о количестве запросов.
Если количество запросов считать по количеству "Запрос.Выполнить()", то Ваше решение укладывается в постановку задачи. Естественно, с допуском "можно не вычислять каждый раз"(с). Однако, есть ли у Вас оценка эффективности такого решения в части выполнения самих "ВЫБРАТЬ" в этом одном запросе?
107. ildarovich 7850 15.11.10 09:35 Сейчас в теме
(106) Наихудший случай - когда все вершины связаны одним циклом.
Пусть вершин N.
Всего в пакетном запросе будет 1 +( log(N) + 1) + 1 запросов.
Самый "тяжелый запрос" - последний запрос в "рефрене".
В нем соединяются две временные таблицы размером N x (N - 1). По методу циклов
получаем оценку этого запроса O(N x (N - 1) x N x (N - 1)).
Наилучший случай - когда вершины вообще не связаны.
Тогда та же оценка улучшиться до O(N x 1 x N x 1).
Об эффективности говорить не приходится :cry: .
Некоторым утешением служит то, что получаемое замыкание содержит информацию о связях всех элементов, то есть одновременно решается в N раз более сложная задача.

Естественно, выгрузив в оперативную память информацию о связях графа и обработав ее, скажем, в таблице значений (с рекурсией или без), получим существенно более быстрое решение.

Плюс решения через запрос - его "декларативность", ну и определенная "красота".
К посту (103) я прикреплял конфигурацию для тестирования метода, сделаю это еще раз, там я поправил несколько строк, чтобы обрабатывать графы побольше.

... все же не получается это сделать, если есть интерес, подскажите, как сюда выложить конфигурацию ...
109. Ish_2 1104 15.11.10 10:00 Сейчас в теме
(107)
Об эффективности говорить не приходится


Я тоже плачу. "Красота" и "декларативность" - это для прикола.
Я уже писал Арчибальду - важнейшая характеристика алгоритма для графа - его эффективность. В интернете таких алгоритмов - "тьмы и тьмы и тьмы".
Эффективность Вашего алгоритма вызывает , как я вижу , наши взаимные рыдания.
Поэтому и справедливо рассматривать пост (103) как забавный прикол. И не более того.
111. Арчибальд 2706 15.11.10 10:22 Сейчас в теме
(109) А вот имени Арчибальдова не следует упоминать всуе :!:
112. Ish_2 1104 15.11.10 10:23 Сейчас в теме
(111) Виноват !
Строку "Я уже писал Арчибальду.." читать "Я уже писал одному взрослому мужчине.." .
Так , вроде не придерешься - имени не указано.
114. ildarovich 7850 15.11.10 21:49 Сейчас в теме
(109) Ну, какой вопрос, такой и ответ.
Действительно, "прикольно" решать подобные задачи средствами СУБД, в принципе,
для этого не предназначенными.
Сохраняя результаты промежуточных вычислений на диске, невозможно соревноваться с алгоритмами, работающими в памяти.
Предложенная задача, например, решается для графа в миллион узлов за 16 секунд при помощи простейшей программки из 15-ти строк, использующей таблицу значений "Дуги"
Запрос = Новый Запрос("Выбрать * ИЗ Справочник.Справочник");
Дуги = Запрос.Выполнить().Выгрузить();
Дуги.Индексы.Добавить("Ссылка");
Результат = Новый СписокЗначений;
Результат.Добавить(Элемент);
Указатель = 0;
Пока Указатель < Результат.Количество() Цикл
	Для Каждого Дуга Из Дуги.НайтиСтроки(Новый Структура("Ссылка", Результат[Указатель].Значение)) Цикл
		Если Результат.НайтиПоЗначению(Дуга.Элемент) = Неопределено Тогда
			Результат.Добавить(Дуга.Элемент)
		КонецЕсли
	КонецЦикла;
	Указатель = Указатель + 1
КонецЦикла;
Результат.ВыбратьЭлемент()
Показать

При этом большая часть времени - это не обработка, а получение исходных данных из БД!
115. hogik 443 15.11.10 22:44 Сейчас в теме
(114)
Сергей.
1) Спасибо Вам за оценку эффективности алгоритма из #103.
2) Для алгоритма из #114. Если использовать СУБД, которая немного предназначена для решение подобных задач, то можно время чтения приравнять нулю. На моей тестовой платформе исходные данные считываются в память - около секунды.
116. Ish_2 1104 15.11.10 22:49 Сейчас в теме
(114) А для задачи разузлования в (79) аналогично через таблицу значений сможете ?
Только в (79) я ошибся: не семь десятков номенклатур . а шесть десятков.
И подчеркиваю, контроль на зацикленность обязателен.
Очень интересно при Вашем подходе (всё в оперативной памяти) - сколько времени это займет ?
117. Арчибальд 2706 16.11.10 08:45 Сейчас в теме
118. Ish_2 1104 16.11.10 08:58 Сейчас в теме
(117) Лучше в своей теме "Графин...". Буду пугать.
Через таблицу значений в 77 это сделать сложнее.
У вас отсутствует команда НайтиСтроки , выбирающая по фильтру нужные строки из таблицы значений.
Ну, раз взялся , то помни :
- контроль зацикленности каждой ветки обязателен.

1. 4 мин - не о чем говорить
2. 3 мин - очень плохо
3. 2 мин - просто плохо
4. 1.5 мин - посредственно
5. 1 мин - хорошо
6. 40 сек - отлично
7. 20 сек - Арчибальд - СУПЕРСТАР на все времена !
( в укзанное время входит копирование элементов из справочника в таблицу значений)
125. hogik 443 18.11.10 05:37 Сейчас в теме
(118)
Игорь.
К вопросу о времени выполнения данной задачи за 20 секунд.
Время выполнения вот такого цикла в "1С 7.7":
Т=_GetPerformanceCounter();
Для Н=1 По 1000000 Цикл
А=2*2;
КонецЦикла;
Сообщить(_GetPerformanceCounter()-Т);
На моём компьютере 1.431 сек.
Ну может хватит пугать людей абсолютными величинами? :evil:
А в этой задаче, кроме подсчета количества на нижнем уровне, еще надо много чего делать...
128. Ish_2 1104 18.11.10 06:55 Сейчас в теме
(125) Отличная мысль.
Я сообщу вам свое время для этого теста.
А также время исполнения запроса на сервере "select sum(a*a) from table" , где table имеет поле "а" и 1 000 000 записей
130. Ish_2 1104 18.11.10 09:02 Сейчас в теме
(125) К вопросу о том , "зачем пугать людей абсолютными величинами ?"
Давая абсолютные числа , я, конечно, рискую . Но так интереснее.

Пугать людей нужно затем , чтобы в процессе написания простейшего алгоритма люди задумались над тем : что они делают ? туда ли они попали ?
Независимо от техники на которой они работают, с рекурсией они проиграют многократно, кто-то в 20 раз , кто -то в 10 раз , кто-то в 3 раза.
Вы мне дали - 140 сек , как время которое невозможно превзойти на Вашем компьютере. Было бы смешно , если бы я Вам дал 120 сек.
Согласитесь , можно оспорить (техника там ... диски.. память... процессор).
Очень спорно , даже 70 сек - всякое бывает.
Приводя число 20 сек - я намекаю , что дело в другом принципиальном подходе.
99.9% времени обработки у меня осуществляется на сервере.
Пусть у тестировщика плохонький ,7 летней давности сервер и MSSQL 2000 , ну что ж , тогда 60 сек, а чем черт не шутит - даже 90 сек. Но это существенно выше чем 140 сек.
131. Ish_2 1104 18.11.10 09:19 Сейчас в теме
(125) Отвечаю "зеркально":
Время выполнения вот такого цикла в "1С 7.7":
Т=_GetPerformanceCounter();
Для Н=1 По 1000000 Цикл
А=2*2;
КонецЦикла;
Сообщить(_GetPerformanceCounter()-Т);
На моём компьютере 1.125 сек.

Теперь другой тест уже 1сv8 ("клиент-серверный" вариант) :
	Скрипт = Новый COMОбъект("MSScriptControl.ScriptControl");
	Скрипт.language = "javascript";
	мСек1 = Формат(Скрипт.eval("new Date().getTime()"),"ЧГ=0");
	
	Запрос = Новый Запрос;
	Запрос.МенеджерВременныхТаблиц = Новый МенеджерВременныхТаблиц;
	Запрос.Текст = "ВЫБРАТЬ ПЕРВЫЕ 1000000
	               |	Сумма(Спец.Количество*Спец.Количество) КАК Количество
	               |ПОМЕСТИТЬ Врем
	               |ИЗ
	               |	Справочник.СпецификацииНоменклатуры.ИсходныеКомплектующие КАК Спец ";
	Результат = Запрос.Выполнить();			   
	
	мСек2 = Формат(Скрипт.eval("new Date().getTime()"),"ЧГ=0");
	Если мСек2 - мСек1 <> 0 Тогда
		Сообщить("Завершено за " + ((мСек2 - мСек1) / 1000) + " сек.");
	КонецЕсли; 
Показать


Время выполнения 0.151 сек

Итак , сложение миллиона квадратов на сервере выпоняется почти в 7 раз быстрее ,
чем код на 77. Какой же вывод ,Владимир ?
138. hogik 443 18.11.10 21:10 Сейчас в теме
(131)
"На моём компьютере 1.125 сек."(с)
"Время выполнения 0.151 сек"(с)
"Какой же вывод ,Владимир ?"(с)
Игорь.
Ваш вопрос - это шутка?!
Вас, действительно "удивляют" эти времена?
Отвечу на всякий случай. :-(
Вывод, что системы разные (железо) и разное "качество" перевода операторов среды программирования в "машинные" команды.
(137)
"а если мы обошли все узлы графа, то зачем нам еще какие-то построения"(с)
Игорь & Сергей.
Совершенно верно. Если "приземлиться" от высшей математики (включая реляционную модель СУБД) на реальную "землю" - арифметику.
Для решения задачи, в постановки от Игоря. Требуется при любом алгоритме "пощупать" каждый узел дерева. И важно сделать это один раз не порождая никаких "временных" структур содержащих "подмножество" информации, т.к. это всегда не только чтение, но и "запись".
В этой постановке единственный алгоритм - это последовательный обход дерева с запоминанием в стеке вершин маршрута (для проверки цикла и подсчета количеств изделий). Никакого другого способа не существует! Этот обход можно делать рекурсией или циклом "моделирования" рекурсии. Выбор зависит от среды программирования. Оптимизировать можно только время получения узла дерева. Например, если моделировать иерархическую систему на реляционной, то для получения каждого узла приходится "проходить" по дереву индекса таблицы БД. Этот проход оптимизируется путем кэширования. Если на стороне сервера - хорошо. На стороне клиента - отлично.
В случае иерархической системы, индексов (в понимании реляционной модели) для обхода дерева, не требуется - ОНО уже организовано ссылками на узлы.
Теперь, почему рекурсия в самом запросе SQL даёт большой выигрыш?
Конструкция "WITH RECURSIVE" заставляет сервер БД проходить по таблицам навигационным способом. Зачастую, без использования индексов, или с очень эффективным кэшированием их в оперативной памяти. Но такой запрос не выполняет никаких подзапросов, т.е. не создаётся никаких рабочих таблиц. Он пользуется двумя навигационными "командами": "найти по ключу" (лучше по номеру-ссылки записи) и "получить следующую запись в порядке индекса" (лучше в порядке ссылок). Всё...
Я Игорю уже отправлял тест программы на 1С 7.7 для рекурсивного обхода дерева путем моделирования иерархической системы на реляционную модель. Естественно, весь код выполняется на стороне приложения (грубо - клиенте) кроме непосредственно получения очередного узла дерева. Если система программирования позволяет такой алгоритм оформить как "задание серверу" (т.к. результирующий массив данных значительно меньше исходных данных) то алгоритм следует отдать на выполнение серверу. Это и есть основное преимущество клиент-серверных технологий. А запросом оформляется задание серверу, или еще чем - это уже не играет роли.
Ниже представлю, на общее обозрение (не только Игорю), полный текст программы из сообщения (98) данной темы. Это написано с применение клиент-серверной СУБД. Но суть её "клиентовости" (для данного примера) - выполнять поиск (навигацию) по индексу реляционной СУБД на стороне сервера для передачи узла дерева клиенту, а не таскать с сервера страницы индексных файлов, как это происходит в файл-серверных СУБД.
Если провести замер времени выполнения каждого оператора этой "программы", то расклад такой: 30-40% - работа сервера, остальное уходит на выполнение машинных команд на клиенте.
У меня - ВСЁ, по теме "Мы пишем запросы"©... ;-)
Перем Степень[6],Уровень,Процесс,ИмяТаб,ТестЦикл,РезулТаб;
//-------------------------------------- 
Процедура Подсчет(Изделие,ИтогКол) 
	Стр=0;
	Если РезулТаб.НайтиЗначение(Изделие,Стр,"Изделие")=0 Тогда
		РезулТаб.НоваяСтрока();
		РезулТаб.Изделие=Изделие;
		РезулТаб.Количество=0;
	            Стр=РезулТаб.КоличествоСтрок();
	КонецЕсли; 
	РезулТаб.ПолучитьСтрокуПоНомеру(Стр);
	РезулТаб.Количество=РезулТаб.Количество+ИтогКол;
КонецПроцедуры
//-------------------------------------- 
Функция Маршрут(Действие,Вершина) 
	Если Действие>0 Тогда 
		Если ТестЦикл.НайтиЗначение(Вершина)<>0 Тогда 
			Сообщить("Цикл в маршруте: "+ЗначениеВСтрокуВнутр(ТестЦикл));	
			Возврат 0;
		КонецЕсли; 
		ТестЦикл.ДобавитьЗначение(Вершина);
	КонецЕсли;
	Если Действие<0 Тогда 
		ТестЦикл.УдалитьЗначение(ТестЦикл.РазмерСписка());
	КонецЕсли;
	Возврат 1;
КонецФункции                                         
//--------------------------------------
Функция хНайти(Вершина) 
	Возврат Число(EXT._(41,ИмяТаб,"VI21",Вершина,1)); 
КонецФункции
//--------------------------------------
Функция хЧитать(ИмяРекв) 
	Возврат EXT._(43,ИмяТаб,ИмяРекв);
КонецФункции
//--------------------------------------
Функция хСдвинуть(Запись)
	Возврат Число(EXT._(42,ИмяТаб,"VI21",Запись,1));
КонецФункции
//-------------------------------------- 
Процедура Обойти(Знач Вершина,Знач КолУров) 
	Зап=хНайти(Вершина); 
	Если Зап<>0 Тогда   
		Если Маршрут(+1,Зап)=0 Тогда Возврат; КонецЕсли; 
		Кол=Число(хЧитать("Количество"));
		КолУров=КолУров*Кол;
		Пока Зап<>0 Цикл
			Если хЧитать("Связь")<>Вершина Тогда Прервать; КонецЕсли;
			Подсчет(хЧитать("Изделие"),КолУров);
			Процесс=Процесс+1; 
			Если (Процесс%1000)=0 Тогда Состояние(Формат(Процесс,"Ч10.0")); КонецЕсли;
			Обойти(хЧитать("ID"),КолУров);
			Зап=хСдвинуть(Зап);
		КонецЦикла; 
		КолУров=КолУров/Кол;
		Маршрут(-1,""); 
	КонецЕсли;
КонецПроцедуры
//-------------------------------------- 
Процедура Заполнить(Знач Вершина)
	Спр=СоздатьОбъект("Справочник.Дерево");
	Уровень=Уровень+1;
	Если Уровень<=Разм(Степень) Тогда
		Для Н=1 По Степень[Уровень] Цикл  
			Процесс=Процесс+1; 
			Если (Процесс%1000)=0 Тогда 
				ЗафиксироватьТранзакцию();
				Состояние(Формат(Процесс,"Ч10.0"));
				НачатьТранзакцию();				
			КонецЕсли;
			Спр.Новый();
			Спр.Связь=Вершина; 
			Спр.Изделие=Формат(Уровень,"Ч10.0")+Формат(Н,"Ч10.0");
			Спр.Количество=2;
			Спр.Записать();
			Заполнить(Спр.ТекущийЭлемент());	
		КонецЦикла;
	КонецЕсли; 
	Уровень=Уровень-1;
КонецПроцедуры
//--------------------------------------
Процедура Выполнить() 
	Процесс=1;
	Спр=СоздатьОбъект("Справочник.Дерево");
	Тим=_GetPerformanceCounter();  
	Если Флаг=0 Тогда //*** Обход дерева ***
		ТестЦикл=СоздатьОбъект("СписокЗначений"); 
 		РезулТаб=СоздатьОбъект("ТаблицаЗначений");
		РезулТаб.НоваяКолонка("Изделие","Строка");  
		РезулТаб.НоваяКолонка("Количество","Число"); 
		ИмяТаб="СправочникДерево";
		Обойти("     1   ",1);
	Иначе             //*** Заполнение *** 
		Уровень=0; 
		Степень[1]=10;
		Степень[2]=10;
		Степень[3]=10;  
		Степень[4]=10;   
		Степень[5]=10;         
		Степень[6]=10;
		НачатьТранзакцию();
		Спр.Новый(); 
		Спр.Связь=ПолучитьПустоеЗначение("Справочник.Дерево"); 
		Спр.Изделие=Формат(0,"Ч10.0")+Формат(0,"Ч10.0");
		Спр.Количество=1;		
		Спр.Записать();
		Заполнить(Спр.ТекущийЭлемент()); 
		ЗафиксироватьТранзакцию();
	КонецЕсли;
	Сообщить("Время: "+Строка(Цел((_GetPerformanceCounter()-Тим)/1000))+" сек.");	
	Сообщить("Количество: "+Строка(Процесс)); 
	Если Флаг=0 Тогда  
		РезулТаб.Сортировать("Изделие");
		РезулТаб.ВыбратьСтроку();
	КонецЕсли;
КонецПроцедуры
//--------------------------------------
Показать
139. Ish_2 1104 18.11.10 22:21 Сейчас в теме
Много правильных слов.. Но главное , вокруг чего весь "сыр-бор" - это ВРЕМЯ Вашего алгоритма. Про это- молчок.Впрочем , имеете право.

Я тоже завершаю.
На следующей неделе появится новая тема "Запрос против рекурсии" ,
в которой я собираюсь доказать неэффективность приведенного в (138) алгоритма самым простым способом : предъявив обработку , которая многократно быстрее всяких "рекурсивных" процедур.
140. hogik 443 18.11.10 23:49 Сейчас в теме
(139)
"Много правильных слов.."(с)
Игорь.
У меня, опять, нет слов.... ;-)
Вы думаете, что я решил рассказать про свой алгоритм? И про время его выполнения?
Ваша оценка этого, действительно, напоминает изучение электрической схемы пульта ДУ от телевизора путем нажимания кнопок. И Вы пытаетесь предложить людям "...чтобы в процессе написания простейшего алгоритма люди задумались над тем : что они делают ? туда ли они попали ?"(с) и "...что дело в другом принципиальном подходе."(с)
Игорь, а Вы уверены, что делаете именно это? Вы людям пытаетесь рассказать о "кнопках пульта ДУ" и не предполагая, что кроме этих "кнопок" есть еще и "электрическая схема".
Это уже не "конкретизм", а верхоглядство...
119. ildarovich 7850 17.11.10 10:24 Сейчас в теме
(116) Попробую. Задача интересная, но разве она не решалась раньше?
120. Ish_2 1104 17.11.10 10:40 Сейчас в теме
(119) Конечно , решалась .
Много раз и разными людьми. В основном на разных диалектах SQL.
Давайте решим её на 1с. Миша (Танго) , как -то написал что в УПП изделие "тепловоз" с 17 уровнями вложенности раскручивается 5-6 мин. А ,дескать, какие-то молодцы (вообщем "кто-то"),используя WITH в SQL раскрутил такой "тепловоз" за 1мин.
По Мише выходит , тут рекурсия здесь ого-ого . В ней - вся сила.
Информация, конечно, смутная , и сказать что-то более определенное невозможно,а проверить у меня нет возможности.
Но посмотреть можно в БП 1.6 - справочник СпецификацияНоменклатуры.
Из него вытекает таблица Владелец, Номенклатура,КОличество и тест в (79).

Есть подозрение : а не выгрузить ли нам справочник СпецификацияНоменклатуры в таблицу значений , и уже в оперативной памяти всё быстренько порешать ?
122. hogik 443 17.11.10 23:39 Сейчас в теме
(120)
"Есть подозрение : а не выгрузить ли нам справочник ... в оперативной памяти всё быстренько порешать ? "(с)
Интересное подозрение, возникшее, на 120-ом сообщении данной темы. ;-)
Однако, эффективность такого решения сильно зависит от способа организации ТЗ в системе. И "выбор по фильтру" может не помочь, а наоборот... Но достаточно иметь упорядоченную таблицу и находить начало повторяющихся значений дихотомическим поиском, а потом последовательным просмотром всех строк с равным значением реквизита - "моделировать" фильтр. Это для алгоритма простого рекурсивного обхода дерева.
Если же ТЗ позволяют строить индексные структуры, то работа с ними мало отличается (по эффективности) от навигационного доступа средствами СУБД (аналог традиционному доступу в DBF-ных системах). Естественно, с поправкой на вид носителя информации (память/диск). Но, любопытно, что размещение базы данных, в моей тестовой платформе, на RAM диск - увеличивает время выполнения задачи на 10-20% при использовании любого из трех аналогов "файлового" режима восьмой версии 1С-а.
121. Ish_2 1104 17.11.10 13:45 Сейчас в теме
(119) Если соберетесь делать , то вдогонку :
Для пользователя , составляющего спецификации номенклатуры было бы очень полезно следующее. Даже при обнаружении ошибки зацикливания алгоритм должен продолжать работу и на выходе в качестве результата :
1. плоская таблица материалов (пусть даже с ошибками)
2. граф всех найденных ошибок
В прикрепленном файле вид графа ошибок.
Прикрепленные файлы:
123. ildarovich 7850 18.11.10 03:13 Сейчас в теме
(116) Честно говоря, не сразу правильно понял задачу. Сначала построил в справочнике 10-арное 6-ти уровневое дерево из 1 111 111 узлов (элементов справочника) и определил все вершины, в которые можно попасть из корня алгоритмом с контролем зацикливания. Когда оптимизировал алгоритм, применив дерево значений и хитрое связывание, получил 180 секунд. Немного напрягся, так как не попадал в Ваши цифры.
Задача оказалась другой. Вы перебираете пути в относительно небольшом графе. Поэтому тут справочник вообще никуда загружать не нужно. Достаточно объектной модели, так как 1С кэширует объекты в памяти.
Вот так выглядит справочник "Справочник" (смотрите рисунок).
Вот так он заполняется по уровням:
// Алфавит - параметр, содержащий, в данном случае "АБВГДЕ"
Функция НайтиИлиСоздать(Код)
	Узел = Справочники.Справочник.НайтиПоНаименованию(Код);
	Если Узел = Справочники.Справочник.ПустаяСсылка() Тогда
		Узел = Справочники.Справочник.СоздатьЭлемент();
		Узел.Наименование = Код;
		Узел.Записать()
	Иначе
		Узел = Узел
	КонецЕсли;
	Возврат Узел
КонецФункции
Процедура Растить(Корень, Уровень)
	Если Уровень <= СтрДлина(Алфавит) Тогда
		Для ё = 0 По 9 Цикл
			Строка = Корень.Элементы.Добавить();
			Элемент = НайтиИлиСоздать(Сред(Алфавит, Уровень, 1) + ё);
			Если ТипЗнч(Элемент) = Тип("СправочникОбъект.Справочник") Тогда
				Строка.Элемент = Элемент.Ссылка;
				Растить(Элемент, Уровень + 1)
			Иначе
				Строка.Элемент = Элемент	
			КонецЕсли
		КонецЦикла;
		Корень.Записать();
	КонецЕсли
КонецПроцедуры
Процедура КнопкаВыполнитьНажатие(Кнопка)
	Запрос = Новый Запрос("Выбрать * ИЗ Справочник.Справочник");
	Для Каждого Узел Из Запрос.Выполнить().Выгрузить() Цикл
		Узел.Ссылка.ПолучитьОбъект().Удалить()
	КонецЦикла;
	ОбновитьНумерациюОбъектов();
	Корень = НайтиИлиСоздать("0");
	Растить(Корень, 1)
КонецПроцедуры
Показать

Вот так перечисляются пути с контролем зацикливания (там точка с запятой ставится между ошибочно связанными узлами)
Перем ОК, Результат;
Процедура Продолжение(Путь, Узел)
	Если НЕ ОК[Узел.Код - 1] Тогда 	
		Если Узел.Элементы.Количество() = 0 Тогда 
			Результат.Добавить(Путь + "-" + Узел.Наименование)
		Иначе ОК[Узел.Код - 1] = Истина; 
			Для Каждого Строка Из Узел.Элементы Цикл Продолжение(Путь + "-" + Узел.Наименование, Строка.Элемент)	
			КонецЦикла;	
			ОК[Узел.Код - 1] = Ложь
		КонецЕсли
	Иначе Результат.Добавить(Путь + ";" + Узел.Наименование)
	КонецЕсли
КонецПроцедуры
Процедура КнопкаСформироватьНажатие(Кнопка)
	Момент = ТочноеТекущееВремя();
	Запрос = Новый Запрос("ВЫБРАТЬ Ложь КАК ОК ИЗ Справочник.Справочник");
	ОК = Запрос.Выполнить().Выгрузить().ВыгрузитьКолонку("ОК");
	Результат = Новый СписокЗначений;
	Продолжение("", ТочкаВхода);
	Сообщить("ПереборПутей(); // выполнялся " + Формат((ТочноеТекущееВремя() - Момент) / 1000, "ЧДЦ=3") + " секунд.");
	Результат.ВыбратьЭлемент("Результат")
КонецПроцедуры
Показать

На моем ноутбуке перебор занимает 40 секунд.
Прикрепленные файлы:
124. hogik 443 18.11.10 04:47 Сейчас в теме
(123)
"10-арное 6-ти уровневое дерево из 1 111 111 узлов"(с)
Именно такое дерево и надо.
126. Ish_2 1104 18.11.10 05:56 Сейчас в теме
(123) Извиняюсь, не стал смотреть код.
Построить нужно :
"10-арное 6-ти уровневое дерево из 1 111 111 узлов"(с)
Именно так.
На последнем шестом уровне имеем 1 000 000 элементов "Е".
После группирования получим в выходной таблице десять элементов
Е01,Е02,Е03,Е04,Е05,Е06,Е07,Е08,Е09,Е10,
со своими количествами.
(122) Мысль " а не использовать ли нам таблицу значений?" была отброшена в самом начале. Хочется проверить.
Примерно 180 сек при ипользовании рекурсии - такое значение мне выдало уже 4 разных человека. Я тут напрягаю кого могу.
Осталось напрячь махровых SQL-щиков , которые утверждают что вся сила в "WITH RECURSIVE". Если начать с вопроса "Я думаю , мозги SQL-щику без надобности... ?" и плавно перейти к задаче , то должно получиться.
127. hogik 443 18.11.10 06:14 Сейчас в теме
(126)
Игорь.
Думаю у НИХ дело не в "WITH RECURSIVE", а в теоретической возможности, благодаря этой конструкции, выполнить запрос целиком на сервере и получить на клиенте "готовое число". И это совсем другая тема (постановка задачи). ;-) Т.е. Вы всегда сможете сформулировать задачу, добавив некое смысловое условие, и ОНИ не смогут это сделать целиком "в мощности" сервера. И тогда - 180 сек. будет... ;-)
129. Ish_2 1104 18.11.10 06:58 Сейчас в теме
(127) Владимир, Ваш пост для меня сложноват. Не дотягиваю до такого уровня.
132. ildarovich 7850 18.11.10 13:01 Сейчас в теме
(126) Именно эти слова меня сначала и запутали!
Построить нужно :
"10-арное 6-ти уровневое дерево из 1 111 111 узлов"

Но:
На самом деле в задаче мы имеем граф из 61-й вершины с 510-тью связями. И построить нужно
все возможные пути из начальной вершину в конечные, определив сумму по всем путям произведений весов вершин в каждом пути для каждой конечной вершины.
Граф "1 111 111" существует только в воображении (уже не в моем). Ни строить, ни хранить его не нужно. Строятся различные пути. Их 1 000 000.

Это действительно задача, которую можно (быстрее?) решить в СУБД, поскольку запись промежуточных результатов ведется в таблицу из 61-го элемента. За пять шагов можно исключить пять уровней. Думаю, подойдет алгоритм из (103). Также сравню с работой в памяти (оптимизирую через дерево значений (123)).
По сути, нужно пять раз умножить вектор из 61-го элемента на разреженную матрицу 61х61.
Конечно, делать нужно в общем виде. Очень интересно! Пожалуй, речь идет о секундах!
133. Ish_2 1104 18.11.10 13:23 Сейчас в теме
(132) Постараюсь понять , что Вы написали.
Но на всякий случай, алгортим должен быть универсальным.
Вначале работы алгоритм не должен обладать никакой априорной информацией о исследуемом графе . Все графы ,какой бы мы не придумали , он должен обрабатывать одинаково.
Т.е. приведенный тест в (79) , это лишь один из возможных частных случаев, помогающих выявить возможности Вашего универсального алгоритма обработки произвольного графа.
134. ildarovich 7850 18.11.10 13:36 Сейчас в теме
(133) Согласен!
И, наконец, понял источник возможного выигрыша. Список путей не нужен!
Достаточно рекурсивно для каждого узла получить, запомнить и далее использовать результат разузлования подчиненных узлов. То есть всего 61 элементарное разузлование!
135. Ish_2 1104 18.11.10 13:43 Сейчас в теме
(134) Сомневаюсь , что мы понимаем друг друга. Возможное зацикливание в каждой из 1 000 000 ветвей Вы проверяте ? Повторяю , находясь в каждом узле , мы ничего не знаем о содержании в подчиненных узлах.
Жду итогового теста процедур с комментриями. Если находите это интересным -создайте тему.
141. ildarovich 7850 19.11.10 02:28 Сейчас в теме
(135)
Развитие идеи поста (134), рекурсия и массив дали в решении Вашей задачи 0,124 секунды. Вот скриншот решения за 3,635 секунды для графа из 33-уровней (331 вершина).
В программе примерно 20 длинных строчек (чтобы быстрей работала). Контроль зацикливания делается.
Сегодня объяснения делать некогда, поэтому текст пока выкладывать не буду.
Прикрепленные файлы:
113. ildarovich 7850 15.11.10 13:38 Сейчас в теме
(106) Поправочка к (107)
...
В нем соединяются две временные таблицы размером N x N/2. По методу циклов
получаем оценку этого запроса O(N x N/2 x N x N/2).
...
Оценка стала в 4-раза лучше, но все равно миллион узлов так не обсчитать - только небольшие графы! Вот результаты случайного графа из 1000 вершин:
Прикрепленные файлы:
108. Арчибальд 2706 15.11.10 09:53 Сейчас в теме
(103) Элегантно. Правда, есть риск, что размер запроса к базе превысит размер самой базы :D
2. RailMen 823 12.10.10 02:00 Сейчас в теме
Перем Выход;

//ТаблицаЭлементов - таблица с одной колонкой "Элемент" типа СправочникСсылка
Функция ПолучениеСвязиЭлементов( Э1 , ТаблицаЭлементов)

НовСтр=ТаблицаЭлементов.Добавить();
НовСтр.Элемент= Э1
ТаблицаЭлементов.Свернуть("Элемент");

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

Конецфункции;


Выход=Ложь;
5. sCHTASS 49 20.10.10 21:34 Сейчас в теме
(2)
Мне собственно нужен был именно текст запроса. Код 1с по определенным причинам не нужен.

Ну лано, не получился рекурсивный запрос, пришлось обойтись пакетным с 5 уровнем вложения. Вроде как работает...
3. RailMen 823 12.10.10 02:05 Сейчас в теме
Вот тебе решение за 5 минут.
Тут только один минус: запрос в рекурсии читай в цикле.
Принципиально лучшее решение врядли предложу.
Ты поднял неохватную тему Иерархических (рекурсивных) запросов.
4. RailMen 823 12.10.10 02:07 Сейчас в теме
строка
ТаблицаЭлементов.Свернуть("Элемент");
наверно лишняя

да и условие выхода из рекурсии надо почетче написать. все извиняй пошел спать...
6. DJ_Codebase 22.10.10 15:26 Сейчас в теме
Ну и паказал бы этот пакет...
9. sCHTASS 49 22.10.10 19:51 Сейчас в теме
(6)
А что показывать. Пакуем в временную таблицу первый уровень. Получаем таблицу ЭК - ЭК1.

Из этой таблицы вытягиваем вложенность 2ого уровня ЭК - ЭК2 (ЭК1.реквизит). И так далее до упора.

Затем полученные таблицы объединяем. Все.
10. Ish_2 1104 22.10.10 19:59 Сейчас в теме
(9) Ничего не понял . ЧТо объединяем -то ? Лучше написать цикл и запрос.
Интересно.
11. sCHTASS 49 23.10.10 23:24 Сейчас в теме
(10)
Объединяем полученные во время выполнения пакетного запроса временные таблицы.
А вопрос стоял не так, чтобы все воткнуть в запрос, а реально ли написать ЗАПРОС, который реализует то, что нужно.
12. Ish_2 1104 24.10.10 01:26 Сейчас в теме
(11) Дело в том , что в задаче (0) возможно зацикливание. Действительно, ситуацию
Э1-Э2
Э2-Э1
нельзя исключать. Поэтому объединять текущую и предыдущую таблицу нужно в каждом цикле лишь после проверки : нет ли в предыдущей таблице элемента из текущей таблицы.
вот почему насторожила фраза в (9):
"Затем полученные таблицы объединяем. Все".
Т.е. объединение таблиц предлагается осуществить после цикла - что , на мой взгляд, принципиально неверно и не учитывает возможность зацикливания в исходной задаче.
13. WKBAPKA 214 30.10.10 12:23 Сейчас в теме
обычные динамические списки... лучшее лекарство, это рекурсия...
2(11): если я правильно понял, то на выходе может получиться очень даже не хиленький запросик...
2(12): если все так как описано в (0) то зацикливания в принципе быть не может, т.к у элемента может быть один и только один родитель
2(8): уровней вложенности может быть n-уровней... как узнать, сколько циклов должно быть без предварительной обработки? можно конечно в цикле проверять на результат, и если следующий уровень не получен, прерывать цикл...

Я бы решил задачу следующим образом. На мой взгляд, из всех предложенных вариантов, этот вариант будет работать быстрее:
1. Делаем запрос к справочнику. Выбираем все элементы справочника.
2. Выгружаем в таблицу значений и индексируем по полю "Родитель"
3. В цикле уже последовательно искать элементы.

Быстрее будет работать, т.к. будет всего лишь один и только один запрос, дальше работа с памятью
14. Ish_2 1104 30.10.10 17:21 Сейчас в теме
(13) Внимательно перечитай (0).
Есть справочник "Справочник". У элементов справочника есть реквизит "Элемент",
который хранит ссылку на другой элемент этого же справочника. Большая часть
элементов связаны по схеме:
Э1 - Э2 - Э3 - ... - ЭN.


Никаких ограничений на значение реквизита "элемент" не приведено. Значит возможно любое значение. Значит и зацикливание возможно.
Примером такого справочника может служить например "спецификацияНоменклатуры" в БП 1.6. На этом справочнике может быть описана спецификация "электровоза"(это пример Танго), имеющая 17 уровней вложенности.
Примерно через неделю , надеюсь, будет разбираться пример как нужно решать такие задачи.
15. WKBAPKA 214 30.10.10 21:30 Сейчас в теме
2(14): ну в этом случае на зацикливание легко можно будет проверить... все же использование таблицы значений будет быстрее работать, как считаешь? мне самому интересно, а можно ли действительно одним запросом все это вытянуть, ведь иерархические справочники в 1С по сути и являются динамическими списками... в 7.7 было ограничение на глубину 10 уровней, в 8-ке такого ограничения нет... интересно, как преобразовывается запрос если использовать ИЕРАРХИЯ
16. Ish_2 1104 30.10.10 22:51 Сейчас в теме
(15) Ага ! вспомнил ! Твоё предложение использовать ТОЛЬКО ИЕРАРХИЯ в запросе подвинуло тему на форуме в верном направлении.
Здесь , правда, другой случай.
Вообще-то, я выгрузку в таблицу значений исходного справочника даже не рассматриваю. Это не религия. Просто дело в том , что работая в СУБД нужно прежде всего использовать запросы. Если проигрыш при использовании запросов уж очень велик , то тогда можно рассмотреть и кодинг.
В данном конретном случае , считаю что можно обойтись циклом с одним запросом.
Посмотри (7).

Я веду речь идет о размере справочнка - 100 000 элементов и уровень вложенности до 30. Хотелось бы уложиться для самого плохого случая "разузлования" в 30 сек.
Но не будем опережать события . Подождем неделю.
17. Ish_2 1104 31.10.10 04:45 Сейчас в теме
(15) Почему нельзя в задаче "разузлования" использовать выгрузку справочника в таблицу зачений и последующую "В ЛОБ" рекурсивную процедуру раскручивания каждой ветки.
Потому что дерево НЕБИНАРНОЕ допускает коварные штуки.

Каждый из различных элементов А1....А1000 содержит в себе в качестве подчиненных одинаковый набор В1....В1000.
В свою очередь каждый из В1.....В 1000 состоят из других элементов С1..С1000.
Если ты последовательно начнешь раскручивать каждую ветку А-В-С - тебе КОНЕЦ. и никакая быстрая оперативная память тебя не спасет.
Ты попадаешь на миллиард.
Но если ты раскрутил только А -В и увидел :

А1 - В1
----- В2
----- .....
----- В1000

А2- В1
----- В2
----- .....
----- В1000
.................................

Прежде чем раскручивать столбец "В" далее , давай сгруппируем В и получим уже без повторений только тысячу элементов В1...В1000 , вместо миллиона, т.е. в тысячу раз меньше.

Рекурсия "В ЛОБ" для Субд - это ужасное ЗЛО.
18. WKBAPKA 214 31.10.10 10:35 Сейчас в теме
2(17): можно и без рекурсии обойтись, одним циклом... таблицу значений проиндексировать и поиск будет выполняться уже по индексу (по свойе сути, запросы ведь работают по схожей технологии)... сложно сказать, что будет работать быстрее без замеров, 1000 запросов или 1000 поисков... логика подсказывает, что 2-ое... ведь каждый запрос - это новое открытие соединения с базой, выборка, т.е. работа с дисковой системой... с другой стороны, если количество элементов справочника будет ну ооооочень большим, то тут может не хватить оперативной памяти... задачка интересная...
8. Ish_2 1104 22.10.10 17:59 Сейчас в теме
+7 Реально решить задачу простым циклом с одним запросом. Циклов будет столько сколько уровней вложенности.
А Рекурсия здесь - ужасное зло.
19. WKBAPKA 214 31.10.10 12:12 Сейчас в теме
правда тогда никто не мешает использовать временные таблицы вместо таблицы значений... быстрее работать не будет, зато надежнее :)
20. Ish_2 1104 01.11.10 13:07 Сейчас в теме
(19) Нет ,Ярослав. Если в примере , описанном в (17) , не применить "группирование" по колонке( в запросе ли .. в таблице значений ли ... с рекурсией ли ... без рекурсии ли ) - ЛЮБОМУ твоему алгоритму - КОНЕЦ.
21. WKBAPKA 214 01.11.10 13:31 Сейчас в теме
2(20): так в выборку должны попасть только различные элементы... т.е. повторяющихся быть не должно...

приблизительно так:

ВЫБРАТЬ РАЗЛИЧНЫЕ
Ссылка, СсылкаНаСсылку
ИЗ
Справочник.МойСправочник

после чего выгрузить в ТЗ или во временную таблицу и путем перебора искать нужный элемент... при этом не забыв сделать массив обработанных элементов... тут бы неплохо провести эксперемент... может цикл с запросами действительно быстрее будет работаь
22. Ish_2 1104 01.11.10 14:12 Сейчас в теме
(21) Всё это хорошо . Есть только одно НО. Это зацикливание.
Нужно проверять на каждом шаге(цикле) не встречается ли данный текущий элемент в множестве своих родителей.
Применяя "Выбрать различные " ты вместо множества исходных веток дерева с одинаковым элементом на конце - оставляешь одну. А почему, собственно ?
В оставшейся ветке могут встретиться элементы из отброшенных тобой веток.
Пример
Рассмотрим три ветки.

1. А -- В1 -- С1 -- B2
2. А -- В2 -- С1 -- В2
3. А -- В2 -- С2 -- Д
На третьем уровне (С1,С1,С2) ты решил применить "Выбрать различные",
т.к. зачем нам дважды исследовать С1. Ты оставляешь только первую ветку, в которой все замечательно и нет зацикливния.
Но во второй ветке , которую ты отбросил - ОШИБКА зацикливания .
23. WKBAPKA 214 01.11.10 15:42 Сейчас в теме
2(22): если это динамический список, то такого быть не может
25. Ish_2 1104 01.11.10 15:49 Сейчас в теме
(23) Почему не может ? Всё может быть в дереве. И, раскручивая дерево , программист должен быть готов ко всему.
А если не может такого быть , то что мы обсуждаем ? О чём тогда вообще речь ?

Хм... Как с помощью рекурсии "выбрать" все элементы дерева ?
Да уж... (с)
26. hogik 443 02.11.10 19:22 Сейчас в теме
(22)
"Нужно проверять на каждом шаге(цикле) не встречается ли данный текущий элемент в множестве своих родителей."(с) "2. А -- В2 -- С1 -- В2"(с)
А это уже не дерево, кажись. ;-)
"Дерево — это связный граф (то есть такой граф, между любой парой вершин которого существует по крайней мере один путь), не содержащий циклов (то есть ациклический граф). Ацикличность означает, что между любой парой вершин в дереве существует только один путь."
Проверять, может и имеет смысл, но при заполнении исходных данных. Т.к. вспоминая о задаче, приведшей Вас на эту тему форума, будет странно смотреться такое:
Тепловоз -- КолеснаяПара - Ось - КолеснаяПара
Тепловоз -- КолеснаяПара - Колесо (2 шт.) - КолеснаяПара
(24)
""придется при "лобовом" решении многократно "раскручивать" В1. Дай то Бог , если в В1 - мало элементов , а если там миллион ?" (с)
Думаю, при "НеЛобовом" решении придется организовать дополнительное хранилище уже раскрученных элементов. И обеспечить более эффективный способ вытаскивания/вставки туда раскрученных элементов, чем исходные данные. А эффективнее, уже созданной (исходной) структуры, можно придумать способ хранения?
(16)
"Просто дело в том , что работая в СУБД нужно прежде всего использовать запросы."(с)
Работая в СУБД, нужно прежде всего использовать СУБД. И не ставить знак равенства между СУБД и "запросом".
(17)
"Рекурсия "В ЛОБ" для Субд - это ужасное ЗЛО."(с)
На самом деле не "для СУБД", а для СУБД с запросным ЯМД. Хотя и в некоторых СУБД с запросным ЯМД, рекурсия реализуется успешно, даже без особых конструкций типа "Рекурсия" языка запросов.
P.S. (1) Мои тексты на сообщения #16 и #17 не имеют отношение к заголовку темы. Извините... Это я Игорю по теме "Мы пишем запросы" занудно бла-бла пишу. ;-)
29. Ish_2 1104 02.11.10 22:02 Сейчас в теме
(26) , (27) Грамотные , значит... Вы тут меня не пугайте : "ациклический граф", "динамические списки", "такого не может быть!"...
Может .
Даёшь "Циклический граф" и "Адинамические списки" !
В этом ВСЯ СОЛЬ ЗАДАЧИ . В узлах могут быть ЛЮБЫЕ Элементы.
Отсылаю вас к справочнику СпецификацияНоменклатуры в БП 1.6.
Задача из тривиальной превращается в нечто интересное.
И это нечто я собираюсь решать. Без рекурсии. Только средствами 1с.
Будем надеяться , всё получится .
30. hogik 443 02.11.10 22:22 Сейчас в теме
(29)
1) "Отсылаю вас..."
Отсылать - дело хорошее. ;-)
Покажите мне, пожалуйста, картинкой (в этой теме форума) описание назначения справочника "СпецификацияНоменклатуры в БП 1.6" и пример про "КолеснуюПару" в реальном списке этого справочника.
2) "Будем надеяться , всё получится ."
Я и не сомневаюсь - у Вас всё получится.
32. Ish_2 1104 02.11.10 22:56 Сейчас в теме
(30) Дана таблица
Владелец , Номенклатура, Количество.

Колонки Владелец и Номенклатура - одного типа . Таблица заполнена одному Богу известно как.
Для выбранной пользователем Номенклатуры нужно получить получить плоскую таблицу
Номенклатура , Количество. Т.е раскрутить дерево до элементов , которые не имеют подчиненных("детей").
24. Ish_2 1104 01.11.10 15:42 Сейчас в теме
(21) А чтобы картина была более полной ( в какое болото я тебя затащил !)...
Представь себе дерево.
А - В1 - ...
А - В2 - B1 - ...
А - В2 - С1
А - В2 - С1 - В1 - ...
А - В2 - С1 - Д1

Элемент В1 находится на разных уровнях в дереве. Здесь уже никак не применить "Выбрать различые" и нам придется при "лобовом" решении многократно
"раскручивать" В1. Дай то Бог , если в В1 - мало элементов , а если там миллион ?
27. WKBAPKA 214 02.11.10 21:37 Сейчас в теме
так, Вы тут меня не путайте ... динамические списки - это динамические списки... зацикливания в оных быть не может... если есть зацыкливание, то оное уже не динамические списки, то бишь не дерево!
28. hogik 443 02.11.10 21:56 Сейчас в теме
(27) Ярослав. Кому адресовано сообщение?
31. Ish_2 1104 02.11.10 22:47 Сейчас в теме
Проверять, может и имеет смысл, но при заполнении исходных данных. Т.к. вспоминая о задаче, приведшей Вас на эту тему форума, будет странно смотреться такое:
Тепловоз -- КолеснаяПара - Ось - КолеснаяПара


Я пишу четко по теме (0), где ни слова об ограничениях на реквизит "Элемент".
А Вы пишете о том, что привычнее и понятнее .
Представьте себе , что Вам уже поставили задачу в виде (0) и отговорки "типа не то" и "как бы неправильно", что "надо было контролировать при вводе" уже не принимаются. Поздно. Нужно иметь дело с тем что есть. Что будем делать ?
33. hogik 443 02.11.10 23:00 Сейчас в теме
(31)
Игорь.
1) "Что будем делать ?"
Будем делать то - что требуется. Про "бой с тенью", вроде, уже Вам написали...
2) "А Вы пишете о том, что привычнее и понятнее."
Я пишу о том, что Вы пишете: "...исходных веток дерева..."(22), "Всё может быть в дереве. И, раскручивая дерево..."(25)
3) Вы сможете выполнить мою просьбу из #30 сообщения?
34. Ish_2 1104 02.11.10 23:07 Сейчас в теме
(33)
В (32) всё сформудировано. Пусть будут и ограничения :
В таблице не более 100 000 строк. Уровень вложенности "элементов" 30.

Соображение.
На любой самый расчудесный алгоритм найдется такое заполнение Таблицы , которое подвесит на месяц самый наимощнейший компьютер. Поэтому речь , как я сейчас понимаю, идет о некоем усредненном , наиболее оптимальном в большинстве случаев алгоритме. И не более того.
35. hogik 443 02.11.10 23:17 Сейчас в теме
(34)
Игорь.
Я так понял, что пишу в пустоту. Извините... :-(
36. Ish_2 1104 02.11.10 23:42 Сейчас в теме
(35) Картинкой сейчас не могу. Суть такая.
Справочник Номенклатура имеет подчиненный справочник СпецификацияНоменклатуры. В нем указывается из каких "номенклатур" состоит текущий элемент справочника.
Например . Элемент справочника Номенклатура - "Электровоз" имеет в подчиненном справочнике три записи :
- колеса 4 шт.
- корпус 1 шт.
- окно 4 шт.
В одной таблице можно отобразить так :
Владелец, Номенклатура , Количество
Электровоз Колеса 4
Электровоз Корпус 1
Электровоз Окно 4
Но элемент справочника Номенклатура "Окно" имеет свою спецификацию. Продолжаем
ту же таблицу
Окно Стекло 1
Окно Рама 1
И так далее.
Т.е. в (32) минуя эти рассуждения я привел вам сразу эту Таблицу . Упростил так сказать.
38. hogik 443 03.11.10 00:07 Сейчас в теме
(36)
А я Вас не об этом спрашивал.
Я спрашивал - "деревом" или не "деревом" является этот справочник в понимании разработчиков "БП 1.6". В их определении и реализации алгоритмов контроля ввода информации. И какую задачу Вы себе поставили...
37. hogik 443 02.11.10 23:57 Сейчас в теме
(34)
Игорь.
Только несколько цитат из Ваших высказываний в теме:
"Я пишу четко по теме (0), где..."
"Дана таблица Владелец , Номенклатура, Количество."
"Отсылаю вас к справочнику СпецификацияНоменклатуры в БП 1.6."
"Задача из тривиальной превращается в нечто интересное."
"И это нечто я собираюсь решать."
И далее, и подобное про "древесину". ;-)
Перечитайте, пожалуйста, сообщение #1.
И либо давайте обсуждать задачу автора темы, либо давайте обсуждать уже Вашу задачу.
Обращаю, Ваше внимание, что я писал свои сообщения не на #1, а на Ваши сообщения.
39. Ish_2 1104 03.11.10 00:10 Сейчас в теме
40. WKBAPKA 214 03.11.10 08:43 Сейчас в теме
2(39): в моем конструкторе "Финансы и анализ" из одной ячейки можно ссылаться на другую ячейку отчета, что естественно может привести в зацикливание... учитывая, что расчет формул выполняется в рекурсии, исключительную ситуацию "зацикливание" я успешно отрабатываю и выхожу из рекурсии в случае оной...

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

Группа (
ИмяГруппы: Строка
Родитель: Ссылка
)

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

Группа (
ИмяГруппы: Строка
РодительПредыдущий: Ссылка
РодительСледующий: Ссылка
)

В этом варианте возможно зацикливание... Но этого же нет в исходной задачи!

Я предложил сделать простую выборку справочника, что бы перетянуть данные для дальнейшей обработки в оперативную память, или в виде виртуальной таблици (в треминах 1С), проиндексировать поле по которому будет осуществляться поиск, а дальше, дело техники...
41. WKBAPKA 214 03.11.10 08:48 Сейчас в теме
и еще раз привожу из (0):

Есть справочник "Справочник". У элементов справочника есть реквизит "Элемент",
который хранит ссылку на другой элемент этого же справочника. Большая часть
элементов связаны по схеме:
Э1 - Э2 - Э3 - ... - ЭN.


вроде нет двухсмысленности
42. Ish_2 1104 03.11.10 09:22 Сейчас в теме
(41) До меня , кажется ,дошло, что вас с Владимиром сбивает с толку.

1. Что такое "дерево" ? Можно понимать как "ациклический граф" , определением которого тыкает мне Владимир . В контексте же беседы , совершенно ясно , что ациклический граф "ДеревоЗначений" используется для хранения таких данных , которые ссылаются друг на друга.
Рассмотрим пример дерева (ациклического графа):

- Корень
----------- Ветвь1
----------- Ветвь2

Этот ациклический граф используется для хранения в своих узлах каких-то данных.
В скобках указано что содержится в узле :

- Корень ("Электровоз")
---------- Ветвь1 ("Колеса")
---------- Ветвь2 ("Корпус")

Видя это дерево в форме , пользователь решил изменить данные содержащие в "Ветви2". И получил

- Корень ("Электровоз")
---------- Ветвь1 ("Колеса")
---------- Ветвь2 ("Электровоз")

Что же мы получили ?
Мы получили , что ациклический граф ("Дерево") содержит значения которые образуют
"неправильное циклическое дерево" .

Ты простишь пользователя , который сделал такую ошибку ?
Может он так ошибиться в многоуровневом дереве ? - МОЖЕТ .

В конфигурации создадим Справочник:
Код, Наименование, Элемент( с типом "этот справочник")
Запустим конфигурацию на исполнение , откроем форму справочника для ввода новых записей. Скажи мне , чем ограничен пользователь при вводе в поле "Элемент" ?
Правильный ответ : НИЧЕМ. Пользователь может организовать таким образом
"ЛЮБОЕ НЕПРАВИЛЬНОЕ ДЕРЕВО".
Вот это "неправильное дерево" и нужно раскрутить с контролем возможного зацикливания.
43. WKBAPKA 214 03.11.10 09:27 Сейчас в теме
2(42): ты прав, что можно сослаться на первоначального родителя, в этом случае произойдет зацикливание...но такая ситуация решаема... причем легко
44. Ish_2 1104 03.11.10 09:31 Сейчас в теме
45. hogik 443 03.11.10 09:37 Сейчас в теме
(42)
1) "определением которого тыкает мне Владимир"(с)
Я Вам не тыкаю. :-)
2) "чем ограничен пользователь при вводе в поле "Элемент" ?"(с)
Грамотно написанной программой. Для пользователя, для достоверности данных в базе. И это надо писать, а не х-й заниматься, типа, "Рекурсии" запросами. Ух, разозлил меня...
46. Ish_2 1104 03.11.10 09:43 Сейчас в теме
(45) В дереве 30 уровней - 100 000 элементов.
Наконец-то, приближаемся ! Приближаемся к развязке :
Как вы "грамотно" проконтролируете правильность заполнения дерева
("незацикленность") если пользователь решил поменять значение содержащееся на 27 уровне у элемента с номером, скажем 65 555 ?
При этом дерево представлено в базе в виде таблицы Владелец, Номенклатура, Количество.
47. hogik 443 03.11.10 18:25 Сейчас в теме
(45)
"Как вы "грамотно" проконтролируете правильность..."(с)
Движением вверх по дереву. Т.е. 27 чтений (поисков) по ключу.
Игорь, пожалуйста, отвлекитесь на минутку от мысли о запросах.
Задача проверять наличие "циклов" - реально существует.
Но, часто, многие задачи (проблемы) "выносятся за скобки" из-за отсутствия нужного (эффективного) инструмента для решения этой задачи. И происходит это в ущерб конечной задачи. И, если в "Спецификация Номенклатуры в БП 1.6" нет контроля "циклов" при вводе информации, то это и есть тот случай. Т.е. средства разработки диктуют (давят) на постановку конечной (локальной) задачи. И тогда рождается халтура, а не система. Об этом я Вам и пишу уже, почти, год... :-(
Я допускаю, что в "СП в БП 1.6" не стоит вопрос описывать "дерево". Например, они дают возможность описывать "сеть". Именно это я и хотел выяснить - посмотреть описание от 1С и увидеть сам факт "цикла" в фотографии списка элементов справочника.
48. Ish_2 1104 03.11.10 19:17 Сейчас в теме
(47) Ок.Отвлекся от мысли о запросах.
1. Стоило ли описывать древовидную структуру так как это сделано в Справочнике СпецификацияНоменклатуры - я не обсуждаю.
2. Рассуждать о том , хорошо ли это , и в какой СУБД поставленная задача была бы превосходно решена - я тоже не буду.
3. Не обсуждаю я и ценность поставленной задачи. Как и когда рождается халтура - меня также не волнует.

Внимание ! Я обсуждаю решение поставленной задачи :
Дана Таблица, составленная из справочника СпецификацияНоменклатуры :
Владелец , Номенклатура, Количество.
Эта одна таблица описывает спецификации всех номенклатур базы.
Допустим эта таблица идеальна и не содержит зацикливаний.
Пользователь-технолог решил в номенклатуре Агрегат N заменить одну из его составляющих, например "Составляющая 2".
Он выбирает в форме номенклатуру "Агрегат N" и получает список его составляющих первого уровня :
Агрегат N
----- Составляющая 1
----- Составляющая 2
----- Составляющая 3.

Изменив "Составляющую 2" на "Составляющую Х" , нужно убедиться нет ли зацикливания.
Что есть "Составляющая Х" ? это узел находящиися где в середине дерева.
     \                                 /
      --  Составляющая Х --
     /                                 \


Показаны расходящиеся влево и вправо ветви дерева из центра "Составляющая Х", образующих два поддерева Левое и Правое. Исследовать на зацикливание (повторение элемента Составляющая Х)нужно и Левое (вверх по иерархии) и Правое дерево (вниз по иерархии).
Соствляющая Х может находится в любом узле Левого и Правого дерева.

Отсюда становится понятно , что Ваше предложение неверно :
Движением вверх по дереву. Т.е. 27 чтений (поисков) по ключу.


Действительно , таким способом вы определите лишь есть ли зацикливание в одной ветке Левого дерева.
49. hogik 443 03.11.10 20:40 Сейчас в теме
(48)
Игорь.
После "эпиграфа" из трех пунктов, действительно - обсуждать ничего не надо и не имеет смысла. Жаль. Конкретный Вы, наш... ;-)
Однако...
1) Вы не разделяете понятие "ввод" и "заменить" информацию? Естественно при замене значения узла требуется просмотреть "дерево" и вверх и вниз. Вверх - см. выше по теме. Вниз - рекурсия от заменяемого значения до первого нахождения нового значения заменяемого узла среди уже имеющихся ниже.
2) Я, выше по теме, просил Вас определиться для себя и собеседников - какую задачу мы обсуждаем? Постановку автора темы или Вашу постановку? Задачи разные по способу организации исходных данных. Да и по сути, думаю - разные. Допустим, определились - обсуждается Ваша постановка.
А в Вашей постановке, в части замены, заменяется значение (!!!) узла (реквизита строки таблицы) в одном дереве. И никакого влияния на другие деревья оно не может оказывать. Т.е. для "Агрегат 1" замена значения узла "Составляющая 2" не означает замену некого значения узла в "Агрегат 2". А если - означает, то для каждого дерева, где есть "в узле" такое значение, надо искать зацикливание вверх и вниз. Чудес не бывает. Но, думаю, это уже третья постановка задачи - вроде как, и не про "древесину". ;-)
Ага?
50. hogik 443 03.11.10 22:55 Сейчас в теме
(48)
1) Еще добавлю про саму суть замены значения в узле.
При замене значения реквизита, например,"Номенклатура" происходит перестройка дерева. Т.е. от этого узла начинается уже другое поддерево. Если оно уже существовало в базе, то в нем циклов не будет, т.к. была проверка в момент его ввода. А проверить повторяемость всех узлов этого поддерева с узлами стоящими выше точки прикрепления поддерева - требуется.
2) Контроль дерева "на циклы" надо делать при вводе (изменении) данных, а не при его обработке. Т.к. информация должна лежать в базе изначально верной. Ведь, кроме Вашей задачи обработки дерева есть и другие задачи. Им желательно иметь верные исходные данные. Т.е. в Вашем алгоритме проверки на циклы в дереве можно и не делать, т.к. по жизни такого в системе не должно быть.
51. Ish_2 1104 03.11.10 23:38 Сейчас в теме
52. hogik 443 03.11.10 23:42 Сейчас в теме
(51)
"Э...эх." - это "плюс" или "минус". И Ваше "Ок." имеет двоякий смысл. Поясните, пожалуйста...
55. Ish_2 1104 04.11.10 00:28 Сейчас в теме
(52),(53) Передохнем.
Своего решения я не представил. Чего шашками махать...
56. hogik 443 05.11.10 23:22 Сейчас в теме
(55)
Игорь.
Меня опять посетила мысль. ;-)
Если уже структура исходных данных для начальной задачи изменилась, то что мешает попробовать придумать некую структуру (способ) хранения "деревьев" в среде 8.х с помощью её штатных средств ЯОД для эффективной обработки "дерева" её ЯМД. И, возможно, тогда в цикле "Мы пишем з..." родится ППП для поддержки "деревьев" в среде 8.х. Или это уже сделано?
57. Ish_2 1104 06.11.10 04:52 Сейчас в теме
(56) Я бы сформулировал так : возможна ли более эффективная процедура раскручивания дерева (читай - "разузлованиаее" номенклатуры), хранящегося в базе в виде таблицы
Владелец,Номенклатура,Количество .
Ничего еще не сделано. А имеющийся у меня в настоящий момент алгоритм разузлования вызывает только сомнения. Вот и всё.
58. hogik 443 06.11.10 17:59 Сейчас в теме
(57)
Это уже было сформулировано многократно выше по теме.
Я о другом говорю. Таблица "Владелец,Номенклатура,Количество" это "внешнее" представление. Но "таблицу" можно организовать различным способом под предполагаемые алгоритмы её обработки. Например, ввести в структуру дополнительные поля, ссылки, представить несколькими "таблицами" и т.д. Т.е. заниматься не только "процедурой"...
Я не получил ответ фразой "Ничего еще не сделано". Я спрашивал о наличии штатных в 8.х средств (возможностей) представления информации "пригодной" для решения "НАШЕЙ" задачи, кроме "в виде таблицы"(с).
53. WKBAPKA 214 03.11.10 23:48 Сейчас в теме
ребята, мы приходим к одной старой и народной мудрости: автоматизировать хаос не возможно, а если автоматизировать хаос, мы получим в итоге автоматизированный хаос... в данной теме склоняюсь к Владимиру, т.к. да, действительно, есть вероятность, что первоначальному узлу А1 можно задать родителя из его подчиненных узлов... если попробывать такое проделать для группы в 1С, будет выдано сообщение об зацикливании уровней... т.е. проверку на корректность ввода информации в рамках конкретной задачи выполняем на этапе ввода... и решать задачу нужно исходя из конкретных условий! в противном случае получается обычный хаос !
54. hogik 443 04.11.10 00:16 Сейчас в теме
(53)
В алгоритмах обхода "дерева" существую способы выявления циклов. И, думаю, их можно прописать в задаче поставленной Игорем. Но, т.к. задача стоит - "запросами", то, думаю, имеет смысл сделать хотя-бы "ядро" задачи, а не распыляться на нюансы.
Помню, когда я решал подобную задачу на IBM/360, то цикл в дереве определялся по ритму мигания лампочек на пульте управления и такту покачивания дискового накопителя. Кстати памяти у неё было 128 килобайт, пара-тройка дисководов по 7 мегабайт, до 4-х лент по 28 мегабайт. И ничего, справлялась с "тепловозами"... ;-)
59. Ish_2 1104 06.11.10 18:20 Сейчас в теме
(59) В БП 1.6 никакие дополнительные возможности ( имеется ввиду дополнительные структуры) хранящиеся в метаданных конфигуратора мне неизвестны.

Извиняюсь , мне даже в голову такое не приходило . Как такое может быть ?
Есть структура справочник СпецификацияНоменклатуры , который однозначно описывает все возможные деревья номенклатур. Точка.
Вы что же предлагаете хранить в конфигураторе некие постоянные вспомогательные(избыточные) справочники - таблицы , которые ускорят построение дерева для СпецификацииНоменклатуры ? И изменение справочника СпецификацииНоменклатуры будет влечь за собой изменения во всех вспомогательных таблицах - справочниках ?
Причем по неким неведомым правилам , которые якобы ускорят дальнейший поиск ?
Хотел бы я посмотреть на эти правила , оптимизирующие построение произвольного дерева с НЕОГРАНИЧЕННЫМ уровнем вложенности. Ну если бы уровень вложенности был сильно ограничен (например, 6 или 7), но у нас так задача не стоит.
И для 6,7 уровней стандартный алгоритм неплохо справляется. какой смысл ?

Резюме .Целесообразность и последствия такого шага вызывает у меня полное изумление.
60. hogik 443 06.11.10 19:41 Сейчас в теме
(59)
А меня изумляет Ваше изумление на моё предложение после наличия Вашего текста из #17 сообщения: "Каждый из различных элементов А1....А1000 содержит в себе в качестве подчиненных одинаковый набор В1....В1000."(с) Т.е. никакого другого способа как "запросы" Вы не знаете для "...давай сгруппируем В и получим..."(с). Т.е. при использовании регистров накопления хранить итоги это нормально при "единственном" полезном качестве запросов "быстро считать итоги". А при ""разузлованиаее" номенклатуры"(с) - только тупая выборка.
Ну, Вы же мне обещали отвлечься "от мысли о запросах". Не получается? ;-)
61. Ish_2 1104 06.11.10 19:55 Сейчас в теме
(60) Предлагайте конкретно .

1. Какие Вы предлагаете хранить дополнительные структуры или таблицы для ускорения поиска в таблице описывающей СпецификацииНоменклатуры :
Владелец,Номенклатура,Количество.

2. Какие отношения(взаимосвязи) этих дополнительных структур с основной таблицей должны быть ?

Просьба : без размышлизмов.
65. hogik 443 06.11.10 20:29 Сейчас в теме
(61)
Игорь.
Вы сами поняли, что написали?
Вы предлагаете ускорить поиск в этой несчастной таблице!
А я предлагаю эту "таблицу" иметь только в голове, как конечную (удобную) модель для понимания (осознания) постановки задачи. А суть хранения "деревьев" обеспечивать другими структурами. И про эти структуры (штатных для 8.х) подумать и обсудить.
А Вы хотите "без размышлизмов"(с). Это не ко мне. Я не умею не применять "размышлизм".
Пишите запросы...
66. Ish_2 1104 06.11.10 21:10 Сейчас в теме
(65) А я уж , напрягся.. Ожидал откровений. А вопрос -то был без подковырки . Потому что я не знаю иерархических баз данных. а Ваше смутное предположение о неких структурах именно из этой области. Начав рассуждать о том какие структуры для хранения иерархичсеской информации нужны мы бы потихоньку и на своём уровне приблизились к построению некой иерархической базе данных. Проку, правда, от этого никакого , но интересно было бы послушать.

На самом-то деле дополнительные структуры нужны. только не те что Вы предложили , скажем дополнительный индекс на основную таблицу. Жаль только , что 1с не позволяет индексировать по выражению , или с фильтром. Можно только :
Индексировать Владелец.
Оставьте свое сообщение
Вакансии
Руководитель направления 1С
Москва
зарплата от 350 000 руб.
Полный день

1С Программист
Москва
зарплата от 180 000 руб.
Полный день

Программист 1С
Москва
зарплата от 180 000 руб. до 220 000 руб.
Полный день

Аналитик 1С / Бизнес-аналитик
Нижний Новгород
зарплата от 100 000 руб. до 250 000 руб.
Временный (на проект)

Программист 1С
Москва
зарплата от 250 000 руб.
Полный день