Запрос против рекурсии или разузлование номенклатуры

Опубликовал Ish_2 в раздел Программирование - Практика программирования

В задаче "разузлования" номенклатуры в БП 1.6 (2.0) покажем , что  запрос  более эффективен, чем рекурсия.

Программисты при произнесении слов "граф" или "дерево" , не задумываясь продолжают : "Понятно.. это рекурсия !" . Не вдаваясь в дискуссию о том , почему   рекурсия в БД есть синоним неэффективности, мы на простом примере рассмотрим решение задачи "разузлования" номенклатуры принципиально "нерекурсивным" методом. Выберем  эпиграф для статьи :

"Запрос в БД - это сила. Рекурсия - это зло ." 

 


§ 1. Где и зачем это нужно ?

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


§ 2. Постановка задачи.

На нижеприведенном рисунке изображено два способа отображения графа "Спецификации" :

 

 

 

 

 

 

 

 

Рис. 1. Два способа отображения графа. 

В базе данных (БД) такой граф хранится  в табличной форме , поэтому в дальнейшем мы будем рассматривать  таблицу "Спецификации" в качестве исходных данных. Итак , сформулируем задачу разузлования "узко" для изображенного примера : для номенклатуры "Электровоз" найти все составляющие его номенклатуры , неимеющие подчиненных ("детей") с  расчетом необходимого количества .Т.е. в качестве решения мы  должны получить таблицу :

    

 

 

 

 

 

 

 

 Рис. 2. Выходная таблица. 

§ 3. Решение.

Преобразуем заданную в условии задачи таблицу "Спецификации", добавив колонку
"КодНоменклатуры" :

 

 

 

 

 

 

 

 

Рис. 4. Таблица "Спецификации".

Создадим временную таблицу "ВремТаблица0" с единственной записью ,содержащей  
номенклатуру "Электровоз" :

 

 

 

 

 

 

 

 

Рис. 5. Начальная таблица ВремТаблица0.

Начальные данные заданы. Рассмотрим код обработки :

  ТекстЗапроса = "ВЫБРАТЬ
                   |    ЕСТЬNULL(Спец.Номенклатура, Исх.Номенклатура)                 КАК Номенклатура,
                   |    Исх.Количество * ЕСТЬNULL(Спец.Количество, 1)                    КАК Количество,
                   |    Исх.СтрокаКодов + ЕСТЬNULL(Спец.КодНоменклатуры, """")   КАК СтрокаКодов,
                   |    ВЫБОР
                   |        КОГДА Исх.ПризнакКонцаВетки > 0
                   |            ТОГДА Исх.ПризнакКонцаВетки
                   |        КОГДА Спец.КодНоменклатуры ЕСТЬ NULL
                   |            ТОГДА 1 // нормальное завершение ветки
                   |        КОГДА Исх.СтрокаКодов ПОДОБНО Спец.КодНоменклатуры
                   |            ТОГДА 2 // зацикливание
                   |        ИНАЧЕ 0     // ветка продолжается
                   |    КОНЕЦ                                                                                  КАК ПризнакКонцаВетки
                   |ПОМЕСТИТЬ Последующая
                   |ИЗ
                   |    Исходная КАК Исх
                   |     ЛЕВОЕ СОЕДИНЕНИЕ Спецификация КАК Спец
                   |     ПО (Исх.ПризнакКонцаВетки = 0) // соединяемся только тогда, когда ветка продолжается
                   |            И Исх.Номенклатура = Спец.Владелец
                   |;
                   |УНИЧТОЖИТЬ Исходная
                   |;
                   |ВЫБРАТЬ ПЕРВЫЕ 1 Посл.Номенклатура
                   |ИЗ  Последующая КАК Посл
                   |ГДЕ Посл.ПризнакКонцаВетки = 0"
;

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

На рис. 5-8 расмотрены промежуточные временные таблицы алгоритма во всех циклах решения.

 

 

 

 

 

 

 

 

Рис. 5 Таблица ВремТаблица0.

 

 

 

 

 

 

 

 

Рис. 6. Вид таблицы  после исполнения первого цикла ( перед началом второго).
В колонке ""СтрокаКодов" накапливаются все коды номенклатуры текущей ветки.

 

 

 

 

 

 

 

 

 

Рис. 7. Вид таблицы  после исполнения второго цикла . Обратите внимание , 
обнаружено зацикливание , но работа "по графу" продолжается. Следующий цикл
- третий.

 

 

 

 

 

 

 


Рис. 8. Вид таблицы  после исполнения третьего цикла. Все записи таблицы имеют
ненулевой ПризнакКонцаВетки - осуществляется выход из цикла.

ВремТаблица3 содержит все необходимые данные для вывода результатов решения :
 - графа ошибок ( по колонке "СтрокаКодов" для номенклатуры "Электровоз" получаем дерево "Ошибки")
 - выходной плоской таблицы номенклатур

Замечания.

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


§ 4. Тест  по быстродействию. 

Чтобы оценка  быстродействия была предельно конкретной , в качестве среды выберем  - демонстрационную конфигурация БП 1.6(2.0)   и  представим   два  лёгких теста начального заполнения справочника "СпецификацииНоменклатуры", реализованных в обработке  "ЗапросПротиврекурсии.epf". Нижеприведенные тесты-"миллионники", надеюсь, с лихвой перекрывают все возможные случаи медленного "разузлования" в реальных задачах. Действительно , практически невозможно представить себе предприятия , на которых бы  справочник Номенклатура имел размер более 300 000 записей и  уровень графа, описывающего Спецификацию сложного изделия, превышал бы число 20.
Тест № 1. "Десять"
Справочник "СпецификацииНоменклатуры" содержит 6-уровневый 10-арный граф , имеющий 1 000 000 различных ветвей и при обходе такого графа таблица ВремТаблица6 на выходе цикла алгоритма содержит 1 000 000  записей. Но сам справочник "СпецификацииНоменклатуры" в своей табличной части содержит лишь 60 записей.
Проще говоря , корневому элементу подчинены 10 элементов, каждому из которых подчинен одинаковый набор из десятка следующих элементов и т.д.  

Тест № 2. "Два"
Справочник "СпецификацииНоменклатуры" содержит 20-уровневый бинарный граф , имеющий 1 048 576 различных ветвей и при обходе такого графа таблица ВремТаблица20 содержит 1 048 576  записей. Но сам справочник "СпецификацииНоменклатуры" в своей табличной части содержит лишь 40 записей.

Рис. 9. Быстрое (4-6 сек) создание тестового примера в обработке "ЗапросПротивРекурсии.epf"

Небольшой объём исходных данных в тестах №1 и №2 порождает иллюзию : сейчас загрузим всё в таблицу значений и в оперативной памяти всё "быстренько" порешаем с помощью рекурсии. Прозрение к любителю рекурсии приходит после замера времени выполнения. Автор провёл опрос среди знакомых специалистов и для Теста №1 получил следующую информацию (приводится обобщенно , со слов авторов) : Разузлование номенклатуры для Теста № 1  140-220 сек в файловом варианте. Понимая всю условность приведенной информации , автор  самостоятельно реализовал простейшую имитацию рекурсионного алгоритма :

Рис. 10. Имитация рекурсионного алгортима. Количество циклов 1 111 111 равно количеству узлов  в графе
          теста №1.

В этой имитации "ничего нет". В ней заведомо многократно меньше операторов ,  таблица значений пуста, затратный контроль зацикливания не осуществляется и т.д. Время выполнения этой имитации лишь на 15%-20% меньше времени выполнения обработки "ЗапросПротивРекурсии.epf" в тесте №1 . Стал очевиден качественный вывод : рекурсионный алгоритм проигрывает и проигрывает много.


Приведем результаты тестирования для обработки "ЗапросПротивРекурсии.epf". Замеры производились для "теплого"(второго) запуска обработки как в клиент -серверном, так и в файловом варианте. Нижние пределы диапазонов приведены как оценки значений, полученных на компьютере автора. Про верхние пределы диапазонов : скажем так , автору не удалось найти такие серверы и такие рабочие станции для файлового режима , на которых бы время выполнения было хуже. Итак , оценки (подчеркиваю , оценки) для "среднеофисных" серверов и локальных станций с оперативной памятью 1Гб.


Тест № 1 "Десять"     

Для файлового варианта

  25-60 сек    
Для клиент- серверного варианта   25-60 сек   


Тест № 2 "Два"     

Для файлового варианта

  60-150 сек
Для клиент- серверного варианта   120- 300 сек


Рис.11. Результаты тестирования.

§ 5. Для любопытных.

   
В статье ни слова не сказано  о сравнении по быстродействию с другими не-1совскими реализациями решения тестов №1и №2. А вдруг всё дело только в том , что 1с-овский интерпретатор неэффективен ? Может быть , если реализовать задачу на Си или Delfi, то   удастся достичь лучшего быстродействия, чем указано в теме ? Или , может быть , использовать "чисто" TSQL  ? Прогноз автора : НЕТ. НЕ ПОМОЖЕТ. Такая Рекурсия всё равно проиграет запросу 1с.  Но буду рад ,если появятся публикации на эту тему с другими мнениями.
Прошу только помнить, что в статье  идет речь не о "заточке" для тестов №1 и № 2, а об универсальной обработке произвольного графа ( в общем случае, циклического), которая " в среднем" оптимальна, на взгляд автора, для решения задачи "разузлования" на предприятии. Это значит , что таблица Спецификации может иметь миллионы записей и это существенно не скажется на быстродействии представленной обработки (в клиент-серверном варианте). Это значит также , что алгоритм различные графы и деревья , содержащиеся в таблице Спецификации, обрабатывает одинаково и априорно (на входе) не имеет  никакой "подсказывающей "информации о характере графа .

Второй вопрос , который никак не затронут в статье : как нам не попасть на "миллиард" ? как оптимизировать работу с повторениями элементов при "разузловании" ? Можно заметить ,в частности, что при отсутствии контроля зацикленности можно было вставить в демонстрационный запрос  "СГРУППИРОВАТЬ ПО " и тогда время выполнения по тесту № 1 было бы меньше 2 сек. Подход же с контролем зацикленности  сложнее, и, думаю, мало востребован в практических задачах учета.  "Миллиард"  оставим без рассмотрения. В обработке "ЗапросПротивРекурсии.epf" лишь применено ограничение на размер промежуточных временных таблиц.

§ 6. Заключение

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

Статья была уже написана , когда я на ИС получил информацию и поверхностно познакомился с подходами к задаче "разузлования" , применяемыми в  реальных, "вполне взрослых" проектах . Подходы эти  несколько смутили. Но не отменили главного вывода статьи : применение рекурсии в задачах "разузлования" ( в постановке см.§2) избыточно.


§ 7. Благодарности

Автор приносит благодарности всем участникам дискуссии , предшествующей появлению данной статьи :
Hogik ,Tango , Wkbapka , Арчибальд , Ildarovich, ILM. Эти авторы  разными способами и с разной силой толкали к пониманию новой для меня задачи "разузлования".Спасибо. 

Файлы

Наименование Файл Версия Размер Кол. Скачив.
ЗапросПротивРекурсии.epf
.epf 12,64Kb
14.01.11
349
.epf 12,64Kb 349 Бесплатно

См. также

Лучшие комментарии

179. ildarovich (файл скачал) 02.12.2010 12:48
(178) Игорь! Вы не выполнили условия нашего спора. Кроме мелких придирок к моей обработке не привели никаких аргументов в защиту своей позиции (прежде всего своих результатов сравнительного тестирование времени разузлования двух обработок на разных тестах). Как еще Вас стыдить, я не знаю. Желаю просто не отмахиваться от новых знаний. Если Вы воспользуетесь моими советами - сделаете свою обработку лучше. Ведь если бы Вы внимательно прочитали мою статью и приняли на свой счет, вы бы не сделали примитивной ошибки - не "попали на миллион". Независимо от результатов, решать задачу мне было интересно.

Для всех остальных (кто дочитал до конца) сообщаю (позиция обоснована в моих постах в этой теме):

ВЫВОДЫ СТАТЬИ О ПРЕИМУЩЕСТВАХ ПРИВЕДЕННОГО ЗАПРОСА ПРОТИВ РЕКУРСИИ - НАГЛАЯ И СОЗНАТЕЛЬНАЯ ЛОЖЬ!!!
Ответили: (179) (180) (181)
# Ответить
2. Арчибальд 23.11.2010 15:32
Все-таки хотелось бы цифирки получить... Но за неимением...
Функция СписДетей(Узел, Цепь);
	Рез = СоздатьОбъект("СписокЗначений");
	ТЗ_Дуги.ВыбратьСтроки();
	Пока ТЗ_Дуги.ПолучитьСтроку() = 1 Цикл
	    Если ТЗ_Дуги.Количество = 0 Тогда
	        Продолжить;
	    КонецЕсли;
	    Если ТЗ_Дуги.Отец = Узел Тогда
	        Если Найти(Цепь, ТЗ_Дуги.Сын.Код) > 0 Тогда
	            ТЗ_Дуги.Количество = 0; // Разорвали связь
	        Иначе
	            Рез.ДобавитьЗначение(ТЗ_Дуги.Сын.Код,""+ТЗ_Дуги.Количество);
	        КонецЕсли;
	    КонецЕсли;
	КонецЦикла;
	Если Рез.РазмерСписка() = 0 Тогда
	    Возврат "";
	Иначе
	    Возврат Рез;
	КонецЕсли;
КонецФункции
//__________________________________________________________­_________
Функция УдлиннитьЦепи(СписЦепей)
	Рез=СоздатьОбъект("СписокЗначений");
	Для й=1 по СписЦепей.РазмерСписка() Цикл
	    ТекСписок = СписЦепей.ПолучитьЗначение(й);
	    Поз.НайтиПоКоду(Прав(ТекСписок, 5));
	    Дети = СписДетей(Поз.ТекущийЭлемент(), Сред(ТекСписок,12));
	    Если ПустоеЗначение(Дети) = 1 Тогда//Цепочка закончилась, разузловываем
			
	    Иначе //СписокЗначений
	        Фин = Дети.РазмерСписка();
	        Для ё = 1 по Фин Цикл
	            лСтр = "";
	            Хвост = ";" + Дети.ПолучитьЗначение(ё, лСтр); 
Ннос = Формат(Число(Лев(ТекСписок,10)) *Число(лСтр),"Ч(0)10");
	            Рез.ДобавитьЗначение(Ннос+Сред(ТекСписок,11)+Хвост);
	        КонецЦикла;
	    КонецЕсли;
	КонецЦикла;
	Возврат Рез;
КонецФункции
//__________________________________________________________­_______
Процедура Разузловать()
	Для й = 1 по СЗ_Подграфы.РазмерСписка() Цикл  //Разузловываем сразу все корневые вершины
	     ТекСписок=СоздатьОбъект("СписокЗначений"); 
	    ТекСписок.ДобавитьЗначение(Формат(1,"Ч(0)10")+";"+СЗ_Подграфы.ПолучитьЗначение(й).Код);
	    Пока ТекСписок.РазмерСписка()<>0 Цикл
	        СледСписок = УдлиннитьЦепи(ТекСписок);
	        СледСписок.Выгрузить(ТекСписок);
	    КонецЦикла;
	КонецЦикла;
КонецПроцедуры
...Показать Скрыть


Это реализованный в http://infostart.ru/public/78032/ алгоритм получения всех цепочек в графе. Он вполне совпадает с алгоритмом в статье, однако не имеет отношения к запросам. Аналог временной таблицы (очередной) из статьи - это СледСписок (цепочек в графе). Функция СписокДетей - полный аналог Конструкции ВЫБОР (и остатка текста запроса). Разница в том, что в УдлиннитьЦепи у меня явным образом эти цепи перебираются, а у автора стоИт ВЫБРАТЬ (из временной таблицы) и ПОМЕСТИТЬ вместо моего ДобавитьЗначение.
Таким образом, словоформа "ЗапросПротивРекурсии" здесь, пожалуй, неуместна. Возможно, "ЗапросПротивЦикла" ?
Ну, а сравнение цикла (самого внешнего) с рекурсией - это совсем другая тема, подробно обсуждавшаяся в http://infostart.ru/public/20797/
Где-то тААк вООт...
Ответили: (7) (12)
+ 3 [ hogik; anig99; cool.clo; ]
# Ответить
164. ildarovich (файл скачал) 01.12.2010 12:46
(163) По настоянию Игоря сделал вариант программы, повторяющий "странное" поведение его обработки в случае, когда в спецификации указана номенклатура с нулевым количеством. Обработка Игоря зачем-то разбирает и такую номенклатуру. С Игорем трудно спорить - любое понимание задачи, отличающееся от его собственного, он тут же объявляет "ошибкой" и "прекращает тестирование". Ну а поскольку в данном случае моя обработка только упростится на один оператор "если", я решил согласиться. Нужная для сравнения версия моей обработки называется "Разузлование_БП_1_6_ПустышкиТянем". Она приложена к данному посту.

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

Чтобы не затягивать сериал, предлагаю параллельно проверить обработки на тесте "Матрешка" и заранее придумать объяснение тому, что "универсальная" обработка "запрос в цикле" не работает в конфигурациях, в которых коды номенклатуры не уникальны в пределах всего справочника.
Ответили: (165) (166)
# Ответить
152. ildarovich (файл скачал) 29.11.2010 21:39
(149) Если бы Вам пришлось тренироваться в прыжках с парашютом, прежде чем испытывать программу
управления навигационным комплексом самолета, Вы бы были осмотрительнее в выборе методов решения задач.
А бухгалтер - он и не такие издевательства стерпит.

В общем, пользователь Вам судья! Но я бы предпочел, чтобы Вы признали, что нельзя считать
запрос, который работает миллионы лет, победившим рекурсию
. И честно, без уверток написали об этом в своей статье.
Ибо, как говорят мои коллеги - "отрицательный результат - тоже результат".
Этот поступок был бы достоин уважения.
А так - извольте...
+ 2 [ Natgrey; hogik; ]
# Ответить
53. Арчибальд 25.11.2010 17:32
(28) Весь день отвлекали враги. Вот только теперь добрался до результатов.
Сразу оговорюсь: Таблицу, описывающую граф, я создаю не из справочника, а непосредственно. На тесте №1 замерить результат я не смог: он менее секунды. Тогда я к листьям из этого теста прицепил по 10 дуг со случайно выбранными концами (т.е. разузловываем не просто дерево, а с возможными циклами с 10 миллионами возможных путей длины 8). В этом случае разузлование длится около секунды, но заведомо меньше 2-х.
Работал локально, база ДБФ-ная. 1С не перезапускал. Одна хитрость: кроме ТЗ_Дуги я использовал ТЗ_Узлы с колонками "Отец" и "СписокДетей", т.е. описание графа избыточно, примерно как в первоначальном тексте http://infostart.ru/public/78032/
Прекращайте писать запросы!
Ответили: (54) (60) (61)
+ 1 [ hogik; ]
# Ответить
55. huse (файл скачал) 25.11.2010 17:48
А откуда вообще предпосылка, что рекурсия медленная? Ведь другими словами Вы хотите сказать, что вызов функции в 8-ке медленный.
Ответили: (57)
+ 1 [ hogik; ]
# Ответить
204. Ish_2 07.02.2011 20:03
(201) "если структуру табличек спроектировать под конкретные паровозы. ххх каждого паровоза - свою табличку."

Это путь в никуда. В этих табличках будут повторяющиеся агрегаты. И при изменении состава одного агрегата придется менять все таблички, в которые он входит.
+ 1 [ Lara.Builova; ]
# Ответить
128. ildarovich (файл скачал) 28.11.2010 19:54
(127) Игорь! Вы, наверное, не обратили внимания, но в (112) уже приведены результаты этого теста (в строке №3). На этом графе я запускал и Вашу и свою обработку, на ноутбуке и на сервере. Есть и обработка для формирования этого теста (прилагается к моей статье - нужно поставить галочку "дерево"). Во только почему у Вас все тесты имеют одинаковый номер? Я дал этому тесту №3. Обозначил его 1<10<10<10<10<10<10, имея ввиду, что "<" обозначает ветвление. Граф этого вида называется "дерево". Честно говоря, потратил много времени на оптимизацию программы именно для этого случая. Непонятно: до сих пор Вам это было непонятно? :o
То есть Вы вообще не читали мои посты: про ФОКУС, про деревья - это все про данный тест. :cry: Я писал их, зная результаты работы своей программы на этом тесте. Только вот, называя условия этого теста боевыми, Вы лукавите! - могу сослаться на Ваше же высказывание.
Ответили: (129) (130)
+ 1 [ hogik; ]
# Ответить
69. Арчибальд 26.11.2010 10:28
+68 Т.о. "запросно-лобовой" подход к задаче разузлования совпадает с подходом "что тут думать, трясти надо". И трясем 20 секунд. Мой же вариант - сначала полсекунды "подумать" (преобразовать представление графа), а потом за полсекунды разузловать его.
"Запрос в БД - это сила. Рекурсия - это зло ."
Может, рекурсия и зло. Иногда. Но запрос - отнюдь не всегда сила. В контексте статьи - это зло.
Ответили: (72) (83)
+ 1 [ hogik; ]
# Ответить
39. Ish_2 25.11.2010 06:57
(38)
В статье приведен взгляд автора на оптимальный алгоритм работы с графом, приведены результаты такого тестирования , которое доступно автору.
Прикреплен файл с реальной обработкой в реальной среде Демо-конфигурации БП 1.6.
Желающий может всё проверить .
Конкретная же цена Ваших альтернативных решений 140- 220 сек - слишком высока для мистера.

Что же до минуса ... Никаких обид.
+ 1 [ e.kogan; ]
# Ответить

Комментарии

1. ILM (файл скачал) 23.11.2010 14:51
Однозначно интересный подход, сейчас попробую его на реальных данных.
# Ответить
2. Арчибальд 23.11.2010 15:32
Все-таки хотелось бы цифирки получить... Но за неимением...
Функция СписДетей(Узел, Цепь);
	Рез = СоздатьОбъект("СписокЗначений");
	ТЗ_Дуги.ВыбратьСтроки();
	Пока ТЗ_Дуги.ПолучитьСтроку() = 1 Цикл
	    Если ТЗ_Дуги.Количество = 0 Тогда
	        Продолжить;
	    КонецЕсли;
	    Если ТЗ_Дуги.Отец = Узел Тогда
	        Если Найти(Цепь, ТЗ_Дуги.Сын.Код) > 0 Тогда
	            ТЗ_Дуги.Количество = 0; // Разорвали связь
	        Иначе
	            Рез.ДобавитьЗначение(ТЗ_Дуги.Сын.Код,""+ТЗ_Дуги.Количество);
	        КонецЕсли;
	    КонецЕсли;
	КонецЦикла;
	Если Рез.РазмерСписка() = 0 Тогда
	    Возврат "";
	Иначе
	    Возврат Рез;
	КонецЕсли;
КонецФункции
//__________________________________________________________­_________
Функция УдлиннитьЦепи(СписЦепей)
	Рез=СоздатьОбъект("СписокЗначений");
	Для й=1 по СписЦепей.РазмерСписка() Цикл
	    ТекСписок = СписЦепей.ПолучитьЗначение(й);
	    Поз.НайтиПоКоду(Прав(ТекСписок, 5));
	    Дети = СписДетей(Поз.ТекущийЭлемент(), Сред(ТекСписок,12));
	    Если ПустоеЗначение(Дети) = 1 Тогда//Цепочка закончилась, разузловываем
			
	    Иначе //СписокЗначений
	        Фин = Дети.РазмерСписка();
	        Для ё = 1 по Фин Цикл
	            лСтр = "";
	            Хвост = ";" + Дети.ПолучитьЗначение(ё, лСтр); 
Ннос = Формат(Число(Лев(ТекСписок,10)) *Число(лСтр),"Ч(0)10");
	            Рез.ДобавитьЗначение(Ннос+Сред(ТекСписок,11)+Хвост);
	        КонецЦикла;
	    КонецЕсли;
	КонецЦикла;
	Возврат Рез;
КонецФункции
//__________________________________________________________­_______
Процедура Разузловать()
	Для й = 1 по СЗ_Подграфы.РазмерСписка() Цикл  //Разузловываем сразу все корневые вершины
	     ТекСписок=СоздатьОбъект("СписокЗначений"); 
	    ТекСписок.ДобавитьЗначение(Формат(1,"Ч(0)10")+";"+СЗ_Подграфы.ПолучитьЗначение(й).Код);
	    Пока ТекСписок.РазмерСписка()<>0 Цикл
	        СледСписок = УдлиннитьЦепи(ТекСписок);
	        СледСписок.Выгрузить(ТекСписок);
	    КонецЦикла;
	КонецЦикла;
КонецПроцедуры
...Показать Скрыть


Это реализованный в http://infostart.ru/public/78032/ алгоритм получения всех цепочек в графе. Он вполне совпадает с алгоритмом в статье, однако не имеет отношения к запросам. Аналог временной таблицы (очередной) из статьи - это СледСписок (цепочек в графе). Функция СписокДетей - полный аналог Конструкции ВЫБОР (и остатка текста запроса). Разница в том, что в УдлиннитьЦепи у меня явным образом эти цепи перебираются, а у автора стоИт ВЫБРАТЬ (из временной таблицы) и ПОМЕСТИТЬ вместо моего ДобавитьЗначение.
Таким образом, словоформа "ЗапросПротивРекурсии" здесь, пожалуй, неуместна. Возможно, "ЗапросПротивЦикла" ?
Ну, а сравнение цикла (самого внешнего) с рекурсией - это совсем другая тема, подробно обсуждавшаяся в http://infostart.ru/public/20797/
Где-то тААк вООт...
Ответили: (7) (12)
+ 3 [ hogik; anig99; cool.clo; ]
# Ответить
3. Арчибальд 23.11.2010 15:56
6-уровневый 10-арный граф , имеющий 1 000 000 различных ветвей и при обходе такого графа таблица ВремТаблица6 на выходе цикла алгоритма содержит 1 000 000 записей.
Позволю себе не согласиться. По этой логике 2-уровневый 3-арный граф должен дать 9 записей. У меня гораздо больше получается... А циклов нет, прошу заметить.
Ответили: (6) (12)

Прикрепленные файлы:

Графин.PNG
# Ответить
4. ildarovich (файл скачал) 23.11.2010 16:40
(0) Игорь! Именно так я и представлял себе Ваше решение (по Вашим предварительным словам). Оставляйте "СГРУППИРОВАТЬ ПО"! - Именно это не дает экпоненциально расти времени работы Вашего алгоритма. А с контролем зацикливания лучше придумать что-либо другое! - Нужно просто оставлять во временной таблице пройденные узлы не в виде нарастающей строки пути, а как-либо по-другому...
Ответили: (5) (13)
# Ответить
5. Арчибальд 23.11.2010 16:49
(4) Не выйдет. Если мы не помним весь путь, то цикла не обнаружим.
Кстати, время там не по экспоненте растет, а еще круче. Факториально.
Ответили: (9) (13)
# Ответить
6. ildarovich (файл скачал) 23.11.2010 16:55
(3) Там, видимо, была оговорка. Имелся в виду не граф, а дерево. Корень дерева - нулевой уровень.
Ответили: (8)
# Ответить
7. Ish_2 23.11.2010 16:57
(2) Твой код я посмотрю. А пока так:

Я уже писал тебе , что алгоритмов работы с графом - "тьмы и тьмы и тьмы " . Сами по себе эти алгоритмы , как и представленный в этой статье, - очевидны , просты , НЕИНТЕРЕСНЫ. За месяц я просмотрел "тучу" алгоритмов - образцовых, доморощенных, школьных. Если хочешь , еще раз пройдусь по интернету и вышлю тебе сколько нужно похожих алгоритмов : 2 ? 5 ? 10 ? Так вот .
Это истоптанная вдоль и поперек поляна и говорить о первенстве или об авторстве просто смешно .Перебирая реализации , независимо от того "на чём" ? я задавал только один вопрос : "Сколько секунд на тест № 1 ?" . Получал ответ , и говорил автору "спасибо, не нужно."
Цель этой публикации - не изобрести НОВЫЙ алгоритм, а решить "узко-конкретный" вопрос :

КАКИМ ДОЛЖЕН БЫТЬ В СУБД САМЫЙ БЫСТРЫЙ , САМЫЙ НАДЕЖНЫЙ АЛГОРИТМ РАБОТЫ С ГРАФОМ ? И КАК ЕГО РЕАЛИЗОВАТЬ ?

Я ответил на него как мог.
Ответили: (10)
# Ответить
8. Арчибальд 23.11.2010 17:01
(6) Ну нет, автор постоянно в обсуждениях подчеркивал произвольность графа. Если бы речи шла о дереве - можно было бы организовать обход "вглубь" и помечать пройденные дуги. Сложность тогда почти пропорциональна количеству узлов/дуг.
# Ответить
9. ildarovich (файл скачал) 23.11.2010 17:07
(5) Я имел ввиду помнить не путь, а пройденные вершины - порядок ведь не важен, но эту мысль еще нужно обдумать.
По поводу роста времени я имел ввиду не рост в зависимости от числа уровней, обусловленной природой задачи, а дополнительный рост времени, обусловленный тем, что мы не сворачиваем таблицу после каждой итерации... хотя, Вы, наверное, правы.
# Ответить
10. Арчибальд 23.11.2010 17:08
(7) Конечно же речь не о первенстве/авторстве. У себя я указываю, что алгоритм стандартный. Соответственно, у тебя тоже. А вот сколько таки секунд на тест #1 получилось? Иначе говоря, насколько создание временной таблицы и обход ее запросом быстрее/медленнее создания в памяти массива и обьхода его в цикле?
Ответили: (11) (26) (84)
# Ответить
11. Ish_2 23.11.2010 17:34
(10) Робею отвечать . Вроде бы старался в теме отобразить все параметры теста №1.
Для тебя лично :

На твоем компьютере (если в нем более 1 Гб оперативной памяти)
в файловом варианте в демонстрационной конфигурации 1сv8 БП 1.6 или БП 2.0 время
выполнения теста №1 "Десять" 25 - 60 сек. (неофициально надеюсь , на 18 сек как у меня )

P.S. На всякий случай, просмотрел тему (у меня IE8) - там четко написано и выделено Жирным щрифтом Тест № 1 "Десять", далее идет таблица с результатами тестирования , в первой строке таблицы две колонки :
файловый вариант --------------------- 25 -60 сек
# Ответить
12. Ish_2 23.11.2010 17:59
(2),(3) Хм... Постарался внимательно перечитать еще раз .
Судя по всему , мы говорим каждый о чем - то своём.
В каждом предложении комментарии (2) , уверен , непонимание настолько зашкаливает , что я даже не знаю с какого места начинать разговор.
# Ответить
13. ildarovich (файл скачал) 23.11.2010 18:12
(4) (5) Поторопился с выводами. Действительно, пока не придумывается как совместить контроль зацикливания и "сгруппировать по" в предложенном запросе.
Но! - Это легко контролировать при записи каждой спецификации! Так что такой контроль нужно просто перенести в другой модуль - вот такое решение!
Ответили: (14)
# Ответить
14. Ish_2 23.11.2010 18:30
(13) В статье я неслучайно отказался от рассмотрения этого вопроса:

Как же сделать , какие предусмотреть дополнительные структуры (справочники), которые :
1. Автоматически изменяются при записи элемента спецификации (изменении узла графа).
2. Обладают "ускоряющими " свойствами при построении графа.
Здесь возможны варианты и варианты. Думаю , это тема отдельного разговора.
Пока выяснять это рано.

( для меня , конечно, потому что я не знаю возможно ли здесь общее решение без привязки к конкретной задаче (конкретному виду графов)).
# Ответить
15. hogik 23.11.2010 19:39
(0)
Ставлю "плюс" на сообщение (2) от Александра (Арчибальд) - ВСЁ сказано.
Однако, автору рекомендую:
1) Провести замеры не для "теплого" запуск своего алгоритма.
2) Подсчитать реальное количество операций ввода/вывода на сервере.
3) Вспомнить, что индексная структура таблицы БД уже есть - "дерево".
Скажу грубо.
Проведено, в очередной раз, тестирование эффективности кэширования системы ввода/вывода ОС-а (для файлового режима) и СУБД (для клиент-серверного режима).
Хотя, я полностью согласен с утверждение автора:
"...встроенных возможностей платформы 1с...вполне достаточно..."
для тех задач, для которых ОНО предназначено. ;-)
P.S.
Поправка к "Автор провёл опрос... для Теста № 1...140-220 сек.".
Без использования 1С.
Для файлового варианта: 35 сек.
Для клиент- серверного варианта: 70 сек.
Алгоритм - тупой обход "дерева" рекурсией или циклом (не имеет значения).
И это время не зависит от "вида дерева".
Рабочих таблиц в алгоритме не создаётся.
Исходная таблица не подвергалась "ревизии".
Т.е. никаких дополнительных полей, индексов, фильтров и т.д. - не создавалось.
Ответили: (16) (31)
+ 1 [ TriD; ]
# Ответить
16. Ish_2 23.11.2010 20:26
(15) Допускаю, что я что-то не понял в посте Арчибальда. Может быть. Но повторяю, меня не интересуют алгоритмы ,как таковые. Меня интересуют объективные тесты.

Теперь, к сожалению , о более общих вещах.
Для кого-то совершенно очевидных , для кого -то - нет.

Владимир , поверьте мне - не мы первые спорим в этом мире .
Размышлизмами можно делиться до бесконечности.

За тысячи лет человечество выработало некие правила, азы ведения споров, выяснения ,(пусть и несовершенного) некоторого приближения к истине.

Первое правило : наличие критерия. Я его предложил в теме : тест №1 и тест № 2 и вопрос СКОЛЬКО ?
Если Вы его не принимаете ( имеете право !), то предлагайте свой или закончим.
Если принимаете то :

Приводите результаты тестирования :
Ваш вариант (кратко какой ) :
1. Номер теста .
2. Время выполнения.
На той же машине - мой вариант (файловый или клиент -серверный) :
1. Номер теста .
2. Время выполнения.

На одной одной машине объективно сравниваются два разных решения.
Сравнение - есть основа анализа. Никакого анализа без сравнения быть не может .
Вы понимаете ?

Приводить одни результаты без приведения результатов для альтернативного варианта - бессмысленно. Если результаты будут сочтены интересными обеими сторонами, то стороны разбираются и выясняют, как могут, истину.
Но вначале ( Внимание !) не размышлизмы, а факты. Вы готовы к такому конкретному разговору ?

Если что-то показалось обидным - то виноват .
Но как еще проще объяснить , совершенно очевидные вещи - я просто искренне не знаю. Мы играем по правилам , или мы не играем вовсе.
Ответили: (17) (19)
# Ответить
17. hogik 23.11.2010 21:53
(16)
Игорь.
Вы не читаете мои сообщения. :-(
1) "На одной одной машине объективно сравниваются два разных решения."(с)
С самого начала обсуждения я Вам сказал, что сравнивать абсолютными величинами - бред. Сказал Вам, что еще и разные среды программирования, разные СУБД, разные ОСы и т.д. Нет! Вы упорно хотели получать от меня абсолютные величины. Вы их получили...
И вы теперь меня спрашиваете: "Вы понимаете ?"(с)
2) "...меня не интересуют алгоритмы ,как таковые. Меня интересуют объективные тесты"(с)
Тесты - чего? Тесты "результатов"?
3) "Сравнение - есть основа анализа. Никакого анализа без сравнения быть не может."
Вам на протяжении всей темы про запросы предлагалось сравнивать.
4) "Вы готовы к такому конкретному разговору ?"
Я, давно, с Вами веду конкретный разговор. И не получаю ответов на самые просты вопросы. Ну хоть на пункт #2 из сообщения #15 - дайте ответ.
5) В моём сообщении #15 есть "P.S.", как замечание к конкретным данным из Вашей публикации. Но есть и другой текст. Вы его прочли?
Ответили: (18)
# Ответить
18. Ish_2 23.11.2010 23:12
(17) Понятно.
# Ответить
19. ildarovich (файл скачал) 24.11.2010 00:23
(16) Игорь!
Как говорится: "Платон мне друг, но истина дороже!" -
Я переписал свой алгоритм Как не попасть на миллион на Ваш случай - типовую БП (хранение спецификаций в отдельном справочнике).
У меня получилось (только файловый вариант):
Тест №1 - 0,468 сек.
Тест №2 - 0,172 сек.
Как будете проверять?
Вообще я приложил к своей статье внешний отчет для БП, но сам его на БП не проверял (у меня в базе только минимум объектов).
Ответили: (20)
# Ответить
20. Ish_2 24.11.2010 06:55
(19) Отлично.
Давайте договоримся о сценарии тестирования и сравнения.
Итак, сравниваются две универсальных обработки работы с графом

Первое. Нужно выбрать площадку(среду) для сравнения.
Предлагаю демо-конфиграцию БП 1.6 или БП 2.0.(как самую распространенную конф-ию) .Она должна быть у Вас и у меня.
Второе. У Вас и у меня должны быть сравниваемые внешние обработки.
Обе обработки должны быть тщательно отлажены и проверены авторами в БП1.6(2.0).
Чтобы не было возгласов "Ой! я тут исправлю - ой! тут не проверил".
Т.е. по-врослому.
Третье.Авторы обмениваются произвольными тестами заполнения Справочника СпецификацииНоменклатуры и сравнивают результаты тестирования.

Если три пункта (совершенно очевидных) принимаются, то начинаем .

Если ДА, то первым тестом от меня будет граф 1-10-10-10-10-10-10 со всеми уникальными значениями. Ведь у нас с Вами не заточки под тесты №1 и №2, а универсальные обработки для работы с графом. А для универсальных обработок
первое свойство - работоспособность и устойчивость. Вначале его проверим , а потом уж будем соревновать в скорости.
Договорились ?
Ответили: (21)
# Ответить
21. ildarovich (файл скачал) 24.11.2010 09:40
(20) Договорились.
1. БП 1.6.
2. Мне потребуется денек (отвлекают тут меня) на тщательную отладку (на всякий случай).
3. Согласен.
4. Первый тест принимается.
5. Еще хотелось бы электровоз найти. Хотя бы без наименований в виде списка (Код-Код-Количество).
5. Приз - "плюсик" к статье от проигравшего победителю.
6. Разумные сроки на ответы (не часы).
Ответили: (22)
# Ответить
22. Ish_2 24.11.2010 09:48
(21) Отлично.Принимается.
Какой вариант выберем в качестве основного ?
Файловый или клиент-серверный ?
(обычно сравнения и тесты делаются для клиент-серверного варианта , как более устойчивого и предсказуемого на больших объёмах, но - дело Ваше)
Ответили: (23)
# Ответить
23. ildarovich (файл скачал) 24.11.2010 10:15
(22) Файловый, если результаты не будут очевидно разными. Тогда решим заново.
(просто у меня трехзвенка только на работе)
Ответили: (25)
# Ответить
24. m_001 24.11.2010 10:16
Надеюсь автор не будет возражать ;) , если добавлю версию для УПП 1.3.5.1. на платформе 8.2. Просто мы давно перешли на УПП и работаем только с ним.
Так что посмотрите обработку для УПП в прикрепленном файле.
Разузлование проходит быстро, ошибки зацикливания тоже ищутся.
Ответили: (29) (30)

Прикрепленные файлы:

ЗапросПротивРекурсии_v82.epf
# Ответить
25. Ish_2 24.11.2010 10:27
(23) Отлично.
Теперь об удобстве сравнения и анализа. Сравниваемые обработки должны обладать таким развитым интефейсом,
чтобы пользователь мог быстро интерактивно проверить созданный граф, внести специальные ошибки и посмотреть результат. Не буду же я гадать правильно ли создан огромный граф рассматриваемой обработкой или нет ?
Т.е. я это должен сделать интерактивно как пользователь , а не ковыряя чужой код, и не ломая голову над созданным графом в виде таблицы.
Иначе пустые споры : "правильно-неправильно" затянутся , как у меня с Владимиром.
Предлагаю (но не настаиваю) скачать обработку ЗапросПротивРекурсии.epf и посмотреть как в ней решены вопросы контроля и какие созданы средства для быстрой проверки.
Еще раз - мы рассматриваем вопрос как создать удобные и быстрые средства контроля и анализ ошибок , а не сам алгоритм (он у каждого свой). Грубо говоря - договоримся и создадим оснастку
Ответили: (89)
# Ответить
26. Ish_2 24.11.2010 10:45
(10) Ты уж уважь... Напиши сколько длится в твоей реализации Тест №1 на 77 на твоей машине, и если есть у тебя демо-конфигурация БП 1.6(2.0) , то сколько в ней длится тест №1 для обработки "ЗапросПротивРекурсии.epf".
Т.е. предлагаю обмениваться числовыми характеристиками.
Тогда всё упростится и истина , надеюсь, станет ближе.
Ответили: (27)
# Ответить
27. Арчибальд 24.11.2010 12:15
(26) ОК. Займусь. Сделаю регулярное дерево и попробую. Чуть позже.
Ответили: (28)
# Ответить
28. Ish_2 24.11.2010 12:32
(27) Спасибо. Но на всякий случай... А то тут у нас Сергеем как-то вышло недоразумение.
Обработка твоя должна быть универсальной , т.е. не "заточкой" для теста №1 с известной регулярной структурой, а эффективной для любого графа. Это значит , и то что алгоритм твой при начале работы - ничего не знает ( не обладает априорной информацией) о характере графа.
Извиняюсь , если обидел таким разжёвыванием.
Ответили: (53)
# Ответить
29. Ish_2 24.11.2010 14:29
(24) Пропустил Ваш пост. Сообщение мне на e-mail чего -то не пришло. Виноват. Посмотрю.
# Ответить
30. Ish_2 24.11.2010 14:42
(24) УПП у меня - нет . Но насколько я слышал , там должен быть Регистр где содержится ОсновнаяСпецификацияНоменклатуры. Т.е. спецификаций у номенклатуры может быть несколько. В моей же обработке они все сольются в одну, если их несколько. Это нездорово.
Поэтому , строго говоря , в код обработки должны быть внесены изменения :
во временную таблицу Спецификации (процедура КнопкаВыполнитьНажатие()) должны копироваться не все спецификации , а только те, для которых установлено в регистре что это основная спецификация . Примерно так .
Если сможете сделайте - я выставлю в теме это как Ваш файл .

И еще одна просьба : приведите , пожалуйста пример насколько быстро разузловывается "самая большая Ваша номенклатура".
# Ответить
31. Ish_2 24.11.2010 18:17
(15) Высылаю обещанное.
Ответили: (32) (33)

Прикрепленные файлы:

ТаблицаТестовДля Владимира.xls
# Ответить
32. hogik 24.11.2010 21:18
(31)
Игорь.
Спасибо за замеры.
Однако в этих замерах "SQL сервер не перезапускался"(с).
Т.е. такие замеры меня не интересуют.
(0)
По публикации.
Автор, в очередной, раз доказал (показал) что один запрос лучше, чем много. ;-)
Для этого была выбрана одна из самых неудобных задач в теме реляционных СУБД - обход дерева. Добавлено несколько дополнительных условий, усложняющих решение задачи методом простого обхода дерева - проверка цикличности, подсчет "изделий". Использовались термины не относящиеся к сути задачи - "рекурсия", "разузлование", "спецификация". При сравнении различных методов (не алгоритмов!) обработки информации применялись подтасовки фактов. Например: замеры от разных людей в разных средах, самостоятельное "тестирование" рекурсии...
И сделан очевидный вывод, что лучше когда вся "тяжесть вычислений (99.9%) ложится на сервер БД"(с).
Автор не утруждается анализом "процессов" происходящих на сервере. Типа, "с глаз долой из сердца - вон". На мои просьбы провести "подсчет" количества операций ввода/вывода на сервере - не отвечает. Вопрос кэширования на стороне сервер автора не интересует. Допустим, мы выделили каждому пользователю свой сервер. Или поставили один - ооо-чень мощный компьютер (сервер). Но выделить каждому пользователю свою базу данных у нас, не очень, получится. Т.е. задача сервера - не только обеспечивать "мощей" пользователей, а еще и обеспечивать доступ к общим данным. И это одна из важнейших задач сервера БД. В разных СУБД (и их ЯМД) используются различны инструменты для обеспечения пользователям "одновременный" доступ к информации. Кроме самих инструментов СУБД используются еще и "смысловые" приемы при разработке приложений - специфичная схема БД, разбиение задачи на "отчет" (только чтение) и обновление, интерактивный или пакетный режим и т.д.
К чему, я это всё.
А к тому, что автору имеет смысл определиться - он "обход дерева" делает для отчета (выходной формы) или еще для чего. Судя по выбранным инструментам (запрос) - для отчета. Отчета для подсчета количества "изделий в спецификации". Посчитали - напечатали. А если в момент подсчета другой пользователь изменил "дерево"? Нельзя такое допускать в выбранном автором алгоритме раскручивания дерева (или можно?). Решения два - блокировать всю исходную таблицу, ведь "мы ничего не знаем о дереве"(с) или создавать полную копию исходной таблицы, блокируя ей на момент копирования. Первое - понятно. Т.к. 20 секунд блокировки при множестве желающих работать (не только отчетами) с "деревом" - многовато... Второе - лучше. Благо таблица маленькая и копируется только средствами центральной машины. Но тогда это "чистый отчет". Т.е. никакого воздействия данными отчета на исходную таблицы БД - невозможно. Но тогда почему её не передать клиенту, и не сделать обработку на машине пользователя любым, красивым, методом. Передача - один запрос, по сети за две секунды (для таблицы в 1111111 записей), а без сети - 1 секунда.
Но в реальной жизни с иерархическими структурами НАШИХ задач работает множество пользователей одновременно (интерактивно). Одни смотрят, другие обновляют. И СУБД должна обеспечивать всех пользователей достоверной информацией. Способы такого обеспечения известны - блокировки. Но это другая тема. ;-) В этом важно только одно - быстрое чтение/обновление минимального количества узлов дерева за одну "транзакцию". Т.е. в запросной технологии - запрос на узел дерева (грубо говоря). Без запросной технологии "чтение/обновление" узла без запроса. ;-) Но т.к. алгоритм обработки гораздо сложней чем подсчет изделий, то осмелюсь предположить, что на обработку одного узла придется выполнять либо множество запросов, либо осуществлять его обработку на стороне клиента.
Т.е. подводя итог моему, сумбурному, изложению предлагаю тему "Мы пишем запросы" переименовать в "Мы пишем отчеты запросами". А для отчетов самое оно - использовать запросы. Нужно только изменить схему базы данных под этот инструмент. Что в продуктах 1С и сделано. И никаких задач типа "обход дерева", "нарастающие итоги" и т.д. Для НАС таких задач просто не существует... ;-)
Ответили: (37)
# Ответить
33. hogik 24.11.2010 22:48
(31)
Про Ваши замеры - "специально для меня".
По поводу строчки "вылетело SQL".
На "моей" СУБД стартовый объем занимаемой памяти - 254 мегабайт.
В процессе обхода дерева в миллиард вершин дошло до 320 мегабайт.
Рабочих таблиц не использую... ;-)
# Ответить
34. WKBAPKA 25.11.2010 00:15
ребята, я уже попкорн весь съел... это у вас из серии: что первым было, курица или яицо? ;)
Ответили: (70) (183)
# Ответить
35. WKBAPKA 25.11.2010 00:26
на самом деле, всегда эффективнее будет работа с памятью... запросы от платформы к платформе могут иметь разную производительность, все зависит от реализации... работа же с памятью практически всегда будет эффективнее ... объем информации в данном случае не имеет значение, т.к. на себя эту задачу берет операционная система... ко всему прочему, как описывается в некоторых учебниках по запросам к 1С, когда запросы преобразовываются в TSQL могут быть выбраны разные планы, в этом случае запрос может выполняться часами... имхо, то что я читал... отсюда могу сделать вывод, что решать данную задачу запросами будет не эффективно, с точки зрения скорости...
Ответили: (36)
# Ответить
36. hogik 25.11.2010 00:56
(35)
"работа же с памятью практически всегда будет эффективнее ... объем информации в данном случае не имеет значение, т.к. на себя эту задачу берет операционная система..."(с)
Ярослав.
Поиск волшебных палочек продолжается? ;-)
У Игоря - "запросы". У Вас - "операционная система".
В моём сообщении #33 не опечатка в части количества записей.
Т.к. у меня формат таблицы от "1С 7.7", то это около 77 гигабайт.
В "1С 8.х", думаю, размер записи больше будет.
Читайте таблицу в память, считайте время закачки, покупайте новый "сервер"...
Ответили: (40)
# Ответить
37. Ish_2 25.11.2010 05:30
(32)
- Почём твоя скотина , ковбой ?
- Что Вы знаете о скотине , мистер ... В далекие времена , когда воды Миссисипи были полны и скотина бегала сама по себе...
- Почём твоя скотина , ковбой ?

Понятно , что мистер ничего не знает о скотине, а ковбою есть что сказать о труде животновода и вопрос о качестве мяса ой-как непрост .
Но нужна числовая характеристика в виде цены как некий ориентир, стоит ли продолжать разговор ?
Нужно узнать хотя бы порядок цены . Рассказ животновода о качестве скотины , как он его понимает, можно потерпеть и послушать в одном случае - когда объявляется цена в приемлемом диапазоне. Понимая , что вопрос быстродействии каждого алгоритма очень непрост , тем не менее нужен какой-то ориентир , начальный критерий отбора для реализации решения конкретной задачи "разузлования". Этот критерий - время исполнения по тесту № 1 должно лежать в диапазане 15-30 сек для "среднеофисных"
рабочих станций и для "среднеофисных" серверов. Пусть грубо, пусть много"НО" - но критерий есть.
Почему такой ? - потому что, тогда в реальных "немиллионных" задачах быстродействие
будет более, чем удовлетворительным.
А теперь подумайте , будет ли "мистер" слушать рассказы о непростой работе сервера при объявлении "цены" алгоритма в 200 сек, когда нужно 20 ?
Не судите строго "мистера", когда он обрывает собеседника :

Так, почём твоя скотина, ковбой ?
Ответили: (38)
# Ответить
38. hogik 25.11.2010 06:42
(37)
Игорь.
Вы всё о "числах" говорите.
А я Вам говорю, что Ваш алгоритм не работает.
Что толку считать за 20 секунд на тестовой задаче.
Примеряться к реальной 20/10=2 сек., если он НЕ РАБОТАЕТ.
Я Вам выдал все замеры с пояснение - где работоспособный алгоритм проигрывает. Дал заранее (!!!) опровержение Вашего утверждения про "что 1с-овский интерпретатор неэффективен ?"(с) Пояснил, на пальцах, почему используется в реальных задачах обход дерева "по всем вершинам". Попросил Вас провести замеры Вашего алгоритма в реальных условиях - мимо. Выдал "числа" близкие к "заветному числу", но для работоспособного алгоритма - мимо. И т.д.
Я не ставлю "минусы" за реально проделанную работу автором.
Ставил "минус", только, на публикации украденные или нарушающие правила ресурса.
Но за такую "работу" поставлю.
Халтура и верхоглядство это.
Да еще и с элементами откровенного вранья.
Только не понимаю - зачем Вы это делаете... :-(
Ответили: (39)
# Ответить
39. Ish_2 25.11.2010 06:57
(38)
В статье приведен взгляд автора на оптимальный алгоритм работы с графом, приведены результаты такого тестирования , которое доступно автору.
Прикреплен файл с реальной обработкой в реальной среде Демо-конфигурации БП 1.6.
Желающий может всё проверить .
Конкретная же цена Ваших альтернативных решений 140- 220 сек - слишком высока для мистера.

Что же до минуса ... Никаких обид.
+ 1 [ e.kogan; ]
# Ответить
40. WKBAPKA 25.11.2010 09:11
2(36): причем тут волшебная палочка ? я имел ввиду, что все что касается работы с памятью прикладным программистам не доступно, что за это отвечает операционная система и что код будет работать быстрее, если это будет работа с массивами данных в памяти, а не запросы...
Ответили: (41) (60)
# Ответить
41. Ish_2 25.11.2010 09:38
(40)
"код будет работать быстрее, если это будет работа с массивами данных в памяти, а не запросы..."


Истин общих - нет.
Если рассматривать вопрос в контексте данной темы , то в статье как раз и показано что запрос эффективнее, чем использование рекурсии в оперативной памяти. И намного.
См. Рис.9 в теме.
# Ответить
42. huse (файл скачал) 25.11.2010 09:48
(0) Если сделать рекурсию с кэшем - это будет самое быстрое разузлование. Так как задача разузловки для каждого вида узла будет решаться только один раз.

ЗЫ И вообще некорректно сравнивать рекурсию с запросами. Запрос - это выборка из БД. Рекурсия - это способ перебора различных списков. Можно пользоваться запросами вместе с рекурсией. Рекурсия дает минимальный и прозрачный код. Перебор не очень очевиден и удобен - посмотрите сколько строк вы написали, чтобы сделать обход дерева. Если говорить о скорости - иногда приходится отказываться от рекурсии, но не всегда и не обязательно.

ЗЗЫ. Если говорить о задаче разузловки - я бы использовал рекурсию, запросы и кэш (либо ввиде временной таблицы, либо ввиде соответствия).
Ответили: (43)
+ 1 [ hogik; ]
# Ответить
43. Ish_2 25.11.2010 10:08
(42)
Если сделать рекурсию с кэшем - это будет самое быстрое разузлование.

Как гипотеза - принимается.
Добиться каких-то практических результатов от специалистов по TSQL не удалось.
Сам испытываю от такого подхода предельный скепсис, но буду рад , если появятся какие-то решения уже скорее не на ИС.
Ответили: (44)
# Ответить
44. huse (файл скачал) 25.11.2010 10:18
(43) Я решал подобную задачу на 7.7 - деталей было около 3-х тысяч. Глубина примерно 5-6 узлов (диван, модуль, каркас, элемент каркаса, деталь, технологическое объединение деталей, материал). Переход от плана производства диванов до потребности в сырье делался около 5-10 минут (за давностью уже не помню). В качестве кэша использовал СписокЗначений.
Ответили: (46) (51)
# Ответить
45. SatanClaws 25.11.2010 10:24
ТекстЗапроса = "
|SELECT '" + РадугаСервис.ЗначениеВСтрокуБД(ЗначениеФильтра) + "' ID Into " + ИмяВремТаблицы + "
|
|While @@RowCount > 0
|INSERT INTO " + ИмяВремТаблицы + "
|SELECT
| Спр.ID
|FROM
| $Справочник." + ЗначениеФильтра.Вид() + " Спр
| LEFT JOIN " + ИмяВремТаблицы + " ВремТаб (NoLock) on ВремТаб.ID = Спр.ID
|WHERE
| ParentID In (SELECT ID FROM " + ИмяВремТаблицы + " (NoLock))
| And ВремТаб.ID Is Null
|
|If (SELECT Count(*) From " + ИмяВремТаблицы + " (NoLock)) > 100
| Create Index " + СтрЗаменить(ИмяВремТаблицы, "[#", "[#IX_") + " on " + ИмяВремТаблицы + " (ID)
|";


Это, кстати, от неявной рекурсии принципиально мало чем отличается....

Но за популяризацию идеи - несомненно плюс.
Ответили: (67)
# Ответить
46. Ish_2 25.11.2010 10:28
(44) Что-то подобное делал и я , лет 8-9 назад. Глубина такая же 5-6.
Но от рекурсии отказался из-за тормозов и не поленился написать вложенный 6 раз цикл.
Так было быстрее. Правда , потом оказалось , что одно изделие имеет уровень 7...

Если же перейти к реализациям на 1с8 , то думаю , здесь рекурсии делать просто нечего. Огромный проигрыш. Известные мне реализации проигрывают поуровневому обходу графа "в лоб" (сверху-вниз) , описанному в теме , от 7 до 10 раз.
Ответили: (47)
# Ответить
47. huse (файл скачал) 25.11.2010 11:50
(46) я так же - сначала написал тупую рекурсию. считало ж-у-у-у-тко долго. по-раскинул мозгами - проблема была в повторных расчетах узлов. добавил кэш и все сильно-сильно ускорилось.
Ответили: (48)
# Ответить
48. Ish_2 25.11.2010 12:26
(47) Ну , мнений-прогнозов может быть как угодно много.
Мой прогноз : в 1cv8 c кэшем ли , без кэша ли, с повторным расчетом узлов (хотя не могу себе такого представить), без повторного расчета узлов (только так ,разумеется) рекурсионный подход проигрывает. Проигрывает жестоко , безнадежно.
Да , ладно бы речь о каких-то блохах, скажем,
рекурсионная реализация на "миллионном" тесте № 1 дала 40 сек против 20 сек (всего лишь в 2 раза).
Тут многое можно оспорить в условиях эксперимента , можно привести миллион причин почему это произошло
и требовать пересмотра условий. Даже 80 сек (в 4 раза)еще не дает гарантий. Но 140 сек(в 7 раз) - это перебор.

С другой стороны , конечно , это всего лишь эксперимент одного автора на ИС . И не более того.
В свободное время, смеха ради попробуйте реализовать Тест №1 и запустите свою обработку графа.
Может быть , Вы меня опровергнете ?
Опубликую в теме сразу : так мол и так, Huse доказал... и опроверг все построения автора.
Обещаю.
Ответили: (49)
# Ответить
49. huse (файл скачал) 25.11.2010 12:53
(48) а твоя обработка требует разузлование.dt?
Ответили: (50)
# Ответить
50. Ish_2 25.11.2010 12:58
(49) Виноват , не понял. Что такое разузлование.dt ?
Моя обработка запускается в любой конфигурации БП1.6(2.0) для платформы 1с8.
Ничего не требует. По кнопке запускается тестовое заполнение миллионного теста и "кнопка выполнить". Всё. См. Рис.9 темы.
Ответили: (56)
# Ответить
51. cool.clo 25.11.2010 13:18
(44) Абсолютно похожим образом решал немного другую задачу - необходимо было нескольких сайтах свести номенклатуру, отсортировать по всем вложенным категориям(их где-то 6-7) и внести для всех общую артикулизацию. Также делал кэш (в смысле тоже СписокЗначений). Действительно с кэшем было веселее(когда я его сделал сам поначалу удивился как быстро). НО! Номенклатуры всего-то было тысяч 20..., поэтому я думаю рекурсия здесь не самый оптимальный метод. Согласен с Ish_2. В 1С я думаю этот метод просто не самый быстрый. (имею ввиду 8, поскольку с 7.7 не имел дела, вообще раньше делал небольшие учетные программки на Delphi (+SQL). 1С в функционале просто беспощадно выигрывает, но вот скорость надо сказать - вопрос кто выигрывает спорный, несмотря на то, что программы совершенно разные , да и программист я не ахти. )
# Ответить
52. kim241 (файл скачал) 25.11.2010 13:22
В рекурсивном примере добавьте индекс для таблицы значений и скорость резко взлетит ;)
# Ответить
53. Арчибальд 25.11.2010 17:32
(28) Весь день отвлекали враги. Вот только теперь добрался до результатов.
Сразу оговорюсь: Таблицу, описывающую граф, я создаю не из справочника, а непосредственно. На тесте №1 замерить результат я не смог: он менее секунды. Тогда я к листьям из этого теста прицепил по 10 дуг со случайно выбранными концами (т.е. разузловываем не просто дерево, а с возможными циклами с 10 миллионами возможных путей длины 8). В этом случае разузлование длится около секунды, но заведомо меньше 2-х.
Работал локально, база ДБФ-ная. 1С не перезапускал. Одна хитрость: кроме ТЗ_Дуги я использовал ТЗ_Узлы с колонками "Отец" и "СписокДетей", т.е. описание графа избыточно, примерно как в первоначальном тексте http://infostart.ru/public/78032/
Прекращайте писать запросы!
Ответили: (54) (60) (61)

Прикрепленные файлы:

Миллион.PNG
+ 1 [ hogik; ]
# Ответить
54. Ish_2 25.11.2010 17:44
(53) Честно сказать , ничего не понял.
Я полагал , что постановка аналогична той что в текущей теме . Дана таблица значений:
Владелец, Номенклатура, Количество - задается начальный корень "владелец" и всё - поехали !

Или
Родитель, Ребенок , количество - задается начальное значение Родитель" и всё !

Ты уж тогда опиши , что у тебя задано и что нужно найти.
Или представь обработку .ert
Для меня то , что ты написал полный ребус.
Ответили: (58)
# Ответить
55. huse (файл скачал) 25.11.2010 17:48
А откуда вообще предпосылка, что рекурсия медленная? Ведь другими словами Вы хотите сказать, что вызов функции в 8-ке медленный.
Ответили: (57)
+ 1 [ hogik; ]
# Ответить
56. huse (файл скачал) 25.11.2010 17:50
(50) понял - вечерком разверну - сделаю свой вариант в твоей обработке.
Ответили: (57)
# Ответить
57. Ish_2 25.11.2010 17:53
(55) Строго говоря , прав только опыт. И чем больше опытов - тем лучше.
(56) Ага. Так легче будет разбираться.
# Ответить
58. Арчибальд 25.11.2010 18:19
(54) Дана ТаблицаЗначений Отец, Сын, Количество.
Есть конкретный отец.
По ней я делаю еще одну ТаблицуЗначений Отец, Дети
Дети - это СписокЗначений Сын,Строка(Количество) - мне в семерке неудобно искать всех сыновей каждый раз, я уж один раз ее (таблицу дуг) перелистаю.
Потом разузловываю. Все за 1 секунду.
Ответили: (59) (61) (66)

Прикрепленные файлы:

Миллион.ert
# Ответить
59. Ish_2 25.11.2010 18:29
(58) Ок. Буду смотреть.
# Ответить
60. hogik 25.11.2010 19:17
(40)
Ярослав.
1) "все что касается работы с памятью прикладным программистам не доступно"(с)
Доступно.
2) "за это отвечает операционная система"(с)
Допустим. Но размер используемой памяти "заказывает приложение". Существуют ограничения количественные и "качественные" (одновременный доступ к данным с разных ЭВМ). И для уменьшения потребного размера необходимо в памяти иметь только нужную и возможную информацию. Этим, в частности, и занимается СУБД. А если в одной таблице, например, лежат "деревья" для разных "тепловозов" и требуется обработать конкретный "тепловоз" - надо отобрать нужные данные из таблицы БД. В схеме БД в постановке от Игоря - отобрать нужные данные равносильно решить конечную задачу.
3) "за это отвечает операционная система и что код будет работать быстрее"(с)
Для обсуждаемой темы, нет никакой связи в ответственности ОС-а и скорости кода.
4) "если это будет работа с массивами данных в памяти, а не запросы..."(с)
Безусловно. Остаётся НУЖНЫЕ данные рационально положить в память.
(53)
"Прекращайте писать запросы!"(с)
Александр.
А если нету никаких других средств обработки данных в БД?
И даже в НАШЕЙ "1С 7.7" SQL-ной версии всё делается запросами.
Для примера (примера !!!).
Метод ВыбратьЭлементы().
В DBF-ной версии ничего не выбирается. Это только установка на первую запись множества. А в SQL-ной версии это передача от сервера клиенту всего множества элементов справочника. А если они все не нужны приложению? А если приложение вызывает этот метод многократно?
Ответили: (61)
# Ответить
61. hogik 25.11.2010 19:49
(58)
Александр, дополнение к (60) о "Прекращайте писать запросы!" из (53).
Методы "НайтиПоКоду(), НайтиЭлемент() и т.д" - в платформе реализуется запросами.
# Ответить
62. Eugeneer 25.11.2010 21:58
А зачем вообще рекурсия нужна если есть метод НайтиСтроки()....
Ответили: (63)
# Ответить
63. Ish_2 25.11.2010 22:08
(62) Это ты сгоряча. Попробуй накидать такую процедуру .
Ответили: (64)
# Ответить
64. Eugeneer 25.11.2010 22:16
(63) я понимаю что процедура может быть кайфовая и интересная, но я привык не усложнять жизнь там где это не требуется.
Поверте мест для оптимизации хватает с головой везде. но не там где доли секнуды решают всё.
Все таки такие гипермегасуперпупер толстые дерева значений это огромная редкость.
Чесно не проверял но на 10000 строк дерева (у меня есть много рекурсий и я очень часто использую деревья) разницы несущественны. толи секунда то ли полсекунды...
Ответили: (65)
# Ответить
65. Ish_2 26.11.2010 05:31
(64) Да , согласен. Задача редкая и актуальна для крупных предприятий.
# Ответить
66. Ish_2 26.11.2010 08:08
(58) Эффектное начало "Прекращайте писать запросы !" - возбудило интерес.
Я даже хлопнул в ладоши - " Это по-нашему ! Ай, да Арчибальд !"
Ты щелкнул "миллионный граф" , как и Сергей, - за секунду и даже не насторожился : этого сделать еще никому и нигде не удалось .

Теперь по существу. Будем плясать от печки - от постановки задачи.
Графы номенклатуры (спецификации) в БД хранится в табличном в виде см. рис. 1 текущей темы . Другими словами , Таблица с колонками
Владелец,Номенклатура, Количество полностью и однозначно описывает любой граф номенклатуры текущей конфигурации.
Любые другие дополнительные структуры для хранения информации о графе ( в твоей обработке это "глТЗ_Узлы") - избыточны, и могут применяться в реальных проектах для ускорения обработки графа. Эта избыточность , как неизбежное зло, приводит к "геморрою" при модификации графа (согласованные изменения нужно проводить сразу в нескольких таблицах и следить за целостностью)
Вот они-то, эти избыточные структуры, и не должны использоваться при решении.

Еще раз. Когда стартует твой алгоритм ( у тебя процедура "Разузлование")
он должен иметь на входе справочник с реквизитами Владелец,Номенклатура,КОличество ( у тебя это таблица "глТз_Дуги") . ВСЁ ! Точка.
В ней должен быть полностью описан исходный граф .

Ты же на входе имеешь две таблицы глТЗ_Дуги и глТЗ_Узлы.

Вот и весь секрет : в миллион раз упростив задачу - ты решил её за секунду.
Ответили: (68)
# Ответить
67. Ish_2 26.11.2010 08:51
(45) А можно поподробнее ? Как ставилась задача и как решалась ?
Здесь я вижу один из альтернативных подходов к задачам , подобным "разузлованию" :
откажемся от встроенных возможностей платфомы 1с как неэффективных ! -
и во внешней обработке обратимся к базе 1с через ADO- соединение.
Ну и как ? Насколько помогло ? Каков максимальный граф ? и каково время обработки графа ?
Ответили: (86)
# Ответить
68. Арчибальд 26.11.2010 10:17
(66) На входе алгоритма я имею Справочник.Наборы с реквизитами Отец, Сын (элементы справочника Номенклатурные позиции) и Количество. Это безызбыточное определение графа, бесспорно. Ну и что?
Для графов существует множество задач, и для решения их могут и должны использоваться разные представления. Для разузлования я выбрал глТЗ_Узлы, формирую эту единственную таблицу простейшим запросом (см. рис.) и при разузловании пользуюсь только ей. Никаких избыточных структур. Решал бы я другую задачу - возможно, я бы использовал еще какое-нибудь представление.
Ну, а дополнительное условие - не преобразовывать структуру - напоминает известную историю, когда у пациента удаляли гланды, а тот по условию должен был держать рот закрытым.
Ответили: (71)

Прикрепленные файлы:

МиллионЗапрос.PNG
# Ответить
69. Арчибальд 26.11.2010 10:28
+68 Т.о. "запросно-лобовой" подход к задаче разузлования совпадает с подходом "что тут думать, трясти надо". И трясем 20 секунд. Мой же вариант - сначала полсекунды "подумать" (преобразовать представление графа), а потом за полсекунды разузловать его.
"Запрос в БД - это сила. Рекурсия - это зло ."
Может, рекурсия и зло. Иногда. Но запрос - отнюдь не всегда сила. В контексте статьи - это зло.
Ответили: (72) (83)
+ 1 [ hogik; ]
# Ответить
70. prizrak58 26.11.2010 11:26
под конфигурации Комплексная автоматизация не работает, выдает ошибку:
{Форма.Форма(34)}: Ошибка при вызове метода контекста (Выполнить): {(2, 14)}: Поле не найдено "Спец.Ссылка.Владелец"
Спец.Ссылка.<<?>>Владелец КАК Владелец,
Запрос.Выполнить();
по причине:
{(2, 14)}: Поле не найдено "Спец.Ссылка.Владелец"
Спец.Ссылка.<<?>>Владелец КАК Владелец,
# Ответить
71. Ish_2 26.11.2010 11:46
(68) Начинаем разбираться :

В постановке задачи текущей темы четко сказано, что мы имеем на входе :
Таблицу Владелец,Номенклатура,Количество
( у тебя это Справочник.Наборы со структурой Отец,Сын,КОличество). И Все !

Эта и только эта таблица должна быть известна при старте алгоритма,
все другие структуры должны создаваться внутри процедуры Разузловать(),
по которой мы контролируем время.Это требование настолько элементарное ,
что я не собираюсь его доказывать.

Что же мы имеем в твоей обработке ?
Внутри процедуры Разузловать() идет обращение к таблице глТЗ_Узлы , которая
создана вне процедуры Разузловать(), вне зачета времени.

Серьезное ли это нарушение ? - Отвечаю: Да .
Достаточное ли основание , чтобы прекратить дальнейшее рассмотрение кода ? - Отвечаю : Да .
Вывод : автор обработки решает какую-то свою задачу , отличную от той, которая задана в теме.
# Ответить
72. Ish_2 26.11.2010 11:57
(69) Да , не торопись ты с лозунгами. Разберись со своей обработкой.
# Ответить
73. huse (файл скачал) 26.11.2010 11:57
(0) Написал (рекурсия+кэш+запрос):

Тест1: 0 секунд
Тест2: 0 секунд
Тест3: обвал 1С-ки. Там зацикливание? Сейчас проверку сделаю.
Ответили: (75)
# Ответить
74. huse (файл скачал) 26.11.2010 12:07
(0) Вот результат работы:
**** Начато тестирование Тест №1 "Десять" ( 6 уровней, 1 000 000 ветвей)
Общее время выполнения 1
**** Начато тестирование Тест №2 "Два   " (20 уровней, 1 048 576 ветвей)
Общее время выполнения 0
**** Начато тестирование Тест №3 "Ошибки" (7  уровней, 1 000 000 ветвей)
Общее время выполнения 0
...Показать Скрыть


Если запущу повторно первый тест тоже 0 выдаст.

Вот код, вставленный в твою обработку и выведенный на отдельную кнопку:
Функция ПолучитьСостав(Запрос,Кэш,Номен,КолВо=1)
	Запрос.Текст = "ВЫБРАТЬ
	               |	Спец.Номенклатура,
	               |	Спец.Количество
	               |ИЗ  Справочник.СпецификацииНоменклатуры.ИсходныеКомплектующие КАК Спец
	               |ГДЕ (НЕ Спец.Ссылка.ПометкаУдаления И Спец.Ссылка.Владелец = &Узел)";
	Запрос.УстановитьПараметр("Узел",Номен);
	тз=Запрос.Выполнить().Выгрузить();
	Если тз.Количество()=0 Тогда
		Возврат 0;
	Иначе
		тз0=тз.СкопироватьКолонки(); развернули=Ложь;
		Для каждого эл из тз Цикл
			тз1=Кэш[эл.Номенклатура];
			Если тз1=Неопределено Тогда
				Кэш.Вставить(эл.Номенклатура,1);
				тз1=ПолучитьСостав(Запрос,Кэш,эл.Номенклатура,эл.Количество);
				Кэш.Вставить(эл.Номенклатура,тз1);
			КонецЕсли;
			Если тз1=0 Тогда
				стр=тз0.Добавить();
				стр.Номенклатура=эл.Номенклатура; стр.Количество=эл.Количество*КолВо;
			ИначеЕсли тз1<>1 Тогда
				развернули=Истина;
				Для каждого эл1 из тз1 Цикл
					стр=тз0.Добавить();
					стр.Номенклатура=эл1.Номенклатура; стр.Количество=эл1.Количество*КолВо;
				КонецЦикла;
			КонецЕсли;
		КонецЦикла;
		Если развернули Тогда тз0.Свернуть("Номенклатура","Количество"); КонецЕсли;
		Возврат тз0;
	КонецЕсли;
КонецФункции

Процедура КнопкаВыполнитьНажатие1(Кнопка)
	Если Не ЗначениеЗаполнено(Номенклатура) Тогда
		 Предупреждение("Не заполнена Номенклатура !",20);
		 Возврат;
	КонецЕсли;	 
	НачДата = ТекущаяДата(); 
	Результат.Очистить();
	Ошибки.Строки.Очистить();
	Сообщить("**** Начато тестирование "+Номенклатура);
	Запрос = Новый Запрос;
	Кэш=Новый Соответствие;
	Результат=ПолучитьСостав(Запрос,Кэш,Номенклатура);
	Сообщить("Общее время выполнения "+ (ТекущаяДата()-НачДата));
КонецПроцедуры
...Показать Скрыть


Код особо не оптимизировал. Если бы работало тормозно - занялся бы, а так работает быстро ну и пофиг с ним.
Ответили: (76)
+ 1 [ ildarovich; ]
# Ответить
75. Ish_2 26.11.2010 12:09
(73) Да там сделана имитация зацикливания. Если в алгоритме нет контроля зацикливания , то он так и должен щелкать Тесты №1 и №2 за 0 сек.
Контроль зацикливания должен быть безусловным, т.е. любое зацикливание должно быть отловлено.
Чтобы можно было проверить правильность контроль зацикливания должен выдаваться по окончанию граф ошибок. Иначе как пользовтаель исправит эту ошибку в огромном графе ?
Если снять контроль зацикливания - задача становится тривиальной и неинтересной.
# Ответить
76. Ish_2 26.11.2010 12:13
(74) К посту на ИС можно прикрепить файл. Внизу окна сообщения надпись "прикрепить файл".
Прикрепи файл обработки - я его посмотрю.
Ответили: (78)
# Ответить
77. huse (файл скачал) 26.11.2010 12:16
(0) Как видим утверждение, что рекурсия зло - абсолютно несостоятельно.
+ 1 [ hogik; ]
# Ответить
78. huse (файл скачал) 26.11.2010 12:19
(76) Прикрепил
Ответили: (79)

Прикрепленные файлы:

ZaprosProtivRekursii.epf
# Ответить
79. Ish_2 26.11.2010 12:23
(78) Отлично !
Я так понимаю , что ты создал универсальную обработку ? которая раскрутит любой граф , каким бы он не был с любым зацикливанием ? Например, если в тесте № 1 все 1 111 111 узлов уникальны ( не повторяются) , то также быстро всё будет ? У меня - да . А у тебя ?
Ответили: (80) (81)
# Ответить
80. huse (файл скачал) 26.11.2010 12:30
(79) зацикливание я просто срезаю (игнорирую) - можно было бы орать, что ошибка или собирать ее куда то, но не интересно - допиши если надо.

В остальном она раскрутит любой граф. Насчет так же быстро - нет. Когда все узлы графа будут уникальны - скорость приблизится к твоему алгоритму. Единственное твой выиграет, потому что меньше команд выполняет. Поэтому надо будет оптимизировать код, который я написал - возможно использовать временные таблицы и Группировку, а не Соответствие. Тогда скорость будет примерно одинакова с твоим алгоритмом.

Другое дело что в жизни такой уникальный граф - редкость. Поэтому сейчас создавать такую обработку неинтересно. Главное я доказал - рекурсия совершенно не при чем.
Ответили: (83)
# Ответить
81. huse (файл скачал) 26.11.2010 12:37
(79) Вообще простая логика показывает, что обработка 50 узлов, состоящих из 10 элементов - это быстрая задача. Если мы 50 узлов заменим на 1 млн узлов - естественно скорость выполнения упадет.

Твой алгоритм неэффективно работает на поставленной задаче - вместо того, чтобы обработать 50 узлов - он делает перемножение и обрабатывает больше. Поэтому работает 50 секунд вместо 1-ной (у меня по-крайней мере).
Ответили: (82)
# Ответить
82. Ish_2 26.11.2010 12:59
(81) Я буду смотреть твою обработку . А пока :

Простая логика - у каждого своя.
Если я тебя правильно понял , то твой универсальный алгоритм в тесте №1 , если в графе все узлы уникальны , даст время в 20 000 раз более медленное, чем в придуманном для простоты контроля и удобного тестирования тесте №1.
Т.е. работоспособность в реальных задачах на миллионном произвольном графе мы о не можем гарантировать.

А теперь сравни :
представленная в теме обработка ЗапросПротивРекурсии.epf на миллионном графе со структурой теста № 1 при любой уникальности (неповторяемости) узлов даст один и тот же результат. (увеличится время копирования Справочника СпецификацияНоменклатуры во врем.таблицу , увеличится время выгрузки миллиона выходных записей запроса на форму, но само разузлование будет длиться столько же +-10%.
Ответили: (83) (84)
# Ответить
83. Ish_2 26.11.2010 13:02
(69) Прочти , пожалуйста (80) и (82).
Я просто хочу быть понятым.
У тебя на входе Справочник.Наборы , который я как-то хитро неизвестным тебе образом задал. В нем не один граф, в нем все графы номенклатуры предприятия.
Задаю тебе точку входа и ВСЁ.
Если ты рассмотришь задачу под таким углом зрения - ты всё поймешь. Именно так она ставится в реальных задачах разузлования. Так она стоит и у меня.
Другие разновидности задачи - ТРИВИАЛЬНЫ.

(81) Мало того , тест № 2 (20 уровней), такой же миллионник как и Тест№1, приведен здесь для того , чтобы утверждать универсальность обработки:
представленная обработка обработает граф произвольного вида до 20 уровня с миллионом уникальных узлов за время за 120-300 сек + время копирования справочника+время выгрузки миллиона элементов на форму в табличное поле.
Итого примерно 120-400 сек.
Ответили: (84) (90)
# Ответить
84. huse (файл скачал) 26.11.2010 13:46
(83) Ты говоришь что-то непонятное. Взял бы да посмотрел уже обработку. Я использую Справочник.СпецификацииНоменклатуры (а не Наборы). Я не особо разбираюсь в БП 1.6. Посмотрел твой код и предположил, что в этом справочнике лежит разузловка. Использую только этот справочник. Заполнение его и Справочник.Номенклатура производился твоим кодом.

(82) Мой универсальный алгоритм будет работать тем дольше, чем больше уникальных узлов он обрабатывает.

Мы имеем граф (1-10-10-10-10-10-10).

Твой алгоритм пошагово модифицирует граф:
1. (10)-10-10-10-10-10
2. (100)-10-10-10-10
3. (1000)-10-10-10
4. (10000)-10-10
5. (100000)-10
6. (1000000)
И в результате обрабатывает 1 111 111 элементов.

Мой алгоритм:
1. 1-10-10-10-10-(10)
2. 1-10-10-10-(10)
3. 1-10-10-(10)
4. 1-10-(10)
5. 1-(10)
6. (10)

И в результате обрабатывает 60 элементов.

Если граф будет

1-10-100-1000-10000

Твой алгоритм:
1. (10)-100-1000-10000
2. (1 000)-1000-10000
3. (1 000 000)-10000
4. (10 000 000 000)

Будет обрабатывать 10 001 001 010 элементов

Мой алгоритм:

1. 1-10-100-(10000)
2. 1-10-(10000)
3. 1-(10000)
4. (10000)

Будет обрабатывать 40 000 элементов

Если не веришь - напиши тест №4 и убедись.
Ответили: (85) (88) (92)
+ 1 [ hogik; ]
# Ответить
85. Ish_2 26.11.2010 13:49
(84) Смотрю.Ок.
# Ответить
86. SatanClaws 26.11.2010 14:11
(67)
Да это кусок из 1С++ класса, строящий фильтр по условию вхождения в группу справочника.

Для осьмерки, на сколько я знаю, ни метапарсера толкового, ни преобразователя "ссылка <-> идшник в базе" нет.

ЗЫ там, кстати, еще и ошибка сделана - одного Нолока не хватает.
Пойду убьюсь исправлю.
Ответили: (87)
# Ответить
87. Ish_2 26.11.2010 15:08
(86) 1с++. Нет слов.
# Ответить
88. Ish_2 26.11.2010 15:14
(84) Код не смотрел. До этого не дошло. Провел два эксперимента.

1. Запустил файловый режим.
Нажал твою кнопку "Выполнить1" для специально приготовленного миллионного теста с уникальными узлами .
Примерно через 25 мин . через диспетчер задач прервал выполнение 1сПредприятия.

2. Взял Тест №1. Интерактивно ( табличное поле Спецификации это позволяет) внес в спецификации зацикливание. Дальше смотри рисунок .
2.
Ответили: (119) (122) (125) (126)

Прикрепленные файлы:

ПримерДляHuse.png
# Ответить
89. ildarovich (файл скачал) 26.11.2010 16:28
(25) Игорь! Я провел эксперименты. Ваши выводы и результаты по тесту №3 не подтверждаются. Вашу обработку брал из Вашей статьи, свою - из своей "Как не попасть на миллион". Заполнялку брал свою(приложена к моей статье).В результате на тесте с 1 111 111 позициями номенклатуры Ваша обработка работала 145 секунд, моя (рекурсия в оперативной памяти) - 115! Могу объяснить только тем, что Вы заполняли спецификации "слоями", так что две последовательно выбираемые спецификации лежат рядом или (чем еще?).
Ответили: (91) (92)

Прикрепленные файлы:

ИтоговоеСравнение.png
+ 1 [ hogik; ]
# Ответить
90. Арчибальд 26.11.2010 16:44
(83) http://infostart.ru/public/78737/
Произвольные графы до 11, правда, уровня.
# Ответить
91. ildarovich (файл скачал) 26.11.2010 16:50
(89) В итоговой таблице (описании тестовых структур - не в результатах!) есть незначительные неточности. Вечером исправлю и дополню таблицу.
# Ответить
92. Ish_2 26.11.2010 17:19
Давайте по порядку.

(84) Huse , надеюсь мы закончили тестирование и вопросов больше нет.

(89) Арчибальд, мне нужно от тебя словесное уведомление ,
1. Что на входе алгоритма (процедура Разузловать()) у тебя только справочник Отборы структурой Отец , Сын, Количество и одна выбранная Позиция номенклатуры и ВСЕ !

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

(91) Ildarovic, тоже жду словесного подтверждения :
1. Ваша обработка должна быть работоспособной в БП 1.6 (2.0), предыдущая обработка была с ошибками и вылетала. Разбирать код её я не стал.

1. Что на входе алгоритма у Вас только справочник СпецификацияНоменклатуры одна выбранная номенклатуры и ВСЕ !

2. Я могу заполнить Ваш справочник как угодно , каким угодно по виду миллионным графом с уникальными элементами или с любыми зацикливаниями и Ваша обработка
а ) не вылетит б) покажет хотя бы строкой все зацикленные ветки , которые я внес.

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

Дополнение. Всеми этими свойствами , разумеется обладает представленная в теме
обработка ЗапросПротивРекурсии.epf . Т.е. вопрос :

Почём твоя скотина , ковбой ?

- я задал вначале себе.
Ответили: (93) (95)
# Ответить
93. ildarovich (файл скачал) 26.11.2010 17:38
(92) Подтверждаю:
1. Обработка работоспособна в БП1.6, приложена к статье. На предыдущей было черным по белому написано - "для БП (не проверялась!)".
1. Именно так - на входе ссылка на разузловываемую номенклатуру.
2. Заполняйте справочник как угодно. Обработка а) не вылетит б) покажет узел, входящий в цикл (выдача цепочки не нужна (обосновано в тексте программы) и на быстродействии не сказывается).

Можете привязаться только к пункту 2б, но это бессмысленно. Мне просто не хотелось идти у Вас на поводу и делать проверку цепочки таким ненадежным способом как поиск кода (наименования) в строке пройденного пути - ведь об уникальности кодов (наименований в справочнике мы не договаривались!). Перечень цепочек может быть слишком большим и не говорит о конкретном месте ошибки. Нужен анализ, который у Вас тоже не делается.
Также можете попривязываться к тому, что я делаю засечку "финиша" в момент возврата результата в виде соответствия - требование вывода в табличный документ ? появилось позже. Вывод (уточните для меня еще раз, куда) сразу сделаю.

А все таки пришлите свою заполнялку для дерева 1 111 111, чтобы я мог убедиться в послойном заполнении, можете проверить мою - работает не три часа, в 1,5 - рекурсия ;) !
Ответили: (94)
# Ответить
94. Ish_2 26.11.2010 17:49
(93)
1.требования вывода в табличный документ - у меня нет. Если есть то укажите.
Результат разузлования должен выводится на форму в виде табличного поля (таблицы значений).
2. Как же пользователь узнает где ошибка в графе ? как он её будет искать ?
У меня выдаются первые 100 ошибок в виде графа - причем именно там где они произошли (можете убедиться ) и пользователь может интерактивно их тут же исправить. Скажите как я проконтролирую правильность вашей обработки если мне выдастся просто сообщение для миллионного графа : элемент такой -то ? где его искать и в каких местах спецификации если он повторяется в 1000 спецификаций и лишь в одной из них он зацикливается ??
В условии задачи указана БП 1.6 - в этой конфигурации в справочнике Номенклатуры коды уникальны.
Что предложите ?
Ответили: (98) (112)
# Ответить
95. Арчибальд 26.11.2010 17:51
(92)
Арчибальд, мне нужно от тебя словесное уведомление ,
1. Что на входе алгоритма (процедура Разузловать()) у тебя только справочник Отборы структурой Отец , Сын, Количество и одна выбранная Позиция номенклатуры и ВСЕ !

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

По первому пункту ДА.
По Второму пункту. а) ДА, б) при нахождении каждого зацикливания сообщается начало и конец ветки и ветка "обрезается". То есть ДА.

Дополнительно: я явно указываю предельную длину цепочки. При превышении цепочка обрезается. Однако этот момент не критичен, можно этого и не делать - работоспособность сохраняется.
Ответили: (96) (97)

Прикрепленные файлы:

Иллюстрация.PNG
# Ответить
96. Ish_2 26.11.2010 18:06
(95)Правильно ли я понял . Пример если в графе есть ветка:
Корень-Эл357-Эл31-Эл11-...Эл20- Эл54-Эл78--...Эл20.

Эту строку - ветку от корня я увижу целиком ? как сейчас на экране ?
так , как в моей обработке (только в строковом виде ) ?
P.S. Прошу поверить это не дурь и не придирки -
иначе я не проверю правильность контроля зацикливания.
не найдет её и пользователь, который работает со спецификациями, тот для которого всё и предназначено.
# Ответить
97. Ish_2 26.11.2010 18:14
(95)+ Сам посуди , элемент Эл20 может в встретиться в 1000 спецификаций и лишь в одной из них он зациклен. Я его тогда не найду по информации "Корень - Эл20"
Ответили: (99)
# Ответить
98. ildarovich (файл скачал) 26.11.2010 18:18
(94) Предложу подумать
1. Сколько цепочек будет выведено как циклические (без ограничений 100), если в тесте №2 ввести в две спецификации нижнего уровня две разных номенклатуры первого (уровни с нуля) уровня. Как выбрать ошибочную связь? (На самом деле в цепочках нужно посчитать дуги и проверить только самые часто встречающиеся - такой результат будет самым точным, но такой анализ выходит за рамки задачи).
Я бы предложил для поиска ошибок отдельную процедуру (функцию), на вход которой подается ошибочный узел из моего диагноза.
Вывод перепишу.
Ответили: (100)
# Ответить
99. Арчибальд 26.11.2010 18:26
(97) Зачем мне все ветки? Если в графе есть дуга с началом в Эл20 и концом в любом из предков Эл20, скажем, Эл50, ты предлагаешь мне перечислить все цепочки от Эл50 до Эл20? Ошибка-то одна, ее и фиксим, т.е. обрезаем дугу и сообщаем ее начало и конец (см. рисунок в 95 посте). А сколько различных циклов порождает эта ошибка - зачем это считать?
Ответили: (101)
# Ответить
100. Ish_2 26.11.2010 18:32
(98) А зачем думать ? Посмотрите как выводятся ошибки у меня в ЗапросПротивРекурсии.epf .
В демо БП запустите обработку. Заполните тестовый пример Тест № 1.
В табличном поле спецификации появится сформированное дерево с корнем Тест № 1.
Интерактивно открывайте любую ветку появится форма элемента справочника "СпецификацияНоменклатуры" -
исправляйте её как хотите. Вносите зацикливания и смотрите на странице панели "Ошибки",
что получится после "кнопки выполнить".
Ответили: (104)

Прикрепленные файлы:

ПримерКорректировкиТеста№1.png
# Ответить
101. Ish_2 26.11.2010 18:42
(99) Специально для тебя приготовлю простейшее изображение варианта графа с ошибкой зацикливания ,
ты мне мне ответишь какую ветку (в виде строки выдаст твоя обработка).
А пока другой пример попроще,из моей обработки.
Номенклатура "Тест №1 "Ошибки" была специально зациклена на 7 уровне.
И программа выдала все ветки ошибок.
Ответили: (102)

Прикрепленные файлы:

ИзображениеГрафаОшибок.png
# Ответить
102. Арчибальд 26.11.2010 18:46
(101) Уж пришли тогда текстовый файл

НомНоменклатуры;НомНоменклатуры;Количество
НомНоменклатуры;НомНоменклатуры;Количество
.......
НомНоменклатуры;НомНоменклатуры;Количество

Загружу и запущу.
Ответили: (103) (105) (107) (108) (127)
# Ответить
103. Ish_2 26.11.2010 18:53
(102) Отвлекут минут на 10. Скоро отвечу.
# Ответить
104. hogik 26.11.2010 18:55
(100)
Не удержусь - отвечу.
"Интерактивно открывайте любую ветку появится форма элемента справочника"(с)
Посадите на Ваш алгоритм двух пользователей.
Интерактивно... :-)
Ответили: (106)
# Ответить
105. Ish_2 26.11.2010 19:23
(102) Посмотри на этот пример . Эл 20 - встречается в графе 4 раза.
В предыдущем посте я неправильно сформулировал .
Я ожидаю увидеть у тебя две ошибочных ветки в виде строк :
Корень-Эл1-Эл20-Эл21-Эл20;
Корень-Эл2-Эл3-Эл20-Эл21-Эл20;
Почему ?
Потому что , что же я буду лазить по всем спецификациям и искать где он еще встречается ?
Ответили: (108)

Прикрепленные файлы:

ИзображениеГрафаОшибок.png
# Ответить
106. Ish_2 26.11.2010 19:26
(104) Хорошо , что не удержались !
Только , Вадимир, в 8-ке два пользователя параллельно могут открыть форму элемента справочника.
При записи, правда, у последнего из двух попытавшихся записать этот элемент возникнут проблемы .
Ответили: (109)
# Ответить
107. Ish_2 26.11.2010 19:32
(102) А может ,и правда . подготовить тебе текстовые файлы и выгрузить все мои тесты миллионники ?
КодВладельца,КодНоменклатуры,Количество ?
# Ответить
108. Ish_2 26.11.2010 19:51
(102) Пост(105) считать ошибочным. Достаточно выдать одну ветку
# Ответить
109. hogik 26.11.2010 19:55
(106)
Игорь, спасибо за пояснения отличий 8-ки от 7-ки. ;-)
Но, не про "проблемы" записи я Вам напомнил.
Прочтите, пожалуйста, моё сообщение #32 целиком.
Там есть слова: "Т.е. никакого воздействия данными отчета на исходную таблицы БД - невозможно". Готов дать пояснения...
P.S. Еще раз не удержусь - напишу.
Мне очень понравилось сравнение НАШЕЙ темы с "ковбоем, мистером и скотиной".
Однако у "скотины" кроме цены есть еще масса характеристик.
И если "мистер" собирается покупать "скотину" для людей или себя, то он, прежде всего смотрит на "скотину". А уже потом справляется о цене. И обсуждает разные нюансы выращивания "скотины".
А если "м..." собирается перепродать "скотину" и наварить на этом, то это уже другое название покупателя на букву "м". Его интересует прежде всего цена...
Ответили: (110)
# Ответить
110. Ish_2 26.11.2010 20:00
(109) Диалог двух персонажей и главный вопрос :

Почем твоя скотина , ковбой ?

могут иметь много толкований .
Против Вашего я никоим образом не возражаю.
Ответили: (111)
# Ответить
111. hogik 26.11.2010 20:07
(110)
Игорь.
Вы, опять, в моих сообщения читаете только знакомые Вам слова. :-(
P.S.
Всё - я "отписываюсь" от данной темы обсуждений.
Пора заняться написанием очередного отчета для пользователей (людей).
У меня же нету СКД... ;-)
# Ответить
112. ildarovich (файл скачал) 26.11.2010 20:12
(94) Вношу поправку в итоговый отчет. Некоторые результаты "Запроса" оказались лучше.
Свои исследования я на этом заканчиваю, научившись по ходу дела быстро обрабатывать большие графы в памяти.
Вот моя итоговая таблица
Ответили: (114) (128)

Прикрепленные файлы:

ИтоговоеСравнениеПлюс.png
# Ответить
113. ildarovich (файл скачал) 26.11.2010 20:33
(0) В целом по статье могу сказать следующее: Игорь показал ФОКУС. То есть в статье основное внимание уделено ФОКУСУ. На ней должно быть написано: "НЕ ПЫТАЙТЕСЬ ЭТО ПОВТОРЯТЬ!". А поскольку многие приняли статью за чистую монету - раскрою секрет этого ФОКУСА, если автор не хочет саморазоблачаться.
Приведенный в статье метод (не подход, а метод как одновременное разузлование и контроль циклов в одном запросе) имеет некоторый выигрыш перед другими только в одном случае: КОГДА ГРАФ ЯВЛЯЕТСЯ ДЕРЕВОМ. Стоит ветвям пересечься, метод проигрывает в сто и тысячи раз. Деревья - это гораздо более простой граф для алгоритмической обработки. В дереве у любого узла всегда есть уровень: для контроля зацикленности проверьте, чтобы в спецификации указывались только элементы следующего уровня и все! Распихивать древовидную спецификации одного изделия по объектам ИБ при этом даже нет смысла - на части спецификации нет внешних ссылок! Достаточно одной спецификации из миллиона элементов (с указанием для каждого порядка сборки - пути). А скрещивать УЖА (поиск циклов) и ЕЖА(разузлование) в одном запросе на практике? - будете иметь 200 секунд вместо 0,017!!!
Успехов в написании правильных запросов!
Ответили: (114) (118)
# Ответить
114. ildarovich (файл скачал) 26.11.2010 20:50
(112) Считаю, что рекурсия победила как минимум со счетом 2:1.
По результатам закономерности из (113) смогу синтезировать тест в пользу любой гипотезы. Синтетические тесты, поэтому, малоинтересны.

Даешь ЭЛЕКТРОВОЗ!
Ответили: (115) (117)
# Ответить
115. Ish_2 26.11.2010 21:41
(114) Сергей , не нужно спешить объявлять о победе.
Поднимитесь вверх по теме и посмотрите . что произошло с обработкой Huse на нерегулярном графе ? Не сделано главного : Ваша обработка не проверена на работоспособность и устойчивость на специально для этого созданном графе.
Ваша обработка же универсальная , устойчивая, работоспособная.
Неужто неинтересно узнать правду , что произойдет с Вашей обработкой в миллионном графе с нерегулярной структурой ?
Ответили: (116)
# Ответить
116. ildarovich (файл скачал) 27.11.2010 12:17
(115) Надеюсь, это будете делать Вы ?
Слышал, что если долго трясти ящик с радиодеталями, когда-нибудь получится телевизор.
А если речь о специально созданном тесте, то вот Вам тест из моего ФОКУСА - "Матрешка".
Создайте спецификацию всем известной матрешки из вложенных друг в друга миллиона матрешек (пусть это будет тест №5). Вообще определите максимальную вложенность матрешек, решаемую Вашим методом. За свой метод рекурсии я ручаюсь.
# Ответить
117. Ish_2 27.11.2010 12:31
(114) Господа . Предлагаю следующий порядок тестирования :
вначале мы разберемся с обработкой Сергея , а потом обсудим обработку Арчибальда.

Я скачал обработку Сергея из его темы с названием что-то вроде : "Супер-быстрая обработка для БП 1.6".
Постараюсь сегодня доложить результаты .
# Ответить
118. ildarovich (файл скачал) 27.11.2010 12:47
+ (113) Кстати, для спецификаций в виде дерева есть очень эффективные методы выборки подчиненных узлов - одним простым запросом к одной таблице узлов!
На узлах дерева всегда можно определить отношение порядка - например, порядок левостороннего обхода, присвоить этот "порядок" каждому узлу (в виде действительного числа, чтобы при вставке не менять "порядок" других узлов), и выбирать все подчиненные узлы как узлы, "порядок" которых помещается между "порядком" данного и следующего через более высокий уровень узла.
Спецификации в виде дерева можно записать в скобочной форме для интерпретации, использовать ЛИСП как в AutoCAD и так далее, но это уже совсем другая история!
# Ответить
119. Ish_2 27.11.2010 19:24
(118) Результаты тестирования обработки Сергея.

Тема "Как не попасть..." http://infostart.ru/public/78371/
Тестируемый файл
"Внешний отчет суперскоростное разузлование (быстрее нельзя!) для БП1.6"
http://infostart.ru/public/download.php?file=78562

1с8.1 релиз 8.1.15.14 среда проверки :Демо Бп 1.6 и Демо БП. 2.0.

Использовалась та же методика проверки правильности расчета количества, как и в (88) для обработки Huse. Реультат тот же . Обнаружен неверный расчет количества.

1. Запускаем 1с81 , "чистая" демо БП 1.6.
2. Запускаем ЗапросПротивРекурсии.epf , создаем новую тестируемую номенклатуру
"Тест № 1.." (кнопка "заполнить тестовый пример").
Затем повторяем это действие и в итоге имеем в справочнике "Номенклатура" две номенклатуры с одинаковыми именами ("Тест №1..") и соответствющими им подчиненными элементами (справочник "спецификацииНоменклатуры" содержит два одинаковых графа).

3. Для последней созданной номенклатуры совершаем интерактивно в обработке ЗапросПротивРекурсии.epf искусственное зацикливание на 1 уровне см. прикрепленный файл.
4. Действия для 1-3 повторил для Демо БП 2.0 - результат тот же.

Правильное количество для каждой номенклатуры должно быть 640 000.

Тестирование прекращено.
Заявленная обработка не обладает верным функционалом.
Ответили: (120) (122)

Прикрепленные файлы:

РезультатТестированияСергея.png
# Ответить
120. ildarovich (файл скачал) 27.11.2010 21:04
(119) Непонятно описано как сделаны зацикливания.
Ну и так как у Вас два одинаковых графа с одинаковыми названиями вершин, то и скриншот ситуацию не проясняет. Гадать не хочу -
перечислите строки, которые добавили и в какие спецификации. Номенклатуру желательно с кодами, раз у Вас она с одинаковыми названиями!

Непонятно это:
Для последней созданной номенклатуры совершаем интерактивно в обработке ЗапросПротивРекурсии.epf искусственное зацикливание на 1 уровне см. прикрепленный файл.

- я не знаю, какая номенклатура создана последней (второй корень?)
- почему интерактивно?
- почему в обработке?
- почему искусственное? (у Вас бывает естественное зацикливание?)
- что такое зацикливание на первом уровне? (уровни считаются с нулевого?)
Ответили: (121)
# Ответить
121. Ish_2 27.11.2010 21:19
(120) Хм.. Huse с одного раза всё понял.
В обработке ЗапросПротивРекурсии.epf :
Последовательно друг за другом запускаем тест №1. Получаем две корневых номенклатуры для двух одинаковых по структуре графов .
Используем для внесения зацикливаний последнюю из созданных номенклатур.
Затем на панели Спецификации разворачиваем дерево для тестируемой номенклатуры см.Рисунок 1 и интерактивно правим любой элемент справочника
СпецификацииНоменклатуры . Вот я интерактивно и внес такие изменения в корневую спецификацию "Тест № 1" такие зацикливания.
Слушайте проще попробать вам самому чем мне столько писать. Пробуйте.
Ответили: (122)
# Ответить
122. ildarovich (файл скачал) 28.11.2010 10:42
(121) Может быть, что-то пропустил, но от самого мистера Хьюза не слышал, что он "все понял" в (88).
Своим ответом Вы не добавили мне никакой нужной информации. Будем гадать. Благо, общение с пользователями развивает и телепатические способности.
Пока рабочая версия такая: Видимо, наши с мистером Хьюзом обработки натыкаются на какую-то особенность Вашей процедуры заполнения. В эту пользу говорит то, что:
1. При создании в аналогичной структуре, построенной моей обработкой, тех же замыканий, ошибки не происходит (пробуйте);
2. При перещелкивании первой (правильной) строки в первой спецификации ошибка исчезает (пробуйте).
Буду разбираться дальше...
Но все же обращу внимание на следующие противоречия в Ваших показаниях скриншотах.
1. Вы говорите, что зацикливания вносятся в спецификацию последней созданной номенклатуры, то есть во второй граф. Но в результате разузлования созданной последней номенклатуры должны были бы получиться вершины E11 - Е20, а на скриншоте - Е01 - Е10, как будто разузловывается первый граф.
2. Если и в (119) и в (88) вносились одинаковые исправления в первой спецификации, оставляя правильной первую строчку, то почему в Вашем ответе в (88) 12 возвратов в корень, а в (119) - 18. Кстати, в итоговой таблице корень вообще не должен фигурировать как не терминальная вершина.
Ответили: (123)
# Ответить
123. Ish_2 28.11.2010 12:16
(122) О Хьюзе потом.Перед гаданием устанавливаются факты. Итак.

На Вашей и моей машине легальным способом достигнут одинаковый повторяющийся результат :
Неверный подсчет количества.
Доказано, Ваша обработка обладает НЕВЕРНЫМ функционалом.

Вывод :
Отсюда следует , в настоящий момент , что все заявления о СУПЕРскорости Вашей обработки , сравнительные таблицы
и т.д. и т.п ничего не стоят.
Если в мой обработке , Вы найдете такой же грех с неверным расчетом- я буду вынужден признать то же самое.

О деталях - потом.
Ответили: (124)
# Ответить
124. ildarovich (файл скачал) 28.11.2010 13:24
(123) Упс! - Разобрался! Действительно, при определенном порядке строк (в базе! - не на форме!) при зацикливании возвращалось уже непустое разузлование из зацикленного узла! Моя вина! :(
Поправил несколько символов в строке 11 формы, обработку с исправлениями перевыложил. - Игорю спасибо!
Исправления:
Ответили: (127)

Прикрепленные файлы:

ДобавленныйТекстКСтроке11.png
# Ответить
125. huse (файл скачал) 28.11.2010 18:12
(88) Красавец ))) ты бы еще задачу полностью переформулировал и потом что то доказывал. Ошибки я могу собирать - не интересно. Разница в количестве - в разной обработке ошибочной ситуации. Одинаковой и быть не может - мы по разному куб разбираем.

Вместо того чтобы чему то научиться из моего кода, ты предпочел придумывать ситуации где он не работает. Зачем тебе тогда этот пост? Покрасоваться?

PS Моя единственная цель написания кода - было реабилитировать рекурсию. Рекурсию я реабилитировал, а тебя убеждать или заставлять выполнять какие то обещания, которые ты опрометчиво надавал - это не ко мне.
Ответили: (126)
# Ответить
126. Ish_2 28.11.2010 18:49
(125) Виноват. Твое молчание после поста (88) - я воспринял однозначно . Как признание того , что опубликованные результаты настолько ясны , что обсуждать -нечего.

Еще раз : здесь рассматриваются не обработки "заточки", чтобы быстренько решить тесты №1и №2, а универсальные обработки больших графов с обязательным контролем зацикливания. Тесты же №1 и №2 - это быстрые заполнялки при минимальном объеме информации.

Если рассматриваются "универсальные" обработки , то первым испытанием было :
проверить устойчивость на миллионном графе (1 111 111 уникальных узлов) твою обработку. Т.е. Если размер Справочника СпецификацииНоменклатуры вырос в десятки тысяч раз - то это не должно так существенно сказываться на твоей обработке.
Твоя обработка была прервана примерно через 25 мин. Если желаешь - я скажу тебе
точное время. А лучше сам напиши тест заполнения по Тесту №1 только уникальными значениями.

Вторым условием - было правильный контроль зацикливания. Он у тебя отсутствовал.
На Рисунке к посту (88) -всё есть.

Все выводы (88) ты можешь подтвержить или опровегнуть самостоятельно. И рассказать здесь - что не так. И где я не прав.

Пока же результаты (88) настолько красноречиво играют против рекурсии , что по-моему каких-то комментариев более не нужно.
# Ответить
127. Ish_2 28.11.2010 19:12
(102),(124) Господа Арчибальд и Сергей . Предлагаю каждому реализовать самостоятельно тест №1 1-10-10-10-10-10-10 со всеми уникальными узлами.
Всего должно получиться 6 уровней и 1 111 111 уникальных узлов.
Каждый самостоятельно исследует свою обработку на этом графе и сообщает здесь результаты ( если сочтет это возможным).

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

Результаты приводим для теплых(второй , третий) запусков обработки.
Если нужно потом рассмотрим и холодный запуск, а пока только теплые.
Два режима - файловый и клиент-серверный.
Ответили: (128) (133)
# Ответить
128. ildarovich (файл скачал) 28.11.2010 19:54
(127) Игорь! Вы, наверное, не обратили внимания, но в (112) уже приведены результаты этого теста (в строке №3). На этом графе я запускал и Вашу и свою обработку, на ноутбуке и на сервере. Есть и обработка для формирования этого теста (прилагается к моей статье - нужно поставить галочку "дерево"). Во только почему у Вас все тесты имеют одинаковый номер? Я дал этому тесту №3. Обозначил его 1<10<10<10<10<10<10, имея ввиду, что "<" обозначает ветвление. Граф этого вида называется "дерево". Честно говоря, потратил много времени на оптимизацию программы именно для этого случая. Непонятно: до сих пор Вам это было непонятно? :o
То есть Вы вообще не читали мои посты: про ФОКУС, про деревья - это все про данный тест. :cry: Я писал их, зная результаты работы своей программы на этом тесте. Только вот, называя условия этого теста боевыми, Вы лукавите! - могу сослаться на Ваше же высказывание.
Ответили: (129) (130)
+ 1 [ hogik; ]
# Ответить
129. Ish_2 28.11.2010 20:07
(128) Я их не смотрел , потом что считал , что на данном этапе до выяснения работоспособности и правильности - это полная туфта.
И , вообще-то , оказался прав.
Ну что ж , Арчибальд пусть делает миллионный тест , а я завтра проверю у себя. И мы продолжим беседу по Вашей обработке.
# Ответить
130. hogik 28.11.2010 20:11
(128)
Сергей.
А добавьте, пожалуйста, в свою таблицу мои результаты. ;-)
Колонка "без запросов", строка "1<10<10<10<10<10<10" (нижняя).
Файловый - 35 сек. Клиент-серверный - 70 сек.
На самом деле - меньше.
Я замерял на загруженной другими задачами машине.
Ну, и на моей системе нет такого понятия - "файловый".
Т.к. БД всегда одинаковая.
Меняется только способ передачи "пакетов"
Грубо говоря - меняется только "протокол".
Ответили: (131)
# Ответить
131. ildarovich (файл скачал) 28.11.2010 22:08
(130) Владимир! Я понял условия Игоря так, что в таблицах приводятся лично проверенные авторами таблицы результаты работы своих и чужих обработок разузлования на доступных авторам компьютерах. Ваш результат (35 сек) меня заинтересовал. Я его добавил в свою собственную таблицу, которую здесь выкладывать не буду. Сейчас перечитаю Ваши посты, чтобы понять суть подхода.
Ответили: (132)
# Ответить
132. hogik 28.11.2010 23:05
(131)
Сергей.
Там нет никакого подхода.
Я с самого начала приводил тексты и тесты для "лобового" обхода, именно, дерева со схемой БД из темы "стартового" форума. Рекурсия - текстом из пяти строк. Но в рекурсивной функции не используется запросы. Т.е. это не мой подход, а подход СУБД имеющей не только запросный ЯМД.
По поводу внести мои замеры в свою таблицу - это шутка для Игоря по его методе сравнения результатов тестов... ;-)
# Ответить
133. Арчибальд 29.11.2010 08:26
(127) Я уже оценивал объем вычислений в своем алгоритме как О(N * lgN), где N - число узлов графа. Переходя от 60 узлов к миллиону я ожидал увеличения времени в 40000 раз. Реально получил 830 сек, т.е. в 830/0.276 = 3000 раз. Это в 10 раз больше, чем запрос на 8-ке и в 7 раз - чем рекурсия на 8-ке.
Ответили: (135)
# Ответить
134. Арчибальд 29.11.2010 08:53
+133 На "теплом" старте результат - 630 сек.
# Ответить
135. Ish_2 29.11.2010 08:59
(133)
Ты щелкнул за секунду миллионные регулярные графы с известной структурой с мизерным объемом информации.
Как только же дело дошло до главного реального испытания, по которому и определяется быстродействие реального
решения ты проиграл примерно в 8 раз. Время примерно 10(!!!) мин. Нужно продолжать ?
Ответили: (136)
# Ответить
136. Арчибальд 29.11.2010 09:22
(135) Все не совсем так. Я работаю с произвольными графами. На дереве с 11111 различными ветками (реальная сложность тепловоза) я имею 1.5 секунды. Такой результат вполне допустим даже в процедуре ПриЗаписи в модуле справочника номенклатурных наборов. Что касается нереальных задач - как твой алгоритм ведет себя на задаче 1*10*10*10*10*10*10*10*10*10*10 ? В 10 мин укладывается?
Ответили: (138)
# Ответить
137. Арчибальд 29.11.2010 09:51
+136 Как моя оценка времени (N * lg N / 10000) сек. соотносится с реальностью:
1<10<10<10<10<10<10 (~ 1 000 000 узлов) оценка 600 реальность 630
1<10<10<10<10<10 (~ 100 000 узлов) оценка 50 реальность 40
1<10<10<10<10 (~ 10 000 узлов) оценка 4 реальность 3.3
1<10<10<10 (~ 1 000 узлов) оценка 0.3 реальность 0.3
1<10<10 (~ 100 узлов) оценка 0.02 реальность 0.12
Т.е. имеет место еще и предсказуемость.
# Ответить
138. Ish_2 29.11.2010 10:13
(136)
Критерий был определен заранее. Условия известны участникам. Перед тестированием ни у кого вопросов не возникало. И вот после получения результатов появились сомнения : а зачем это нужно ? а в тепловозе оказывается всего 11 111 узлов и т.д.

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

С другой стороны , что мешает тебе открыть новую дискуссию , в которой будут другие условия ( для "тепловозов" 11 111) ? Это будет совсем,совсем другая тема .
И я со своим запросом туда даже не сунусь.

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

как твой алгоритм ведет себя на задаче 1*10*10*10*10*10*10*10*10*10*10 ? В 10 мин укладывается?


Ты задал превосходный вопрос ! Если представить себе гипотетическую ситуацию решения такой задачи в 1с. То такая задача может быть решена :
1. Только в клиент-серверном варианте , причем никаких процедур на клиенте !
При решении таких задач и проявится огромное , чудовищное преимущество представленного алгоритма перед реализациями в духе Арчибальда или Сергея.
Чем больше объем данных тем больше преимущество запроса перед "рукопашным" кодингом - Сергей здесь не даст мне соврать он испытал это.
Спасибо за вопрос ! Пишите запросы !
Ответили: (139) (140)
− 1 [ ildarovich; ]
# Ответить
139. Арчибальд 29.11.2010 10:34
(138) Что же здесь гипотетического? Я решил эту задачу в 1С7.7. ДБФ за (0.7+0.8) сек. Назови свою цифру. Хоть какую-нибудь. Правда, я могу ориентироваться на твой тест №2, умножая твои (пусть) 100 секунд на (10/2)*(10/2). Минут сорок получается... Чудовищно...
# Ответить
140. Арчибальд 29.11.2010 10:52
(138) Цитата из текста статьи.
Тест № 1. "Десять"
Справочник "СпецификацииНоменклатуры" содержит 6-уровневый 10-арный граф , имеющий 1 000 000 различных ветвей и при обходе такого графа таблица ВремТаблица6 на выходе цикла алгоритма содержит 1 000 000 записей. Но сам справочник "СпецификацииНоменклатуры" в своей табличной части содержит лишь 60 записей.
Проще говоря , корневому элементу подчинены 10 элементов, каждому из которых подчинен одинаковый набор из десятка следующих элементов и т.д.
Именно таковы были
Условия известны участникам. Перед тестированием ни у кого вопросов не возникало. И вот после получения результатов появились сомнения : а зачем это нужно ? а в тепловозе оказывается всего 11 111 узлов и т.д.
После получения мной результата в 0.8 секунды именно на тесте №1, именно так сформулированном, как в тексте статьи начинает выясняться: тут читать, тут не читать, здесь я селедку заворачивал... 60 записей я что ли придумал?
Давай уж. Я по твоим правилам поиграл, попробуй ты по моим.
Ответили: (141) (142)
# Ответить
141. Ish_2 29.11.2010 11:20
(140) Нет , Арчибальд. Ты не прав.
Прочитай все мои посты к тебе , все тщетные предупреждения , что ты пишешь универсальную обработку , а не решаешь заполнялки Тестов №1 и №2. Ты уж самостоятельно , все это проверь.
Тесты №1 и №2 это быстрые поверялки реального универсального алгоритма
- ты и Сергей предупреждались об этом неоднократно ! Тщетно ! Вы с Сергем сделали заточки по тестам №1 и №2.
Теперь читаем тему :
...Такая Рекурсия всё равно проиграет запросу 1с. Но буду рад ,если появятся публикации на эту тему с другими мнениями.
Прошу только помнить, что в статье идет речь не о "заточке" для тестов №1 и № 2, а об универсальной обработке произвольного графа ( в общем случае, циклического), которая " в среднем" оптимальна, на взгляд автора, для решения задачи "разузлования" на предприятии. Это значит , что таблица Спецификации может иметь миллионы записей и это существенно не скажется на быстродействии представленной обработки (в клиент-серверном варианте). Это значит также , что алгоритм различные графы и деревья , содержащиеся в таблице Спецификации, обрабатывает одинаково и априорно (на входе) не имеет никакой "подсказывающей "информации о характере графа .



Теперь
Ответили: (143)
# Ответить
142. Ish_2 29.11.2010 11:23
(140) Я принимаю твое предложение о дуэли. И стреляю первым. В воздух.
За тобой выстрел.

Мне нужно еще окончательно разобраться с Сергеем.
# Ответить
143. Арчибальд 29.11.2010 11:40
(141) Нет у меня заточки под тесты. Именно универсальный алгоритм. Я и проверялся то на (псевдо)случайном наборе дуг, разузловывал не один корень, а весь лес сразу. Разница в том, что, цитирую тебя
при отсутствии контроля зацикленности можно было вставить в демонстрационный запрос "СГРУППИРОВАТЬ ПО "
У меня же самодельное "СГРУППИРОВАТЬ ПО" не мешает контролю зацикленности. И поэтому в реальной жизни, когда
На предприятиях ,осуществляющих сборку сложных изделий (летательных аппаратов, электровозов, судов), состоящих из тысяч и десятков тысяч комплектующих, актуальна задача ведения спецификаций изделий
мой алгоритм, с учетом существующей в той же реальной жизни стандартизации/унификации узлов/деталей, оказывается на порядок быстрее.
Ответили: (144)
+ 1 [ ildarovich; ]
# Ответить
144. Ish_2 29.11.2010 11:56
(143) Арчибальд , тебя уважаю , но на новый круг не пойду. Создай новую тему и разделай там меня под орех в своей постановке задачи. На очереди - Сергей и после этого заканчиваем.
Ответили: (145) (146)
# Ответить
145. Арчибальд 29.11.2010 12:09
(144) Ну, поскольку твой "универсальный" алгоритм не срабатывет, как я понимаю, за обозримое время на моей конкретной задаче из 137 поста, а мой все же срабатывает на любой из твоих, будем считать, что утверждение о чудовищности из 138 поста ты сам и дезавуировал...
# Ответить
146. hogik 29.11.2010 18:21
(144)
"На очереди - Сергей и после этого заканчиваем."(с)
А, я? ;-)
Ответили: (147)
# Ответить
147. Ish_2 29.11.2010 18:24
(146) С Вами , Владимир, я уже всё выяснил. И здесь и на форуме.
У меня никаких вопросов не осталось.
На Сергее заканичиваем.Тема затянулась.
Ответили: (148)
# Ответить
148. hogik 29.11.2010 18:41
(147)
Т.е. Вы согласились с тем, что задача решается проще для программиста и работает быстрей?
Если:
1) Не использовать запросы.
2) Использовать "рекурсию".
3) Не использовать 1С 7.7 и 8.х.
4) Строить схему БД не под конкретную задачу, а для решения разных задач в многопользовательской среде.
# Ответить
149. Ish_2 29.11.2010 19:48
Обработка Сергея во второй раз оказалась с неверным функционалом.
На рисунке отображено элементарное двойное зацикливание ,которое не определелила
Обработка Сергея.
Тестирование прекращено.
Ответили: (150) (151) (152) (160)

Прикрепленные файлы:

ОшибкиСергея.png
# Ответить
150. ildarovich (файл скачал) 29.11.2010 21:36
(149) Игорь! Я проверю.

Только стоит ли нам еще препираться?
Я буду говорить, что две ошибки - ситуация редкая, исправьте одну - ищите вторую и т.п.
Потом буду говорить, что Ваша программа не проходит тест "Матрешка",
т.е. не может решить не абстрактную,
а конкретную задачу - раскрыть спецификацию обычной матрешки.
Потом "Матрешку" зациклю где-нибудь на 100-м (или 500-м) уровне и скажу,
что Ваша программа и циклов не находит.

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

Из сотни номенклатур не я - пользователи могут легко построить набор спецификаций,
которые Ваша программа не обсчитает за все время жизни Вселенной!
Ответили: (153)
# Ответить
151. ildarovich (файл скачал) 29.11.2010 21:37
(149) Но можно и заканчить, так как мне пришлось еще раз убедиться в том,
что аргументами можно победить незнание, а невежество так победить нельзя.

Несколько "цивилизованных" программистов Вам доказывают, что умножение быстрее сложения.
Это не метафора, здесь рассматривается именно этот случай (с точки зрения общей алгебры).
Вы же каждый раз приводите в пример случай сложения разных предметов.
Да еще хотите, чтобы ошибки перечисления этих предметов назывались так же,
как делает Ваша незамысловатая, суперстарательная и супер-гипер-трудоемкая
обработка.
# Ответить
152. ildarovich (файл скачал) 29.11.2010 21:39
(149) Если бы Вам пришлось тренироваться в прыжках с парашютом, прежде чем испытывать программу
управления навигационным комплексом самолета, Вы бы были осмотрительнее в выборе методов решения задач.
А бухгалтер - он и не такие издевательства стерпит.

В общем, пользователь Вам судья! Но я бы предпочел, чтобы Вы признали, что нельзя считать
запрос, который работает миллионы лет, победившим рекурсию
. И честно, без уверток написали об этом в своей статье.
Ибо, как говорят мои коллеги - "отрицательный результат - тоже результат".
Этот поступок был бы достоин уважения.
А так - извольте...
+ 2 [ Natgrey; hogik; ]
# Ответить
153. Ish_2 29.11.2010 22:01
(150) Так Вы проверили ? Есть у Вас ошибка в определении зацикливания ?
Ответили: (156)
# Ответить
154. hogik 29.11.2010 22:50
Сергей & Игорь.
Позвольте и мне сказать.
Надеюсь, что вы оба прочтете.
Вы решаете разные задачи!
Игорь делает уклон на сферу СУБД, а Сергей (и Александр) на численные методы.
Игорю, думаю, надо было с самого начала определить задачу так, чтобы и мысли не было рассматривать "графины". Печально, но в теме СУБД очень мало мест где можно применять "математику". В задаче от Игоря её нет вообще.
Игорь сам-себя запутал и других людей запутал. О мотивах этой "запутки" я сказал выше по теме. У Игоря и в обсуждении на форуме, и в данной статье идет "полная путаница" терминов и задач.
Пример "разузлования" (условно!!!).
Колесо автомобиля.
Шина (1 шт.).
Обод (1 шт..
Камера (1 шт.).
Грузик (от 0 до 10 штук).
Но описано само изделие - его состав. А какая будет шина ничего не сказано. На этой позиции могут быть разная шина - производитель, сезонность, вес, цена, поставщик и т.д. Т.е. это (в нашем примере) жестко узел с степенью - четыре. Т.е. описан "каркас" изделия. И это дерево, естественно - без циклов. Часто, заранее, с подсчитанным количеством "входимости" позиций в "каркас". А количество изделий подсчитывается простым запросами с Sum()-ами. ;-)
Для работы с таким деревом требуется не выборка множества узлов, а получение одного узла "соотнесенного" с его родителем и детьми. Это делается не запросом и не "закачкой" в память информации - в СУБД это возможно, но это не есть корректные способы взаимодействия приложения с БД. Почему? Мне казалось, что я об этом сказал многократно в форуме до появления данной стать. Оказывается - нет :-(
А если в задаче строго дерево, то единственный тест (по классификации от Сергея) - под номером три. Всё остальное не имеет отношение к дереву. Т.е. это частные задачи с элементами "фокусов" не в сфере СУБД.
Сравните свои скорости на третьем тесте. Для деревьев с разными степенями и уровнями. И разойдитесь. В сфере СУБД, всё остальное не имеет смысла...
Ответили: (155)
# Ответить
155. Ish_2 29.11.2010 22:54
(154) Пока не мешайте. Мы уж как-нибудь закончим с Сергеем сами.
− 1 [ hogik; ]
# Ответить
156. ildarovich (файл скачал) 29.11.2010 23:43
157. Ish_2 29.11.2010 23:58
Что ж, бывает. Время позднее.
Пора заканчивать. Всем спасибо !
# Ответить
158. huse (файл скачал) 30.11.2010 01:33
(0) ничего писать я больше не буду. ты самый умный - вот и пиши. я верю ты сможешь обосновать клиенту почему так медленно работает.
# Ответить
159. Ish_2 30.11.2010 09:34
И с утра подведем короткое резюме.
Я благодарю авторов Huse,Арчибальда, Сергея , не только обсуждавших задачу "разузлования" , но и представившими свои разработки .
Для меня была важна сама форма эксперимента : открыто обсудить и протестировать в теме альтернативные разработки нескольких авторов.
Насколько это понравилось публике и самим авторам мне судить трудно. Но я старался, чтобы это было интересно.
# Ответить
160. ildarovich (файл скачал) 30.11.2010 12:28
(149) Проверил. Следующее заключение НЕВЕРНО:
Обработка Сергея во второй раз оказалась с неверным функционалом.

В Вашей обработке НЕПРАВИЛЬНО считается циклом ссылка с незаданным - нулевым количеством!
То есть номенклатура всего лишь упомянута в спецификации, ее количество там не задано, оно нулевое. Вес дуги равен нулю. В нашей задаче это - фактическое отсутствие связи - инцидентность равна нулю!
Проверил на Вашей обработке: стер количество из зацикливания в корень в тесте №3, а ошибка все равно показывается! - могу скриншоты привести. Курам на смех!
Хотите, чтобы моя обработка показывала цикл - проставьте в спецификации ненулевое количество!
Ответили: (161)
# Ответить
161. Ish_2 30.11.2010 13:24
(160) Спокойно. Давайте разбираться.

Что есть зацикливание ?
Зацикливание - есть факт нахождения в одной элементарной ветке графа двух одинаковых узлов , другими словами "родитель" является одновременно и "ребенком".
Точка.
Этот факт и должна зафиксировать обработка независимо от других условий.

Вы привносите в это определение дополнительное условие :
и "родитель" и "ребенок" должны ненулевое количество. С чего Вы это взяли ?
Из того , что в Вашем алгоритме так удобнее ?

Теперь сравните что информативнее, полезнее для пользователя , работатющего со спецификациями :
- при Вашей обработке пользователь ничего не узнает о явной ошибке зацикливания
если у "зациклившей" количество равно нулю.
- при моей обработке пользователь обязательно увидит зацикливание и сам определит что с ним делать .

Этот пример зацикливания для того и приведен , чтобы показать слабость Вашего алгоритма . Если исправите , то продолжим . У меня есть еще , что сказать, по поводу Вашего алгоритма.
Ответили: (162) (172)
# Ответить
162. ildarovich (файл скачал) 30.11.2010 18:43
(161) Игорь! Это здорово! Мы с Вами сейчас определим понятие нуля в Вашей алгебре. Я переделаю (0 секунд! - на быстродействии не скажется! - одно "если" убрать!) программу под Вашу извращенную алгебру и ... продолжим.

Только будьте осторожнее с такими привычками, заполняя, например графу анкеты "Состав семьи":
Строка "Жена". В графе количество ставите "0". Не говорите никому в этом случае, что у Вас есть "связь с женой". Неправильно поймут! Загремите прямо на "Дагомысскую".
Про зацикливание я уже и не говорю.

Игорь! Прекращайте спорить с очевидным! - Примеров, показывающих слабость моего алгоритма нет! Кстати, потестировал я тут Вашу обработку (Тест№3): Нажимаю - жду - жду - жду. Самого-то не раздражает? А у меня: нажал "выполнить" - сразу ответ! - Красота!
Ответили: (163)
# Ответить
163. Ish_2 30.11.2010 19:36
(162)Продолжаем.Серия третья.
Ответили: (164) (165) (169) (171) (172) (177)

Прикрепленные файлы:

Ощибки Сергея СерияТретья.png
# Ответить
164. ildarovich (файл скачал) 01.12.2010 12:46
(163) По настоянию Игоря сделал вариант программы, повторяющий "странное" поведение его обработки в случае, когда в спецификации указана номенклатура с нулевым количеством. Обработка Игоря зачем-то разбирает и такую номенклатуру. С Игорем трудно спорить - любое понимание задачи, отличающееся от его собственного, он тут же объявляет "ошибкой" и "прекращает тестирование". Ну а поскольку в данном случае моя обработка только упростится на один оператор "если", я решил согласиться. Нужная для сравнения версия моей обработки называется "Разузлование_БП_1_6_ПустышкиТянем". Она приложена к данному посту.

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

Чтобы не затягивать сериал, предлагаю параллельно проверить обработки на тесте "Матрешка" и заранее придумать объяснение тому, что "универсальная" обработка "запрос в цикле" не работает в конфигурациях, в которых коды номенклатуры не уникальны в пределах всего справочника.
Ответили: (165) (166)

Прикрепленные файлы:

Разузлование_БП_1_6_ПустышкиТянем.erf
# Ответить
165. Ish_2 01.12.2010 13:20
(164) Работаем последовательно.
Мы начали рассматривать вопрос о Вашей обработке :
соответствует ли она заявленному функционалу ? или правильно ли осуществляется контроль зацикливания ?
Без решения этого принципиального вопроса невозможно двинуться дальше.
Итак , я жду Вашего ответа на (163).
После Вашего ответа на (163) пора уже обсудить вопрос :
сколько нужно обнаружить ошибок в определении зацикливанияв в Вашей обработке ,
чтобы прекратить тестирование.
Например , если Вы исправляете ошибку (163) и я Вам предъявляю СериюЧетвертую.png
- то тестирование завершается и объявляется , что "Разработка Сергея не обладает заявленным функционалом".
Или хотя бы назовите номер серии.

Мы решим этот принципиальный вопрос и , обещаю , приступим к полному рассмотрению вопроса о недостатках обработки ЗапросПротивРекурсии.epf (они разумеется, существуют).
Ответили: (168)
# Ответить
166. Арчибальд 01.12.2010 14:28
(164) Для каждого решения можно подобрать (пограничный) вариант графа, на котором оно будет вести себя хуже какого-то другого. У Игоря вот не вытанцовывается, судя по всему, граф 1*10*10*10*10*10*10*10*10*10*10. У меня слабые результаты на 1<10<10<10<10<10.
Честным выводом из рассмотрения решений на тестах №1 и №2 из статьи было бы отрицание заявленного эпиграфа, поскольку на этих тестах "запросная" техника Игоря проигрывает на 1-2 порядка альтернативным алгоритмам.
Касательно нулевого количества на дуге, кстати, я тоже согласен, что это не зацикливание. При разузловании такая дуга на порождает потомков (порождает нулевое количество потомков), значит, не мешает корректному подсчету составляющих, т.е. не является критической ошибкой. У меня алгоритм проверки зацикливания как раз обнулял количество на ошибочных дугах, после чего разузлование корректно выполнялось. Игорь же просто не смотрит на количество при построении цепочек - ну, нравится ему лишняя работа...
Как-то так...
Ответили: (167) (172)
# Ответить
167. Ish_2 01.12.2010 16:16
(166) Спасатель ? Все разговоры - от лукавого.

Ко всем ! Просьба - не мешать !

Жду ответа Сергея , чтобы задать следующий вопрос.
# Ответить
168. ildarovich (файл скачал) 01.12.2010 16:26
(165) Игорь! Я опрометчиво согласился играть на Вашем поле, по Вашим правилам, при Вашем личном судействе (крайне необъективном!). Поскольку болельщики здесь безгласные и некому кричать "судью на мыло!", а пререкаться с Вами мне жаль времени - решайте сами, когда заканчивать матч. Но если дадите время, я воспроизведу в своей обработке все ошибки особенности Вашей обработки. Уверен, хоть это и не сделает ее лучше, на скорости практически не скажется.
Вы лично объявили разночтение в трактовках цикла в спецификациях принципиальным вопросом, а чем обоснуете?
Но это все "лирика". В следующем посте будет "физика".
Я бы отвечал быстрее, но Вы очень скупо описываете свои действия при тестировании. Лучше были бы .xml - выгрузки спецификаций. Так что пока подождите - воссоздаю условия теста.
Ответили: (169)
# Ответить
169. Ish_2 01.12.2010 16:34
(168) Мы обсуждаем только один вопрос :

ошибка (163) в определении зацикливания в Вашей текущей обработке

Вы отказываетесь её устранять ?

Ответьте "Да" или "Нет" и продолжим обсуждение дальше.
Ответили: (171) (175)
# Ответить
170. Ish_2 01.12.2010 17:26
(168) Всё ! Проехали.
Господа , Сергей и Арчибальд, я был бы вам очень благодарен если бы вы
со всей пристрастностью объявили мне о недостатках моей обработки.
# Ответить
171. ildarovich (файл скачал) 01.12.2010 17:42
(169) Устранять НЕ отказываюсь, но не ошибку, а несоответствие (опять!) выдачи Вашей и моей программы.
Это НЕ ошибка!!! Вот аргументы:
Есть два разных подхода: Ваш и мой.

Ваш подход: выдать пользователю 100 ? первых цепочек вершин, содержащих циклы;
Мой подход: выдать пользователю для ВСЕХ циклов по ОДНОЙ содержащейся в каждом цикле вершине.

В (163) Вы создали граф из дуг Г->Д, Д->Е, Г->Я, Я->Е, Е->Д, Е->Я. Этот граф содержит два цикла: Д->Е->Д и Я->Е->Я.
При моем подходе в выдаче содержались две вершины: Д, входящая в первый цикл и Е, входящая в оба. Это я считаю правильным.
Вы ошибочно считаете, что оператору поможет перечисление цепочек, содержащих циклы. Но - таких цепочек могут быть сотни тысяч!
В своем же тесте №3, (ничего не убирая! - не жульничайте!) добавьте связь ОшЕ00000002 -> Тест№3. Вы не увидите эту ошибку в Вашей выдаче,
хотя она будет только второй!!! Чтобы ее увидеть, Вам придется вывести не 100, а 100 001 ошибочных цепочек.
И только 100 001-ая будет содержать всего вторую ошибочную связь!

Так в каком подходе ошибка? В Вашем или моем? Ответьте аргументировано! Разберите мой пример!
Ответили: (172) (174) (175)
# Ответить
172. Ish_2 01.12.2010 18:19
(171) Один вопрос мы обсудили.
Плавно переходим к недостаткам ЗапросПротивРекурсии.epf

Что же означает (163) ?

Я уже повторяюсь. Но лучше плясать от печки. От постановки задачи.
Что есть зацикливание ?
Зацикливание есть факт когда узел выступает в качестве и "родителя" и "ребенка".
Обработка должна безусловно отобразить такие обнаруженные факты зацикливания.
Не "рассуждая" хорошее это зацикливание и его надо зафиксировать ,
или это "безвредное" зацикливание (с нулевым количеством ) и его можно не фиксировать.
Один из аргументов для такого подхода в (161) специально для Арчибальда(166) :
Теперь сравните что информативнее, полезнее для пользователя , работающего со спецификациями :
- при Вашей обработке пользователь ничего не узнает о явной ошибке зацикливания
если у "зациклившей" количество равно нулю.
- при моей обработке пользователь обязательно увидит зацикливание и сам определит что с ним делать .


Вопрос "Что делать с "безвредным зацикливанием" ?" - это не вопрос наших обработок графа.
Это вопрос пользователя, работающего с графом, или последущей обработки. Текущая обработка обязательно должна зацфиксировать зацикливание. И ВСЁ!

Я утверждаю , что любой другой подход "есть дорога в Ад", то есть (163).
Отсюда вытекают важнейшие следствия.
# Ответить
173. Ish_2 01.12.2010 19:03
Теперь следствия.
Обработка должна содержать АБСОЛЮТНЫЙ ("очень тупой"), а не относительный как у Сергея, контроль зацикливания. Далее. Мало иметь список ошибок - нужно строить их граф. Простой список малоинформативен и неудобен как для пользователя, так и для дальнейшей автоматической обработки. То есть , если вы "по-взрослому" ставите задачу для Заказчика ,вы должны понимать что от простого списка проку никакого и граф ошибок просто необходим.И уже на начальном этапе стало понятно , что затраты на ведение графа ошибок будут огромными.
Если вы "по-взрослому" ставите задачу для Заказчика , то конечно должны предусмотреть "отвязку" от слабости клиента (слабое быстродействие, ограниченный объем оперативной памяти и др.), т.е чем меньше кода на клиенте - тем лучше.

Эти соображения и легли в основу обработки ЗапросПротивРекурсии.epf и обеспечили как её недостатки, так и достоинства.
# Ответить
174. Ish_2 01.12.2010 19:26
(171)
Теперь конкретно Для Сергея.
(ничего не убирая! - не жульничайте!)...
Чтобы ее ( увидеть, Вам придется вывести не 100, а 100 001 ошибочных цепочек.


Кхе-кхе...
У меня действительно стоит выдавать только ПЕРВЫЕ 100 ошибок.
Заметьте , у меня содержится во временной таблице ПОЛНЫЙ граф ошибок , а выдается только 100.
Сколько хочу столько и выдам.
Я посчитал ,что 100 первых вполне достаточно для начала работы пользователя над ошибками.
Сделано это в демонстрационных целях и не более того .
Тестируя программу , я задал 1 000 000 ошибок и не дождался выполнения запроса по ошибкам (т.е. построения графа ошибок). С другой стороны , ничто не мешает БЫСТРО выдавать параллельно общее количество ошибок для информирования пользователя.
# Ответить
175. ildarovich (файл скачал) 01.12.2010 22:46
(169)
+(171) Завтра закончу, так как теперь нужно убрать дублирование функционала и заново протестировать...
Ответили: (176) (178)
# Ответить
176. Ish_2 02.12.2010 03:06
(175) Понял. Только не спешите.
Это уже совсем другая обработка. И другая история.
А эту тему мы завершим.Ок.
Ответили: (177)
# Ответить
177. ildarovich (файл скачал) 02.12.2010 12:04
(176) Почему? Я ведь делаю обработку под Ваши требования?

Вы признаете поражение? Признаете, что запрос проиграл рекурсии? Скажите об этом четко!

И еще ...
Мне вдруг пришло в голову, что Вы настаиваете на Вашем якобы правильном способе контроля зацикливания не из упрямства (каюсь, считал именно так), а просто потому, что не знаете классического способа такого контроля (ну, пропустили тему, с кем не бывает).

Потратьте несколько минут, проглядите по диагонали вольное изложение этого метода.

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

Метод решения:

1. Допустим, что ошибки независимы. Это дает возможность считать более вероятными сначала однократные, потом двухкратные, потом трехкратные ошибки и так далее. Все практические алгоритмы поиска ошибок построены на этом допущении.
2. В результате допущения 1 исходная задача становится оптимизационной: найти минимальное количество связей, разрыв которых делает граф ациклическим.
3. Оптимизационная задача 2 решается методами динамического прораммирования, например, методом ветвей и границ (МВГ). МВГ - это метод сокращенного (границами) перебора (ветвей). Сильно упрощая, можно сказать, что сначала мы размыкаем по одной связи, проверяя, не исчезла ли ошибка. В графе тест №3 на это понадобится максимум 0,122 х 510 дуг - максимум 50 секунд, а реально - гораздо меньше!

Что же дает этот метод решения: он выдает оператору не миллион циклических цепочек (пусть и в виде дерева - в нем Вы сами путаетесь - это говорит (163), где Вы были вынуждены размыкать правильные связи, чтобы показать двойную ошибку).
Он выдает чаще всего единственное правильное решение - ошибочную связь! В худшем (гораздо реже на практике) - некоторое множество связей, из которых оператор делает выбор.
Моя обработка только контролирует (определяет наличие) всех ошибок зацикливания, показывает диагностические признаки (симптомокомлекс) в максимально компактном виде, чтобы в дальнейшем можно было найти ошибку по-умному.

Ваш "наивный" метод делает только на первый взгляд больше. Избыток информации в данном случае - зло для оператора! В случае ста уровней в тесте №1 и зацикливания ОшГВ00000001 -> Тест №3 Ваша обработка
страшно сказать когда выдаст ГУГОЛ (10 в степени 100) цепочек циклов!
А моя обработка через 50 секунд выдаст результат разузлования и одну ошибку (Узел Тест №3 в цикле)!

Подход типа Вашего (запрос в цикле ??? - моветон!) немного выигрывает у рекурсии только в одном редком случае неповторения спецификаций.
Когда граф является ДЕРЕВОМ. Но и в этом случае он НЕ ДОЛЖЕН ПРИМЕНЯТЬСЯ!
Поскольку для этого специального случая, как я уже писал в этой теме раньше (поищите!) должны применяться специальные методы. Запрос будет к одной таблице без всяких циклов и соединений!
Менее чем за 10 секунд для дерева 1 111 111 он выдаст Вам результат разузлования!

По прежнему ждем, что Вы сделаете правильные выводы в аннотации к Вашей статье :D .
Ответили: (178) (184)
# Ответить
178. Ish_2 02.12.2010 12:15
(177) Обсуждение закончено. После драки кулаками не машут.
Ваша обработка тестировалась честно с Вашего согласия и по известным правилам.
У Вас было достаточно времени в МОЕЙ ТЕМЕ привести ВСЕ СВОИ аргументы в пользу СВОЕЙ обработки.
Вы собрались писать НОВУЮ обработку (175). Обсуждать её в своей теме я не намерен.
# Ответить
179. ildarovich (файл скачал) 02.12.2010 12:48
(178) Игорь! Вы не выполнили условия нашего спора. Кроме мелких придирок к моей обработке не привели никаких аргументов в защиту своей позиции (прежде всего своих результатов сравнительного тестирование времени разузлования двух обработок на разных тестах). Как еще Вас стыдить, я не знаю. Желаю просто не отмахиваться от новых знаний. Если Вы воспользуетесь моими советами - сделаете свою обработку лучше. Ведь если бы Вы внимательно прочитали мою статью и приняли на свой счет, вы бы не сделали примитивной ошибки - не "попали на миллион". Независимо от результатов, решать задачу мне было интересно.

Для всех остальных (кто дочитал до конца) сообщаю (позиция обоснована в моих постах в этой теме):

ВЫВОДЫ СТАТЬИ О ПРЕИМУЩЕСТВАХ ПРИВЕДЕННОГО ЗАПРОСА ПРОТИВ РЕКУРСИИ - НАГЛАЯ И СОЗНАТЕЛЬНАЯ ЛОЖЬ!!!
Ответили: (179) (180) (181)
# Ответить
180. Ish_2 02.12.2010 18:32
(179) Спокойно. Вы можете создать новую тему и там провести сравнительный анализ двух обработок и сказать , что Вы думаете о моей обработке и в чем преимущество Вашей. Подготовьтесь получше. Если в Вашей обработке не будет много ошибок , если статья покажется мне интересной - Я приду.
Попробуйте. Докажите свою правоту.
# Ответить
181. huse (файл скачал) 03.12.2010 00:51
(179) может и не сознательная ))))
# Ответить
182. huse (файл скачал) 03.12.2010 01:00
А вообще чем дольше работает программа, тем у Заказчика больше уверенности, что программист написал сложную программу. Тут конечно автор темы всех победил. Особенно если он _честно_ попробует объяснить Заказчику как именно производится разузлование - то Заказчик будет восхищен эрудицей и величиной мозга Автора, ведь ни один Заказчик так до конца и не поймет что же там происходит на самом деле.

PS Знаю один завод, купивший MRP за 70 млн.руб. Завидую черной завистью и записываюсь к Автору на курсы. )))))))))))))))))))
Ответили: (183)
# Ответить
183. Ish_2 03.12.2010 08:42
(182) Появился курсант Хьюз. Тогда продолжим.
Господа. Ни у кого из вас
ни у Владимира,
ни у Хьюза,
ни у Сергея ,
ни у Арчибальда не было никаких шансов.
Потому что ни один из вас не увидел ловушки в условии "безусловного контроля зацикленности".

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

Начинаем движение вслепую.

Ветка 1. А-Б-В- Г- Я_тоже - Е - Я_ТОЖЕ. На последнем сработало зацикливание , движение прекращаем.

Ветка 2. А-Б-В- Г- Я_тоже - Е - Д - Е.

Ветка 3. А-Б-В- Г- Д - Е - Д.

Ветка 4. А-Б-В- Г- Д - Е - Я_Тоже - Е

Итого З элемента (Е- дважды)

Только такой , самый "тупой" и надежный метод обхода дает постоянный состав зацикленных элементов Е,Д,Я_тоже НЕ ЗАВИСЯЩИЙ от порядка обхода.
Если же мы начнем "хитрить", чего-то оптимизировать при обходе, как в ваших алгоритмах , то потеряем элемент.
Причем "хитрый" вариант обхода может выдавать разный состав элементов в зависимости об порядка обхода.
Алгоритм Сергея, например, выдал только Е и Д.
А что это за контроль , который выдает разный, неполный состав зацикленных элементов.
Любому из вас я могу задать вопрос : "Чем потерянный Я_Тоже хуже , чем Е и Д ? Почему вы его не отловили ?". Действительно , раз пропущен зацикленный элемент - значит нарушено условие контроля зацикленности.

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

Я старался для вас , господа ! Надеюсь, вам понравилось.
Ответили: (184)

Прикрепленные файлы:

Гр6.PNG
# Ответить
184. ildarovich (файл скачал) 03.12.2010 10:50
(183) Игорь! Есть подходящий случаю анекдот, только не обижайтесь: "Что такое экзамен? - Разговор двух умных людей. А что, если один из них дурак? - Тогда другой не получит стипендию!".
Выводы, которые Вы сделали в (183)
Значит , чтобы выполнить условие контроля зацикленности в ваших алгоритмах нужно реализовать этот самый "тупой" контроль и так или иначе хранить все ветки графа. А это конец. Конец скорости, конец надежности (памяти клиента может и не хватить).

ОШИБОЧНЫ! Они опровергаются тем, что я написал в (177). Ну поверьте! Если действительно хотите понять, почему, я могу ответить не на форуме в Вашей теме, где Ваше непонимание Вы называете моими ошибками, а в личной переписке. Перечитайте (177) еще раз, напишите мне лично, что Вам непонятно, с чем Вы не согласны. Я постараюсь объяснить.
# Ответить
185. Ish_2 03.12.2010 10:59
Господа , я старался для вас ! И привел всего лишь СВОЙ взгляд !

Если вы хотите постараться для меня :
создавайте СВОИ темы,
спорьте,
опровергайте ,
придумывайте свои конкурсы ,
устанавливайте свои правила ,
шутите САМИ , на СВОИХ условиях и в СВОИХ темах !

А для тех , кто ничего не понял - последняя шутка автора :
http://forum.infostart.ru/forum24/topic36792/message403919/#message403919
# Ответить
186. tango 07.12.2010 18:06
Это болезнь 1снегов, мода ничего не знать, или вообще неизлечимо?
я вот об этом куске кода из сабжа:
//Цикл получения выходной таблицы
Для Счетчик =0 по КоличествоЦиклов+1 Цикл
Запрос.Текст = СтрЗаменить(ТекстЗапроса,"Исходная","ВремТаблица"+ Счетчик);
Запрос.Текст = СтрЗаменить(Запрос.Текст,"Последующая","ВремТаблица"+(Счетчик+1));
РезультатЗапроса = Запрос.Выполнить();
Если РезультатЗапроса.Пустой() Тогда
Счетчик = Счетчик + 1 ;
Прервать;
КонецЕсли;
КонецЦикла;

Что мешает гг коллегам увидеть здесь рекурсию? Может быть, то - что они не знакомы с содержательной частью этого термина?
Ответили: (188)
# Ответить
187. tango 07.12.2010 18:07
Игорь, ты рекурсивно строишь тело запроса, нихт ферштеен?
Ответили: (188)
# Ответить
188. Ish_2 07.12.2010 18:31
(186),(187) Миша, ты не горячись.
У меня даже родилась умная мысль : Много чего на много чего похоже.

Чтобы ты больше не путался - Пример для тебя.
Что такое "реккурентность" и что такое "рекурсия" ?
Реккурентность - это свойство какой либо последовательности.
Рекурсия - это вычислительный прием.
Пример, который ты привел(цикл в теме) подобен следующему:
н=0;
Пока Истина Цикл
     н=н+1;
КонецЦикла;  

В этом примере-Цикле порождающем натуральный ряд чисел мы наблюдаем реккурентность,
каждый последующий член последовательности зависит от предыдущего и отличается от него на единицу.
Но только сумашедший скажет , что мы здесь используем рекурсию(явно или неявно), как вычислительный приём.
По аналогии :

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

Последовательность получаемых временных таблиц также обладает свойством реккурентности,
Но получаем все эти таблицы с помощью ЦИКЛА. Рекурсии, как вычислительного приема здесь нет и в помине.
Никакого рекурсионного определения тела запроса - НЕТ.

Пример использования Рекурсии как вычислительного приема приводить не буду. Надеюсь , ненужно.
Ответили: (190) (194)
# Ответить
189. tango 08.12.2010 10:28
Есть, просто ты его довольно хитро (это комплимент) спрятал в запросы. Рекурсия - у тебя в запросах, и цикл ты прекращаешь, когда достигаешь конца именно рекурсии. Вот сейчас найду старенькую фишку - для упп, в предположении, что нет в спецификах нет кольцевых ссылок, и что специфики - сборочные (в тех условиях это было хорошее предположение). Там у меня в (явной) рекурсии на каждом уровне дерева создается запрос, выполняется, и, фактически, проверяется то же услолвие, что и у тебя. Ты вошел в рекурсию, создав первую таблицу, и "спрятал" ее, тесно переплетя с запросами. У меня - рекурсия явная, запросы - сами по себе. Но разница-то в чем, кроме того. что у тебя было время на 1сные изыски?

Прикрепленные файлы:

КомплектацияПолная.epf
# Ответить
190. Арчибальд 08.12.2010 10:30
(188)
Реккурентность - это рекурсивное определение функции. Они широко распространены в математике.

http://www.structur.h1.ru/recurs.htm
Ответили: (191) (193)
# Ответить
191. tango 08.12.2010 10:33
(190) пять баллов, Арчи
# Ответить
193. tango 08.12.2010 10:38
по ссылке (190): Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной.

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


У тебя, Игорь, косвенная рекурсия, только не через процедуру ку, а через запрос, что роли не играет. А терминальное условие у нас с тобой - одно и тоже.

Сдавайся, короче.
Ответили: (194)
# Ответить
194. Ish_2 08.12.2010 15:26
(192),(193) Мелькнула предательская мыслишка :
Арчибальд и Танго - хорошие люди, ерунду не скажут.
Может и ,правда, сдасться ?

Но жаль поста (188). Я же старался. Показать ,
что рекурентность это прежде всего свойство некоторой последовательности.
Мы говорим , что натуральный ряд рекрентен (обладает рекурентным свойством) , т.е.
каждый член этого ряда
А(N) = A(N-1)+1

Теперь мы говорим , мы получим натуральный ряд без рекурсии ( без этого вычислительного приема),
только при помощи "Цикла"
н=0;
Пока Истина Цикл
н=н+1;
КонецЦикла;


Я еще раз : торжественно вам объявляю ЗДЕСЬ НЕТ РЕКУРСИИ (вычислительного приема , т.е. обошлись без рекурсивного вызова процедуры)).

В этом же смысле , я заявляю в представленной обработке НЕТ рекурсии.
Есть обычный Цикл. С его помощью мы получаем последовательность таблиц ,
каждая последующая из которых получена из предыдущей определенным преобразованием.

О неявной рекурсии имело бы смысл говорить , если бы я организовал нечто
1. Цикл + стек
2. если бы имело место в моей процедуре
Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной.


В моей обработке нет ни того, ни другого.
Если вы настаиваете , что рекурсия в обработке присутствует , то тогда она присутствует и в коде получения натурального ряда.
Так что , уважаемые Танго и Арчибальд не сдамся. И не просите.
# Ответить
195. tango 09.12.2010 10:31
не сдашься, козе понятно
и даже плюсиков еще насшибаешь.
просто когда деревья станут маленькими посмотри на эту строчку:
РезультатЗапроса = Запрос.Выполнить();
в нем ты вызываешь процедуру ку
а в отличие от натурального ряда в бесконечном цикле (реккуррентность) ты имеешь и второй признак - точку выхода из цикла, окончание рекурсии.
Засим прошу извинить,. покидаю твои темы. Ну, пока деревья у тебя еще большие.
Ответили: (196)
# Ответить
196. Ish_2 09.12.2010 11:14
(195) Уходи , но помни : тебе я обязан появлением этой темы.
# Ответить
197. Abadonna 14.01.2011 14:37
"разузлование" номенклатуры в БП 1.6 (2.0)- это круто! ;)
Кто ж ее там заузловывал?
Ответили: (198) (199)
# Ответить
198. Арчибальд 14.01.2011 15:19
(197) Утро доброе :D
# Ответить
199. Ish_2 14.01.2011 15:58
(197) Будь здоров, Аркадий !
Среда какая-то была нужна для запуска и демонстрации.
Суть-то не в ней, а том как разузловывать.
Узко-практического значения статья и прикрепленный файл не имеют - это ты тонко подметил.
# Ответить
200. romansun 07.02.2011 19:04
Выскажусь и я чутка :)

Тема разузловывания, или, по другому, вычисление состава изделия не просто актуальна в перечисленных примерах (летательные аппараты, электровозы, суды) - она там корневая. Обсчет изделения (по комплектующим, по затрачиваемым на изделие материалам, по затрачиваемой работе на изделие и т.д. и т.п) осуществляется только на основании собранного состава изделия. Именно на эти расчеты ориентируются конструктора, технологи, экономисты, бухгалтеры и прочие службы.

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

В разное время были испробованы различные подходы к реализации задачи разузловки, вот некоторые самые интересные:

- полный сбор на T-SQL (рекурсивным запросом) и "выплёвывание" результата в темповый иерархический справочник. Если результат грамотно подготовлен, а именно уже раскидан по владельцам в иерархическую структуру еще в T-SQL, то простейший запрос уже 1С с "УПОРЯДОЧИТЬ ПО ИЕРАРХИИ" выдаёт дерево очень быстро. Метод хорош, но весьма сложен по реализации и поддержке;

- тоже самое, но с "выплёвыванием" результата в XML и получением дерева 1С уже из XML. Тоже неплохой вариант, ибо 1С работает с XML очень быстро;

- последний вариант, насколько я знаю, не внедрённый еще, заключался в заново перепродуманной :) и грамотно переделанной структуре базы с целью максисмального использования регистров и их мощных механизмов виртуальных таблиц. Вроде как давал по производительности самый лучший результат.
Ответили: (201) (203)
# Ответить
201. tango 07.02.2011 19:26
(200) будет не быстро, а очень-очень быстро, если структуру табличек спроектировать под конкретные паровозы. ххх каждого паровоза - свою табличку.
хренюшка в том, что хотят 1сную фишку, т.е чтоб и обновление на УПП накатывалось по одной кнопке, и чтоб паровозы летали
Ответили: (202) (204)
# Ответить
202. Abadonna 07.02.2011 19:35
(201) Желание разузловывать паровозы в 1С (хоть бы и в УПП) равносильно желанию безрукого импотента заняться онанизмом.
Тут 1С должна работать с СКД, которая в данном случае не Система Компоновки Данных, а Система Конструкторской (и технологической) Документации. И не фиг пытаться впихать в 1С абсолютно всё - подавится
Ответили: (205) (207)
# Ответить
203. Ish_2 07.02.2011 19:57
(200) Рассуждения общего плана возможны. Можно так , можно и эдак.
С одним только НО.
И это НО - центральное во всей теме. Как контролировать зацикленность в таблице описывающей ВСЕ изделия на предприятии :
Родитель,Ребенок, Количество.
Эта таблица компактна и удобна при хранении информации - всё в одном флаконе.
Но неудобна при получении таблицы разузлования.
При отсутсвии контроля зацикливания - задача тривиальна и малоинтересна.
При абсолютном котроле зацикливания всё становится не так просто.
К какому падению "алгоритмов" привело "легкое" отношение к контролю зацикливания можно почитать поднявшись вверх по комментариям. Представленный алгоритм в теме дает удовлетворительное быстродействие ~20сек на разузлования миллионного графа см.Тест №1 - что для реальных "паровозов" более чем приемлемо.
При этом никакие дополнительные, ускоряющие структуры хранения информации о графе не используются.

Возможно, поэтому статья опубликована также в разделе "1с рекомендует" .
# Ответить
204. Ish_2 07.02.2011 20:03
(201) "если структуру табличек спроектировать под конкретные паровозы. ххх каждого паровоза - свою табличку."

Это путь в никуда. В этих табличках будут повторяющиеся агрегаты. И при изменении состава одного агрегата придется менять все таблички, в которые он входит.
+ 1 [ Lara.Builova; ]
# Ответить
205. Ish_2 07.02.2011 20:05
(202) Спокойно. Без онанизма.
1с вполне пригодна для разузлования больших изделий.
В этой статье я скромно это доказываю.
Ответили: (206)
# Ответить
206. Abadonna 07.02.2011 20:09
(205) Никогда бухгалтерско-экономическая программа не сможет сравниться со специализированной. Заявляю это как инженер-конструктор по образованию. А желание 1С-ников войти в каждый дом с "Тайдом" мне тоже весьма понятно :)))
Ответили: (208)
# Ответить
207. tango 07.02.2011 20:10
(202) Аб :)
набери в гугле НЭВЗ - это заказчик.
набери http://www.evroconsult.ru/ - это как бы исполнитель.
я там не работаю, уже неделю.
завтра - выхожу на работу в приличной фирме.
# Ответить
208. Ish_2 07.02.2011 20:13
(206) Зачем мне специализированная , если я платформой 1с обойдусь ?
Это я тебе как инженер - электромеханик заявляю.
А электромеханики в этих вещах ого-го-го соображают.
# Ответить
209. Abadonna 07.02.2011 20:15
А электромеханики в этих вещах ого-го-го соображают.

Погугли "ДЗНВА", электромеханик :) Именно там я работал замфиндира по IT до отъезда в Москву
Ответили: (210) (211)
# Ответить
210. Ish_2 07.02.2011 20:20
(209)Погуглил. Кхе.. кхе.. Там трудности с разузлованием ?
Пусть обращаются. Помогу.
Ответили: (212)
# Ответить
211. tango 07.02.2011 20:21
(209) Аб, ты таки вырвался из КЯ! молодца, уважуха
# Ответить
212. tango 07.02.2011 20:22
(210) хи-хи. где, говоришь, твою "статью" рекомендуют?
# Ответить
213. Abadonna 07.02.2011 20:23
Там не было трудностей еще в век древней комплексухи 7.7, во времена только что появившейся бета-версии 8.0, тем более нет и сейчас. Команда моих проггеров снисходила до 1С, а не поднималась до ее "сверкающих высот" :D :D
# Ответить
214. Abadonna 07.02.2011 20:26
Аб, ты таки вырвался из КЯ!

Вот те на! Я думал все уж давно знают... Вырвался, инфаркт, вернулся. Давно уж
# Ответить
215. romansun 07.02.2011 22:20
Abadonna пишет:
Желание разузловывать паровозы в 1С (хоть бы и в УПП) равносильно желанию безрукого импотента заняться онанизмом.
Тут 1С должна работать с СКД, которая в данном случае не Система Компоновки Данных, а Система Конструкторской (и технологической) Документации. И не фиг пытаться впихать в 1С абсолютно всё - подавится


1С обсчитывает паровозы тока в путь :). В полном соответствии с ЕСКД выдает документацию, ведомости всякие и пр. Считает технологию и экономику. Это не УПП - у нас была полностью написанная софтина с нуля. Что-то типа аппиуса. Кто, кстати, видел аппиус в последнее время? Насколько быстро он считает тяжелые сборки?

Вопрос целесообразности написания своей конфы, а не использования чего-то готового, конечно, важен, но это чистый холивар :). Не каждое машиностроительное предприятие полного цикла, с несколькими тыщами слоняющихся по цехам и кабинетам людей готово перетряхивать свои бизнес-процессы ("дык так уже 30 лет работает и ничего") ради "какой-то там автоматизации". К сожалению, в большинстве случаев это так...

А вообще, 1С вполне нормально использовать для этих целей, поскольку легко интегрироваться с бухией, зарплатой и пр. В конце концов, в 1С можно накодить всё что угодно, были бы прямые руки,.. а прямой доступ к sql даёт вообще огромные возможности (хотя и возможностей 1С предостаточно).
Ответили: (219)
# Ответить
216. romansun 07.02.2011 22:52
tango пишет:
будет не быстро, а очень-очень быстро, если структуру табличек спроектировать под конкретные паровозы. ххх каждого паровоза - свою табличку.


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

Конечно, под каждое изделие никак "своих" табличек не делается :).

Циклические сборки, да - это весело :) Порой приходилось объяснять даже конструкторам, что класть пакет в сумку, сумку в чемодан, а чемодан в пакет нехорошо и работать такой паровоз не будет :).

Проблему цикличности можно отчасти решить тупо и просто, по-идиотски так (прошу не пинать!) - никакой даже самый большой паровоз не содержит, не содержал и не будет содержать более 7 уровней вложенности. Понимаете? :) Проверяем, скажем, на 12 циклов и всё - цикличность. Быстро и просто. Решение не математическое, а чисто практическое. Другое дело, что вопрос а в каком узле требует, да, дополнительных изысканий.

Возможно, для судов, например, всё не так радужно, конечно :)
Ответили: (217) (220) (221)
# Ответить
217. tango 07.02.2011 23:23
(216)"этот узел месяц назад", "под каждое изделие никак"
фактически - именно под каждый паровоз свой состав получается, с учетом замен, изменений расценок и т.д.

"7"
17 - реальная цифра, электровоз
Ответили: (218)
# Ответить
218. romansun 07.02.2011 23:51
(217)

17??!! Сурово!! (Что-то я даже засомневался по поводу своих семи, надо завтра уточнить у коллег). Может это с полной раскладкой каких-нить пультов управления, которые обычно идут как покупные изделия? Или какие-то иные принципы у конструкторов, ведь бывает, что и укрупняют узлы и, наоборот, разбивают.
# Ответить
219. Abadonna 08.02.2011 05:50
(215)
Кто, кстати, видел аппиус в последнее время? Насколько быстро он считает тяжелые сборки?

По поводу аппиуса спрошу у нашего проггера с КЭМЗа
У них как раз связка с УПП
# Ответить
220. Ish_2 08.02.2011 08:00
(216) Отлично ! Реальный человек попался .
Нужно не только выдать сообщение о цикличности, дескать , такой-то элемент зациклен, а также показать все зацикленные ветки графа. Чтобы пользователь сориентировался в графе и сам исправил ошибку. Вот как реализован интерфейс для пользователя в текущей теме см. рисунок ниже. Название элементов смысла здесь не имеет.
Показаны все зацикленные ветки, зацикленные элементы изображены красным. Журить пользователя ненужно - пользователь сам выбирая тот или иной элемент может интерактивно исправить спецификацию и избавиться от зацикленности.
Ответили: (224)

Прикрепленные файлы:

ИзображениеГрафаОшибок.png
# Ответить
221. Ish_2 08.02.2011 08:16
(216) Ну и еще. "Паровозы" и "электровозы" просто отдыхают по сравнению с задачей расчета бюджета крупной структуры. Консолидированный бюджет - это дерево, ветки которого бюджеты нижестоящих структур.
Здесь всё сложнее. И если при разузловании используется лишь движение "сверху - вниз" и применяется простое умножение, то здесь более сложные соотношения. В таких задачах особенно важно представить пользователю ясную картину расчета и возможного зацикливания.

Про "паровозы". Хотелось бы узнать про вашу софтину :
1. максимальное количество узлов при разузловании графа спецификаций (1 000 000 есть ?)
2. максимальное количество уровней графа
3. время разузлования
Ответили: (222) (223)
# Ответить
222. mrscylla 08.02.2011 11:28
Как бы то ни было, продуманная структура решающая конкретную конечную цель решает вопрос производительности. И в 1С тоже возможно получить все в разумные сроки.

Имею возможность представлять, то о чем говорит romansun, так как участвовал в разработке, задача там обособленная и изначально решалась с попыткой догнать семерых зайцев по дороге прихватить еще и слона. Поэтому все эти танцы с T-SQL и XML в итоге, с появлением временных таблиц в 1С, ушли в небытие.

Решилось все продуманной структурой решающей только то, что нужно решить (без слонов). Подготовленные данные поступали в СКД, а там уже и иерархия и все остальные прелести.

(221)
1. До миллиона может и не доходило, но план продукции на пол года под 800 тысяч был.
2. Уровней до 10.
3. На эти 800тыс. 40 секунд максимум на разузлование, далее смотря какой отчет СКД, простейший довольно быстро.

пс. на предыдущих вариантах все работало гораздо дольше, полугодовой план мог и по 20 минут курить бамбук (но там больше проблема блокировок была))) )
Кстати, тут еще вопрос железа ессно! )
Ответили: (223) (224)
# Ответить
223. romansun 08.02.2011 11:42
(221)(222)

Да, всё так - помощь зала помогла :). Сам я уже не фигурирую на том предприятии как 2 с лишним года - последней инфой не владею поэтому.

По поводу 'лишь движение "сверху - вниз"' скажу, что и в другую сторону тоже есть - задача применяемости как раз "снизу-вверх".
# Ответить
224. Ish_2 08.02.2011 12:38
(222) Интересно сравнить подходы.
Время указанное ~40 сек (+-5 ) суммарно соответствует у меня
1. Обработке 6-уровневого графа с миллионом уникальных узлов.
2. Выводу выходной плоской таблицы разузлования ( 1 000 000 строк) на форму.
3. Самое важное в это время входит абсолютный контроль зацикливания , подразумевающее построение полного дерева содержащего весь пройденный граф , а не только ветки содержащие зацикливания.

Так вот если пункт 3 у вас отсутствует (он многократно замедляет разузлование) или контроль зацикливания неабсолютен (облегчен) и пользователь после разузлования не имеет полной картины пройденного графа -
то , пожалуй, сравнивать нечего.
Другими словами, контроль зацикливания - это и есть тот самый слон, без которого публика заскучает.
См. рис. (220).
Ответили: (225)
# Ответить
225. mrscylla 10.02.2011 13:00
(224)
1. У нас до 10 уровней ветки бывали. Если "уникальных узлов" означает количество строк в линейной таблице вида "Родитель, Элемент, количество", то примерно схоже +/-
2. Аналогично. При этом полей в таблице ~ 40 (многие из них при разузловании рассчитываются и находятся по хитрому - это наш слон).
3.
К вопросу зацикливания я подошел намного проще.
Так как задача первоначально была посчитать нормативы, то такие ошибки как цикличность считаются очень грубыми и правятся на момент обнаружения.

Поэтому проверка цикличности происходит банально по достижению максимально допустимого уровня вложенности. Например 30.
При обнаружении данного факта, разузлование останавливается и запускается процедура разбора того, что именно тут зациклилось, благо данные то все вот они во временных таблицах. Структура позволяет отследить каждый элемент по веткам дерева. Далее обнаруживается ветка с повторяющимися спецификациями и выводит их пользователю на дознание. "Ошибка: Спецификация "такая то" циклична! Разузлование невозможно!".

Конструктор видя такой момент, тут же правит спецификацию и далее все ок.
В итоге на дальнейших этапах использования разузлования ошибок не возникает. Конструктор проверяет свои спецификации до их утверждения.

Публика счастлива :)
Ответили: (226)
# Ответить
226. Ish_2 10.02.2011 14:05
(225) Понял . Такой грубый приём при контроле зацикливания как ограничение уровней может быть эффективным в данной конкретной задаче. Судя по всему там все довольны.

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

Кроме того ограничение уровней неэффективно для случая когда например :
все ветки графа имеют уровнеь вложенности 20 , а одна или несколько 67 (пример невыдуманный).
Ответили: (228)

Прикрепленные файлы:

Гр6.PNG
# Ответить
227. romansun 10.02.2011 14:22
[перепост отсюда]

В целом, не везде же сложные и большие сборки шоп проверять их на цикличность-то.

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

Вот и всё. Почему бы рекурсивно не собрать применяемость не ставя перед собой глобальные задачи? Я придерживаюсь позиции, что в каждом конкретном случае необходимо решать отдельно, ибо 1С - это не фундаментальная наука, а прикладное программирование. ))

PS. Как же решает этот вопрос аппиус таки? Всё-таки серьёзная коммерческая разработка, они ж по идее не дожны "опуститься" до уровня прямолинейных решений. ))
Ответили: (229)
# Ответить
228. mrscylla 10.02.2011 14:49
(226)
Да действительно случаи у нас совершенно разные. У нас задача была по производству где такого рода ситуация, называется заимствованием и вполне нормальна и не является цикличностью.

У вас же видимо с бюджетированием что то связанное?
Ответили: (229)
# Ответить
229. Ish_2 10.02.2011 15:39
(227),(228) Просто целью публикации было не показать какое-то частное решение (для железных ящиков, например или бюджетирование) , а описать некий общий подход к решению широкого класса задач с разузлованием. Отсюда и жесткое требование абсолютного контроля зацикленности, параллельное построение полного графа , который можно показать пользователю в виде дерева на форме.
Ну, а в каждом конкретном случае , разумеется , такой контроль можно или отключить или "облегчить".
# Ответить
230. Kaperang 14.11.2011 16:41
Здравствуйте, коллеги!
С огромным интересом прочитал статью о разузловании.
У меня вопрос практического характера.
Сейчас потихонечку пишем для собственных нужд конфигурацию для автоматизации учета входящих заявок в ИТ-отдел.
В основе лежит объект "Работа" типа "Задача".

К сожалению, обнаружилось, что данный вид объекта ("Задача") не поддерживает иерархичность, а нам очень хочется реализовать именно иерархичность задач.

Например: корневая задача "Установка принтера" имеет четыре вложенные задачи - "Поиск и согласование модели", "Оформление оплаты", "Оформление сопровождающих документов", "Установка и настройка".
В идеале, количество уровней должно быть неограниченным.

Добавил для объекта "Работа" (тип "Задача") реквизит ссылочного типа ("Работа") - "Родитель".

Возникла задача графического отображения дерева задач. Сделал формирование дерева рекурсией с выводом на экран в дерево значений.
Работает, однако, медленно.
У меня следующий вопрос:
В 8.2 можно для ДинамическогоСписка формы списка указать произвольный запрос.
Если туда подставить запрос, выдающий на выходе иерархическо дерево задач по реквизиту "Родитель", то должно получиться очень красиво.
Вторую неделю бьюсь, никак не могу сформулировать нужный запрос.
Подскажите, пожалуйста, коллега, реализуема ли в принципе такая задача средствами запроса и, если да, то в каком направлении копать.
Ответили: (231)
# Ответить
231. Ish_2 15.11.2011 09:41
(230) Как я понимаю стоит задача вывести на форму дерево из запроса с итогами.
Посмотрите здесь http://infostart.ru/public/79992/
Сравниваются два варианта вывода дерева в табличное поле.
# Ответить
232. Kaperang 15.11.2011 18:19
Попробую пояснить на примере:
имеется исходная таблица из двух колонок - "Задача" и "Родитель". (см.картинку "Исходные данные").

В соответствии со статьей применяем к ней запрос вида:
"ВЫБРАТЬ
ТЗ.Родитель,
ТЗ.Задача
ПОМЕСТИТЬ ТЗ
ИЗ
&ТЗ КАК ТЗ
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
ТЗ.Задача КАК Задача1,
ТЗ1.Задача КАК Задача2,
ТЗ2.Задача КАК Задача3,
ТЗ3.Задача КАК Задача4
ИЗ
ТЗ КАК ТЗ
ЛЕВОЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ1
ЛЕВОЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ2
ЛЕВОЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ3
ПО ТЗ2.Родитель = ТЗ3.Задача
ПО ТЗ1.Родитель = ТЗ2.Задача
ПО ТЗ.Родитель = ТЗ1.Задача
ИТОГИ
ВЫБОР
КОГДА Задача2 ЕСТЬ NULL
ТОГДА Задача1
КОГДА Задача3 ЕСТЬ NULL
ТОГДА Задача2
ИНАЧЕ Задача3
КОНЕЦ КАК Задача4
ПО
Задача1,
Задача2,
Задача3
;

////////////////////////////////////////////////////////////­////////////////////
УНИЧТОЖИТЬ ТЗ"

На выходе получаем не очень понятное, а точнее, совсем непонятное дерево значений (см. картинку "Что получилось")

А то, что мне надо нарисовано на картинке "Что надо".

На всякий случай приложил обработку, с помощью которой проводил эксперименты над таблицой значений.
Ответили: (234)

Прикрепленные файлы:

исходные данные.JPG
что получается.JPG
что надо.JPG
ПостроениеИерархическогоДерева.epf
# Ответить
233. Kaperang 15.11.2011 19:08
Покурил статью еще. Переделал запрос на:

"ВЫБРАТЬ
ТЗ.Родитель,
ТЗ.Задача
ПОМЕСТИТЬ ТЗ
ИЗ
&ТЗ КАК ТЗ
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
ВЫБОР
КОГДА ТЗ2.Задача ЕСТЬ NULL
ТОГДА ТЗ1.Задача
КОГДА ТЗ3.Задача ЕСТЬ NULL
ТОГДА ТЗ2.Задача
КОГДА ТЗ4.Задача ЕСТЬ NULL
ТОГДА ТЗ3.Задача
ИНАЧЕ ТЗ4.Задача
КОНЕЦ КАК Поле1,
ВЫБОР
КОГДА ТЗ2.Задача ЕСТЬ NULL
ТОГДА NULL
КОГДА ТЗ3.Задача ЕСТЬ NULL
ТОГДА ТЗ1.Задача
КОГДА ТЗ4.Задача ЕСТЬ NULL
ТОГДА ТЗ2.Задача
ИНАЧЕ ТЗ3.Задача
КОНЕЦ КАК Поле2,
ВЫБОР
КОГДА ТЗ2.Задача ЕСТЬ NULL
ТОГДА NULL
КОГДА ТЗ3.Задача ЕСТЬ NULL
ТОГДА NULL
КОГДА ТЗ4.Задача ЕСТЬ NULL
ТОГДА ТЗ1.Задача
ИНАЧЕ ТЗ2.Задача
КОНЕЦ КАК Поле3
ИЗ
ТЗ КАК ТЗ1
ЛЕВОЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ2
ЛЕВОЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ3
ЛЕВОЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ4
ПО ТЗ3.Родитель = ТЗ4.Задача
ПО ТЗ2.Родитель = ТЗ3.Задача
ПО ТЗ1.Родитель = ТЗ2.Задача
ИТОГИ ПО
Поле1,
Поле2,
Поле3
;

////////////////////////////////////////////////////////////­////////////////////
УНИЧТОЖИТЬ ТЗ"

Теперь выдает следующий результат - см. картинку "Что получилось - 2". Уже гораздо ближе.
Но все равно, еще не совсем то - нужно - см.картинку "Что надо"

Прикрепленные файлы:

что получается - 2.JPG
что надо.JPG
# Ответить
234. romansun 15.11.2011 19:15
(232)
так нахаляву, запросом, вот такое дерево, как в что надо.JPG вы не получите.. это возможно только если б у вас был иерархический справочник и вы б писали, скажем, УПОРЯДОЧИТЬ ПО <тра-ля-ля> ИЕРАРХИЯ

в запросе без иерархии, только итогами, у вас будет, как бы это сказать, одинаковые по структуре ветки. Т.е. в ветке "ААА" три уровня, значит и везде три уровня... Ибо ИТОГИ ПО работают на все строки, а не только на некоторые ж :). По сути, на желаемом скрине сейчас "ИТОГИ ПО а, б, в" и "ИТОГИ ПО г, д" как-то оказались вместе :)

Насколько я правильно понял и помню прочитанную Хрусталёву, в СКД как раз таки можно замутить свою иерархию на основе табличного представления.
Ответили: (240) (241)
# Ответить
235. romansun 15.11.2011 19:18
новый скрин лучше, да... но максимум чего вы достигнете, это сведете данные в одну колонку... собственно, статьи все про это

т.е. колонки 2 и 3 у вас перейдут на соответствующие позиции в колонке 1... Но полностью нужный вид таким образом получить не получится.
Ответили: (236) (237)
# Ответить
236. Kaperang 15.11.2011 20:05
(235)"... -- Г-голубчики, -- сказал Федор Симеонович озадаченно, разобравшись
в почерках. -- Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал,
что она н-не имеет р-решения.
-- Мы сами знаем, что она не имеет решения, -- сказал Хунта,
немедленно ощетиниваясь. -- Мы хотим знать, как ее решать.
-- К-как-то ты странно рассуждаешь, К-кристо... К-как же искать
решение, к-когда его нет? Б-бессмыслица какая-то...
-- Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица
-- искать решение, если оно и так есть. Речь идет о том, как поступать с
задачей, которая решения не имеет. Это глубоко принципиальный вопрос..."
Аркадий и Борис Стругацкие. "Понедельник начинается в субботу"
# Ответить
237. Kaperang 15.11.2011 20:08
(235) А если серьезно: может быть, я неправильно понял, но данная статья, как мне показалось, посвящена решению задач, аналогичных моей. И судя, по всему, успешно. Вот только не могу пока докопаться, как :(
Ответили: (238) (242)
# Ответить
238. Ish_2 15.11.2011 21:56
(237) Чег-го то странное ... Текст -то текущей обработки для БП 2.0 открыт.
Можно поиграться и задавая ошибки зацикливания смотреть как они отображаются в дереве, т.е. какого вида получается дерево
Такое отображение достигается
1. в результате выгрузки запроса с итогами в дерево
2. при помощи процедур событий в табличном поле.
Ответили: (239)
# Ответить
239. Ish_2 15.11.2011 22:02
(238) Сейчас сам посмотрю как это сделано.
# Ответить
240. Ish_2 15.11.2011 22:13
(237) В (234) всё верно . Чисто запросом с итогами вы такое дерево НЕ получите.
Обычный запрос с всеми итогами выгружается в дерево на форме.
Почему же получается картинка такая "что надо" ?
Нужно посмотреть процедуру в модуле формы
ОшибкиПриВыводеСтроки(Элемент, ОформлениеСтроки, ДанныеСтроки)
В этой процедуре найдите строки
 	КодТекНоменклатуры = ДанныеСтроки["Уровень"+ДанныеСтроки.Уровень()];
	Если Не ЗначениеЗаполнено(КодТекНоменклатуры) Тогда
	  //ОформлениеСтроки.Ячейки.Уровень0.Видимость = Ложь;
	  ДанныеСтроки.Родитель.Строки.Удалить(ДанныеСтроки);
    Иначе
...Показать Скрыть


Так при выводе строки удаляются ненужные(пустые ветки).
Топорно , может быть, но для демонстрационной версии - вполне сойдет.
Получается , что дерево очищается от лишних веток только в видимой области.
Эта небольшая хитрость вызвана вот чем . У меня дерево может содержать до миллиона веток.
Если бы я очищал дерево в цикле перед выводом на форму , то было бы совсем грустно.
С другой стороны , а что нужно пользователю ? Нужно видеть правильное дерево.
Ну так он его и видит . А то что он не видит хм.. ему и не нужно.
Ответили: (242)
# Ответить
241. Ish_2 15.11.2011 22:42
(234)
Насколько я правильно понял и помню прочитанную Хрусталёву, в СКД как раз таки можно замутить свою иерархию на основе табличного представления.


Ты ничего не напутал ?
Если имеется таблица с двумя колонками
Родитель , Ребенок
то ты утверждаешь , что такую иерархию "можно замутить" в СКД ?
Не зли меня.
Ответили: (243)
# Ответить
242. romansun 15.11.2011 22:50
(237)
ну там статья у Ish_2 в основном про сравнение скорости вывода дерева из результата запроса и через СКД. Вывод дерева из результата выполнения запроса сурьёзно тяжелее чем аналогичные действия в СКД. Это уже зафиксированный факт :)

а тут мы говорим про сам приём, когда в ИТОГИ ПО колонки "заводятся" в одну путём манипуляций с ВЫБОР КОГДА ТОГДА. На скрине
колонки 1,2 и 3 таким образом заводятся в колонку 4. Это позволяет получать привычное по виду дерево уже в самом запросе. К слову, на скрине надо было "поле4" поставить первым в выборке для наглядности... А так всю красоту не видно ))

Но никакой такой или иной способ не позволит получить разноструктурные ветки в одном дереве в запросе. Поэтому дальнейшую обработку, если кому надо, осуществляют уже по готовому дереву после вывода. В частности речь идет об убирании лишних итоговых строк, о чем в (240) и написано.
# Ответить
243. romansun 15.11.2011 23:03
(241)

дык мож и напутал, я ж Хрусталеву под подушкою не держу

я говорю про что, собственно, вот, к примеру, дерево вида как из запроса

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


мы в неиерархическом справочнике фиг получим. Это как раз тот вид, который интересует Kaperang. Но, что-то на тему иерархии и получения какой-то там "своей" иерархии я у Хрусталевой видел. Признаю, эта глава меня не интересовала и я её просто пролистал. Если был неправ, готов покаяться в ереси.
Ответили: (244)
# Ответить
244. Ish_2 16.11.2011 00:00
(243)
1. Таблица с двумя колонками :
Родитель, Ребенок
содержит ПРОИЗВОЛЬНЫЙ ГРАФ.
В котором возможно зацикливание, возможна ситуация, что Ребенок принадлежит двум различным Родителям.
Возможны какие угодно кольца.
Тут ни Хрусталева , ни СКД не помогут. Мало того , НЕ МОГУТ помочь в принципе.

2. Иерархический справочник описывается ДЕРЕВОМ (частный случай графа).
В нём , описанные выше случаи невозможны по определению.
Нет зацикливания, Ребенок может принаждежать только одному родителю и проч.
Поэтому для ДЕРЕВА , и только для него, возможно применение СКД .
# Ответить
245. Kaperang 16.11.2011 13:37
Мдя....получается запрос, оптимизируй -не оптимизируй, вернет лишь полуфабрикат разузлования. Который надо потом будет еще дорабатывать напильником.
Хотя, думаю, меня и такой вариант устроит.
Добавил в свою тестовую обработку две процедуры, реализующие чистку дерева значений на лету. От себя добавил проверку на строк уровень ниже, чтобы сразу избавиться от ненужных плюсиков.
   Процедура ДеревоЗначенийПриВыводеСтроки(Элемент, ОформлениеСтроки, ДанныеСтроки)
	
	
	Если ДанныеСтроки <> Неопределено Тогда 
		УбратьЛевыхРодителей(ДанныеСтроки);
		Для каждого Ветка Из ДанныеСтроки.Строки Цикл
		   УбратьЛевыхРодителей(Ветка);
		КонецЦикла; 
	КонецЕсли;
	
		
КонецПроцедуры

Процедура УбратьЛевыхРодителей(ДанныеСтроки)
	
		ДанныеРодителя = ДанныеСтроки["Поле"+(ДанныеСтроки.Уровень()+1)];
		Если Не ЗначениеЗаполнено(ДанныеРодителя) Тогда
			ДанныеСтроки.Родитель.Строки.Удалить(ДанныеСтроки);
		КонецЕсли;
	
КонецПроцедуры
...Показать Скрыть


Итоговый вариант запроса выглядит так:
ВЫБРАТЬ
	ТЗ.Родитель,
	ТЗ.Задача
ПОМЕСТИТЬ ТЗ
ИЗ
	&ТЗ КАК ТЗ
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	"" КАК Поле4,
	ВЫБОР
		КОГДА ТЗ2.Задача ЕСТЬ NULL 
			ТОГДА NULL
		КОГДА ТЗ3.Задача ЕСТЬ NULL 
			ТОГДА NULL
		КОГДА ТЗ4.Задача ЕСТЬ NULL 
			ТОГДА ТЗ1.Задача
		ИНАЧЕ ТЗ2.Задача
	КОНЕЦ КАК Поле3,
	ВЫБОР
		КОГДА ТЗ2.Задача ЕСТЬ NULL 
			ТОГДА NULL
		КОГДА ТЗ3.Задача ЕСТЬ NULL 
			ТОГДА ТЗ1.Задача
		КОГДА ТЗ4.Задача ЕСТЬ NULL 
			ТОГДА ТЗ2.Задача
		ИНАЧЕ ТЗ3.Задача
	КОНЕЦ КАК Поле2,
	ВЫБОР
		КОГДА ТЗ2.Задача ЕСТЬ NULL 
			ТОГДА ТЗ1.Задача
		КОГДА ТЗ3.Задача ЕСТЬ NULL 
			ТОГДА ТЗ2.Задача
		КОГДА ТЗ4.Задача ЕСТЬ NULL 
			ТОГДА ТЗ3.Задача
		ИНАЧЕ ТЗ4.Задача
	КОНЕЦ КАК Поле1
ИЗ
	ТЗ КАК ТЗ1
		ЛЕВОЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ2
			ЛЕВОЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ3
				ЛЕВОЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ4
				ПО ТЗ3.Родитель = ТЗ4.Задача
			ПО ТЗ2.Родитель = ТЗ3.Задача
		ПО ТЗ1.Родитель = ТЗ2.Задача
ИТОГИ
	ВЫБОР
		КОГДА Поле2 ЕСТЬ NULL 
			ТОГДА Поле1
		КОГДА Поле3 ЕСТЬ NULL 
			ТОГДА Поле2
		ИНАЧЕ Поле3
	КОНЕЦ КАК Поле4
ПО
	Поле1,
	Поле2,
	Поле3
;

////////////////////////////////////////////////////////////­////////////////////
УНИЧТОЖИТЬ ТЗ
...Показать Скрыть


Результат выполнения - в картинке "Что получилось - 3". Если снять признак "Видимость" с колонок "Поле 1...3", то практически идентичен тому, что мне было нужно.

Прикрепленные файлы:

что получается - 3.JPG
# Ответить
246. Kaperang 16.11.2011 14:07
Изложенный выше запрос работает всего с двумя уровнями вложенности.
Теперь, насколько я понимаю мне, для того чтобы можно было использовать данное решение на практике, нужно еще две функции:
первая - возвращает цифрой количество уровней вложенности.
вторая - по полученной от первой функции цифре генерит текст запроса с нужным количеством уровней вложенности и подсовывает его в свойство "Запрос" динамического списка.
# Ответить
250. stoptime 29.02.2012 17:57
Спасибо использую на практике подобный подход уже с полгода. могу сказать слово с поре рекурсия - запрос..у меня однозначно запросы работаю быстее...изделия 1-2 тыс. материалов, до 10 уровней вложености. Каждое изделие с индивидуальными особенностями, план производсва около 50 изделий в месяц. планы потребностей в материалах и прочие групповые отчеты у меня таким образом строятся быстрее. рекурсия пороздала намного клиент серверных запросов...с ней план закупок готовился 6-10 минут, теперь 30 сек. причем 28 из них тратится на построение самой формы отчета.
как то так.
Ответили: (251)
# Ответить
251. Ish_2 29.02.2012 18:03
(250) Ну, да... вопрос ясный.
Только жаль , что "те бои уж отшумели давно.."
# Ответить
252. Krabat 12.03.2012 16:55
Спасибо.
Использую такой же принцип разузлования давно (в СУБД, но не в 1С), количество номенклатуры около 50000, уровень вложенности спецификаций 9-10, с получением пооперационного цикла (последовательность операций по каждой номенклатуре) уровень вложенности возрастает до 50-70.
При реализации в 1С сходной проверки на зацикливание столкнулся со следующей проблемой - ограниченность длины СтрокиКодов в 1024 знака. При превышении будет ошибка на неправильные параметры "+", да и ПОДОБНО на клиент-серверной реализации с длинными неограничеными строками не рекомендуется использовать из-за особенностей реализации (по крайней мере на MS-SQL).
Поскольку в моем случае длина кода(однозначно определяющее уровень вложения) + символ разделения, достаточно большая, ограничение действует уже на 10 уровне.
Сталкивался ли кто с подобной проблемой и есть ли какие-нибудь мысли как реализовать проверку по другому, не выходя за рамки запросной концепции.
з.ы. в своем случае длину кода к сожалению уменьшить не могу.
Ответили: (253)
# Ответить
253. Ish_2 13.03.2012 14:22
(252) Согласен. У Вас сработало ограничение на длину строки в SQL.

Что имеем в типовых конфигурациях 1с ? Длина кода+ 2 символа "%" = 12 символов.
Получаем что максимальная вложенность 1024/12 ~ 85.
То есть применимо в огромном подавляющем количестве случаях.
Даже трудно представить граф с уровнем 85 в практических задачах.

В Вашем случае , ничего кроме простого и очевидного на ум не приходит :
ввести новое дополнительное уникальное поле длиной 10 символов для идентификации объекта и использовать его при построении графа.
# Ответить
254. Krabat 15.03.2012 12:49
Поскольку из-за постановки задачи ключ уникальности составной (код объекта + код характеристики + код операции, да еще с разграничивающими символами), то к сожалению ввод дополнительного поля для еще одного кода объекта ничего не дает.
Но направление понятно - каким-то образом сократить размер текста, определяющего уникальность элемента, что бы уложиться в ограничение.
Однако результат получается нестабильный - добавиться еще один уровень вложения и престанет работать...
С чистым составом - все хватает, с операционным составом сложных сборок - совсем другой разговор.
# Ответить
255. toypaul 22.02.2013 15:38
Инетерсная методика. Сейчас пробую посчитать потребность сырья с ее помощью. На одной позиции файловый вариант считает 5 сек. 3 уровня вложенности. Что-то мне кажется долго. Нет? Плюс надо будет адаптировать алгоритм под несколько позиций в исходной таблице, плюс под релиз УПП где не владелец, а таблица выходных изделий.
# Ответить
256. toypaul 22.02.2013 15:56
плюс основные спецификации не учитываются в алгоритме
Ответили: (257)
# Ответить
257. Ish_2 22.02.2013 18:34
(256) Версия для БП 2.0. Для УПП нужно слегка переделать.
Дело не в этих мелочах. Сообщите если не трудно максимальный уровень вложенности.
Интерес представляют эксперименты в УПП для графа уровня не ниже 8-9 и количеством узлов не менее миллиона.
Предполагаю, что общее время разузлования в таком случае не превысит на "среднеофисном клиент-сервере" 1 мин.
# Ответить
Внимание! За постинг в данном форуме $m не начисляются.
Внимание! Для написания сообщения необходимо авторизоваться
Текст сообщения*
Прикрепить файл