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

05.07.11

Учетные задачи - Логистика, склад и ТМЦ

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

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

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

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

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

 


§ 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. Эти авторы  разными способами и с разной силой толкали к пониманию новой для меня задачи "разузлования".Спасибо. 

См. также

SALE! 20%

Автоматический заказ поставщику в 1С: загрузка прайсов и анализ цен поставщиков для УТ 10.3, УТ 11, КА2, УНФ, УПП, ERP, Розница 2

Бюджетирование и планирование Оптовая торговля Розничная торговля Логистика, склад и ТМЦ Анализ продаж Платформа 1С v7.7 Платформа 1С v8.3 1С:Комплексная автоматизация 1.х 1С:Управление торговлей 10 1С:Розница 2 1С:Управление производственным предприятием 1С:Управление нашей фирмой 1.6 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Розничная и сетевая торговля (FMCG) Оптовая торговля, дистрибуция, логистика Беларусь Украина Россия Казахстан Управленческий учет Платные (руб)

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

28500 22800 руб.

21.04.2017    90159    105    39    

190

Модуль "Ответственное хранение" или фулфилмент (FBS / FBO) для 1С:УТ 11.5, КА 2.5, ERP 2.5

Логистика, склад и ТМЦ Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Оптовая торговля, дистрибуция, логистика Управленческий учет Платные (руб)

Модуль "Ответственное хранение" для 1С (УТ 11.5, КА 2.5, ERP 2.5) позволяет организовать учет ответственного хранения товаров с весовыми характеристиками, в том числе со сроком годности и личным кабинетом Поклажедателя. Модуль реализован в виде расширения конфигурации, устанавливается в режиме 1С:Предприятие 8 за 5 минут по инструкции, что позволяет оставить конфигурацию 1С на стандартной поддержке и продолжать получать стандартные обновления от фирмы "1С".

60000 руб.

09.06.2020    34299    27    57    

54

SALE! 10%

Загрузка номенклатуры из Excel в УТ11, КА 2, ERP 2, Розница 2. Дополнительные реквизиты и сведения, характеристики, картинки, цены, остатки

Загрузка и выгрузка в Excel Розничная торговля Логистика, склад и ТМЦ Ценообразование, анализ цен Прайсы Платформа 1С v8.3 1С:Комплексная автоматизация 1.х 1С:Розница 2 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Управленческий учет Платные (руб)

Загрузка из файлов xls, xlsx, ods, csv, mxl в УТ11, КА 2, ERP 2, Розница 2. Задействованы все возможности конфигурации - заполнение реквизитов номенклатуры, дополнительных реквизитов и сведений, характеристики, доп.реквизиты и сведения характеристик. Дополнительные обработки для расширения возможностей.

10560 9504 руб.

29.10.2014    210129    620    524    

439

Загрузка номенклатуры c картинками (несколько потоков одновременно) и сопутствующими данными в базу и любые документы из yml, xls, xlsx, xlsm, ods, ots, csv для УТ 10.3, УТ 11 (все), БП 3, КА 2, ERP 2, УНФ 1.6/3.0, Розница 2

Загрузка и выгрузка в Excel Логистика, склад и ТМЦ Ценообразование, анализ цен Файловый обмен (TXT, XML, DBF), FTP Платформа 1С v8.3 1С:Бухгалтерия 2.0 1С:Управление торговлей 10 1С:Розница 2 1С:Управление нашей фирмой 1.6 1С:ERP Управление предприятием 2 1С:Бухгалтерия 3.0 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х 1С:Управление нашей фирмой 3.0 Платные (руб)

Эволюция не стоит на месте - новая удобная версия функциональной обработки для Вашего бизнеса! Что же Вы получаете? Удобный и интуитивно понятный интерфейс с 3-мя этапами работы. 2 режима - автоматический и ручной. Чтение XLSX, XLSM, CSV, XML/YML форматов без офиса, на любом сервере! Визуальное связывание колонок файла и реквизитов простым перетаскиванием колонок. Создание или обновление номенклатуры с иерархией, характеристик, доп. реквизитов, упаковок, загрузка практически неограниченного количества картинок на одну номенклатуру (с возможностью загрузки в несколько потоков одновременно), с хранением в томах или в базе. Загрузка номенклатуры поставщиков или поиск по их данным номенклатуры. Загрузка доп. реквизитов в характеристики. Загрузка штрихкодов с генерацией новых. Создание элементов справочников и ПВХ "на лету" для выбранных реквизитов. (Обновление от 11.12.2023, версия 9.5 - 9.9)

13200 руб.

20.11.2015    150698    367    375    

501

AS WMS: автоматизация склада с адресным хранением с помощью ТСД

Логистика, склад и ТМЦ Платформа 1С v8.3 Россия Платные (руб)

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

40000 руб.

26.07.2023    3209    13    0    

8
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
97. Ish_2 1104 26.11.10 18:14 Сейчас в теме
(95)+ Сам посуди , элемент Эл20 может в встретиться в 1000 спецификаций и лишь в одной из них он зациклен. Я его тогда не найду по информации "Корень - Эл20"
99. Арчибальд 2706 26.11.10 18:26 Сейчас в теме
(97) Зачем мне все ветки? Если в графе есть дуга с началом в Эл20 и концом в любом из предков Эл20, скажем, Эл50, ты предлагаешь мне перечислить все цепочки от Эл50 до Эл20? Ошибка-то одна, ее и фиксим, т.е. обрезаем дугу и сообщаем ее начало и конец (см. рисунок в 95 посте). А сколько различных циклов порождает эта ошибка - зачем это считать?
101. Ish_2 1104 26.11.10 18:42 Сейчас в теме
(99) Специально для тебя приготовлю простейшее изображение варианта графа с ошибкой зацикливания ,
ты мне мне ответишь какую ветку (в виде строки выдаст твоя обработка).
А пока другой пример попроще,из моей обработки.
Номенклатура "Тест №1 "Ошибки" была специально зациклена на 7 уровне.
И программа выдала все ветки ошибок.
Прикрепленные файлы:
102. Арчибальд 2706 26.11.10 18:46 Сейчас в теме
(101) Уж пришли тогда текстовый файл

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

Загружу и запущу.
103. Ish_2 1104 26.11.10 18:53 Сейчас в теме
(102) Отвлекут минут на 10. Скоро отвечу.
105. Ish_2 1104 26.11.10 19:23 Сейчас в теме
(102) Посмотри на этот пример . Эл 20 - встречается в графе 4 раза.
В предыдущем посте я неправильно сформулировал .
Я ожидаю увидеть у тебя две ошибочных ветки в виде строк :
Корень-Эл1-Эл20-Эл21-Эл20;
Корень-Эл2-Эл3-Эл20-Эл21-Эл20;
Почему ?
Потому что , что же я буду лазить по всем спецификациям и искать где он еще встречается ?
Прикрепленные файлы:
107. Ish_2 1104 26.11.10 19:32 Сейчас в теме
(102) А может ,и правда . подготовить тебе текстовые файлы и выгрузить все мои тесты миллионники ?
КодВладельца,КодНоменклатуры,Количество ?
108. Ish_2 1104 26.11.10 19:51 Сейчас в теме
(102) Пост(105) считать ошибочным. Достаточно выдать одну ветку
127. Ish_2 1104 28.11.10 19:12 Сейчас в теме
(102),(124) Господа Арчибальд и Сергей . Предлагаю каждому реализовать самостоятельно тест №1 1-10-10-10-10-10-10 со всеми уникальными узлами.
Всего должно получиться 6 уровней и 1 111 111 уникальных узлов.
Каждый самостоятельно исследует свою обработку на этом графе и сообщает здесь результаты ( если сочтет это возможным).

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

Результаты приводим для теплых(второй , третий) запусков обработки.
Если нужно потом рассмотрим и холодный запуск, а пока только теплые.
Два режима - файловый и клиент-серверный.

128. ildarovich 7850 28.11.10 19:54 Сейчас в теме
(127) Игорь! Вы, наверное, не обратили внимания, но в (112) уже приведены результаты этого теста (в строке №3). На этом графе я запускал и Вашу и свою обработку, на ноутбуке и на сервере. Есть и обработка для формирования этого теста (прилагается к моей статье - нужно поставить галочку "дерево"). Во только почему у Вас все тесты имеют одинаковый номер? Я дал этому тесту №3. Обозначил его 1<10<10<10<10<10<10, имея ввиду, что "<" обозначает ветвление. Граф этого вида называется "дерево". Честно говоря, потратил много времени на оптимизацию программы именно для этого случая. Непонятно: до сих пор Вам это было непонятно? :o
То есть Вы вообще не читали мои посты: про ФОКУС, про деревья - это все про данный тест. :cry: Я писал их, зная результаты работы своей программы на этом тесте. Только вот, называя условия этого теста боевыми, Вы лукавите! - могу сослаться на Ваше же высказывание.
129. Ish_2 1104 28.11.10 20:07 Сейчас в теме
(128) Я их не смотрел , потом что считал , что на данном этапе до выяснения работоспособности и правильности - это полная туфта.
И , вообще-то , оказался прав.
Ну что ж , Арчибальд пусть делает миллионный тест , а я завтра проверю у себя. И мы продолжим беседу по Вашей обработке.
130. hogik 443 28.11.10 20:11 Сейчас в теме
(128)
Сергей.
А добавьте, пожалуйста, в свою таблицу мои результаты. ;-)
Колонка "без запросов", строка "1<10<10<10<10<10<10" (нижняя).
Файловый - 35 сек. Клиент-серверный - 70 сек.
На самом деле - меньше.
Я замерял на загруженной другими задачами машине.
Ну, и на моей системе нет такого понятия - "файловый".
Т.к. БД всегда одинаковая.
Меняется только способ передачи "пакетов"
Грубо говоря - меняется только "протокол".
131. ildarovich 7850 28.11.10 22:08 Сейчас в теме
(130) Владимир! Я понял условия Игоря так, что в таблицах приводятся лично проверенные авторами таблицы результаты работы своих и чужих обработок разузлования на доступных авторам компьютерах. Ваш результат (35 сек) меня заинтересовал. Я его добавил в свою собственную таблицу, которую здесь выкладывать не буду. Сейчас перечитаю Ваши посты, чтобы понять суть подхода.
132. hogik 443 28.11.10 23:05 Сейчас в теме
(131)
Сергей.
Там нет никакого подхода.
Я с самого начала приводил тексты и тесты для "лобового" обхода, именно, дерева со схемой БД из темы "стартового" форума. Рекурсия - текстом из пяти строк. Но в рекурсивной функции не используется запросы. Т.е. это не мой подход, а подход СУБД имеющей не только запросный ЯМД.
По поводу внести мои замеры в свою таблицу - это шутка для Игоря по его методе сравнения результатов тестов... ;-)
133. Арчибальд 2706 29.11.10 08:26 Сейчас в теме
(127) Я уже оценивал объем вычислений в своем алгоритме как О(N * lgN), где N - число узлов графа. Переходя от 60 узлов к миллиону я ожидал увеличения времени в 40000 раз. Реально получил 830 сек, т.е. в 830/0.276 = 3000 раз. Это в 10 раз больше, чем запрос на 8-ке и в 7 раз - чем рекурсия на 8-ке.
135. Ish_2 1104 29.11.10 08:59 Сейчас в теме
(133)
Ты щелкнул за секунду миллионные регулярные графы с известной структурой с мизерным объемом информации.
Как только же дело дошло до главного реального испытания, по которому и определяется быстродействие реального
решения ты проиграл примерно в 8 раз. Время примерно 10(!!!) мин. Нужно продолжать ?
136. Арчибальд 2706 29.11.10 09:22 Сейчас в теме
(135) Все не совсем так. Я работаю с произвольными графами. На дереве с 11111 различными ветками (реальная сложность тепловоза) я имею 1.5 секунды. Такой результат вполне допустим даже в процедуре ПриЗаписи в модуле справочника номенклатурных наборов. Что касается нереальных задач - как твой алгоритм ведет себя на задаче 1*10*10*10*10*10*10*10*10*10*10 ? В 10 мин укладывается?
138. Ish_2 1104 29.11.10 10:13 Сейчас в теме
(136)
Критерий был определен заранее. Условия известны участникам. Перед тестированием ни у кого вопросов не возникало. И вот после получения результатов появились сомнения : а зачем это нужно ? а в тепловозе оказывается всего 11 111 узлов и т.д.

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

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

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

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


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



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

Мне нужно еще окончательно разобраться с Сергеем.
90. Арчибальд 2706 26.11.10 16:44 Сейчас в теме
(83) http://infostart.ru/public/78737/
Произвольные графы до 11, правда, уровня.
73. huse 26.11.10 11:57 Сейчас в теме
(0) Написал (рекурсия+кэш+запрос):

Тест1: 0 секунд
Тест2: 0 секунд
Тест3: обвал 1С-ки. Там зацикливание? Сейчас проверку сделаю.
75. Ish_2 1104 26.11.10 12:09 Сейчас в теме
(73) Да там сделана имитация зацикливания. Если в алгоритме нет контроля зацикливания , то он так и должен щелкать Тесты №1 и №2 за 0 сек.
Контроль зацикливания должен быть безусловным, т.е. любое зацикливание должно быть отловлено.
Чтобы можно было проверить правильность контроль зацикливания должен выдаваться по окончанию граф ошибок. Иначе как пользовтаель исправит эту ошибку в огромном графе ?
Если снять контроль зацикливания - задача становится тривиальной и неинтересной.
74. huse 26.11.10 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);
		 Возврат;
	КонецЕсли;	 
	НачДата = ТекущаяДата(); 
	Результат.Очистить();
	Ошибки.Строки.Очистить();
	Сообщить("**** Начато тестирование "+Номенклатура);
	Запрос = Новый Запрос;
	Кэш=Новый Соответствие;
	Результат=ПолучитьСостав(Запрос,Кэш,Номенклатура);
	Сообщить("Общее время выполнения "+ (ТекущаяДата()-НачДата));
КонецПроцедуры
Показать


Код особо не оптимизировал. Если бы работало тормозно - занялся бы, а так работает быстро ну и пофиг с ним.
ketr; ildarovich; +2 Ответить
76. Ish_2 1104 26.11.10 12:13 Сейчас в теме
(74) К посту на ИС можно прикрепить файл. Внизу окна сообщения надпись "прикрепить файл".
Прикрепи файл обработки - я его посмотрю.
78. huse 26.11.10 12:19 Сейчас в теме
(76) Прикрепил
Прикрепленные файлы:
ZaprosProtivRekursii.epf
79. Ish_2 1104 26.11.10 12:23 Сейчас в теме
(78) Отлично !
Я так понимаю , что ты создал универсальную обработку ? которая раскрутит любой граф , каким бы он не был с любым зацикливанием ? Например, если в тесте № 1 все 1 111 111 узлов уникальны ( не повторяются) , то также быстро всё будет ? У меня - да . А у тебя ?
80. huse 26.11.10 12:30 Сейчас в теме
(79) зацикливание я просто срезаю (игнорирую) - можно было бы орать, что ошибка или собирать ее куда то, но не интересно - допиши если надо.

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

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

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

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

А теперь сравни :
представленная в теме обработка ЗапросПротивРекурсии.epf на миллионном графе со структурой теста № 1 при любой уникальности (неповторяемости) узлов даст один и тот же результат. (увеличится время копирования Справочника СпецификацияНоменклатуры во врем.таблицу , увеличится время выгрузки миллиона выходных записей запроса на форму, но само разузлование будет длиться столько же +-10%.
77. huse 26.11.10 12:16 Сейчас в теме
(0) Как видим утверждение, что рекурсия зло - абсолютно несостоятельно.
113. ildarovich 7850 26.11.10 20:33 Сейчас в теме
(0) В целом по статье могу сказать следующее: Игорь показал ФОКУС. То есть в статье основное внимание уделено ФОКУСУ. На ней должно быть написано: "НЕ ПЫТАЙТЕСЬ ЭТО ПОВТОРЯТЬ!". А поскольку многие приняли статью за чистую монету - раскрою секрет этого ФОКУСА, если автор не хочет саморазоблачаться.
Приведенный в статье метод (не подход, а метод как одновременное разузлование и контроль циклов в одном запросе) имеет некоторый выигрыш перед другими только в одном случае: КОГДА ГРАФ ЯВЛЯЕТСЯ ДЕРЕВОМ. Стоит ветвям пересечься, метод проигрывает в сто и тысячи раз. Деревья - это гораздо более простой граф для алгоритмической обработки. В дереве у любого узла всегда есть уровень: для контроля зацикленности проверьте, чтобы в спецификации указывались только элементы следующего уровня и все! Распихивать древовидную спецификации одного изделия по объектам ИБ при этом даже нет смысла - на части спецификации нет внешних ссылок! Достаточно одной спецификации из миллиона элементов (с указанием для каждого порядка сборки - пути). А скрещивать УЖА (поиск циклов) и ЕЖА(разузлование) в одном запросе на практике? - будете иметь 200 секунд вместо 0,017!!!
Успехов в написании правильных запросов!
118. ildarovich 7850 27.11.10 12:47 Сейчас в теме
+ (113) Кстати, для спецификаций в виде дерева есть очень эффективные методы выборки подчиненных узлов - одним простым запросом к одной таблице узлов!
На узлах дерева всегда можно определить отношение порядка - например, порядок левостороннего обхода, присвоить этот "порядок" каждому узлу (в виде действительного числа, чтобы при вставке не менять "порядок" других узлов), и выбирать все подчиненные узлы как узлы, "порядок" которых помещается между "порядком" данного и следующего через более высокий уровень узла.
Спецификации в виде дерева можно записать в скобочной форме для интерпретации, использовать ЛИСП как в AutoCAD и так далее, но это уже совсем другая история!
119. Ish_2 1104 27.11.10 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. ildarovich 7850 27.11.10 21:04 Сейчас в теме
(119) Непонятно описано как сделаны зацикливания.
Ну и так как у Вас два одинаковых графа с одинаковыми названиями вершин, то и скриншот ситуацию не проясняет. Гадать не хочу -
перечислите строки, которые добавили и в какие спецификации. Номенклатуру желательно с кодами, раз у Вас она с одинаковыми названиями!

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

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

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

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

О деталях - потом.
124. ildarovich 7850 28.11.10 13:24 Сейчас в теме
(123) Упс! - Разобрался! Действительно, при определенном порядке строк (в базе! - не на форме!) при зацикливании возвращалось уже непустое разузлование из зацикленного узла! Моя вина! :(
Поправил несколько символов в строке 11 формы, обработку с исправлениями перевыложил. - Игорю спасибо!
Исправления:
Прикрепленные файлы:
134. Арчибальд 2706 29.11.10 08:53 Сейчас в теме
+133 На "теплом" старте результат - 630 сек.
137. Арчибальд 2706 29.11.10 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
Т.е. имеет место еще и предсказуемость.
149. Ish_2 1104 29.11.10 19:48 Сейчас в теме
Обработка Сергея во второй раз оказалась с неверным функционалом.
На рисунке отображено элементарное двойное зацикливание ,которое не определелила
Обработка Сергея.
Тестирование прекращено.
Прикрепленные файлы:
150. ildarovich 7850 29.11.10 21:36 Сейчас в теме
(149) Игорь! Я проверю.

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

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

Из сотни номенклатур не я - пользователи могут легко построить набор спецификаций,
которые Ваша программа не обсчитает за все время жизни Вселенной!

153. Ish_2 1104 29.11.10 22:01 Сейчас в теме
(150) Так Вы проверили ? Есть у Вас ошибка в определении зацикливания ?
156. ildarovich 7850 29.11.10 23:43 Сейчас в теме
151. ildarovich 7850 29.11.10 21:37 Сейчас в теме
(149) Но можно и заканчить, так как мне пришлось еще раз убедиться в том,
что аргументами можно победить незнание, а невежество так победить нельзя.

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

В общем, пользователь Вам судья! Но я бы предпочел, чтобы Вы признали, что нельзя считать
запрос, который работает миллионы лет, победившим рекурсию
. И честно, без уверток написали об этом в своей статье.
Ибо, как говорят мои коллеги - "отрицательный результат - тоже результат".
Этот поступок был бы достоин уважения.
А так - извольте...
neyaka; hogik; +2 Ответить
160. ildarovich 7850 30.11.10 12:28 Сейчас в теме
(149) Проверил. Следующее заключение НЕВЕРНО:
Обработка Сергея во второй раз оказалась с неверным функционалом.

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

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

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

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

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

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

Игорь! Прекращайте спорить с очевидным! - Примеров, показывающих слабость моего алгоритма нет! Кстати, потестировал я тут Вашу обработку (Тест№3): Нажимаю - жду - жду - жду. Самого-то не раздражает? А у меня: нажал "выполнить" - сразу ответ! - Красота!
163. Ish_2 1104 30.11.10 19:36 Сейчас в теме
(162)Продолжаем.Серия третья.
Прикрепленные файлы:
164. ildarovich 7850 01.12.10 12:46 Сейчас в теме
(163) По настоянию Игоря сделал вариант программы, повторяющий "странное" поведение его обработки в случае, когда в спецификации указана номенклатура с нулевым количеством. Обработка Игоря зачем-то разбирает и такую номенклатуру. С Игорем трудно спорить - любое понимание задачи, отличающееся от его собственного, он тут же объявляет "ошибкой" и "прекращает тестирование". Ну а поскольку в данном случае моя обработка только упростится на один оператор "если", я решил согласиться. Нужная для сравнения версия моей обработки называется "Разузлование_БП_1_6_ПустышкиТянем". Она приложена к данному посту.

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

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

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

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

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

Ответьте "Да" или "Нет" и продолжим обсуждение дальше.
171. ildarovich 7850 01.12.10 17:42 Сейчас в теме
(169) Устранять НЕ отказываюсь, но не ошибку, а несоответствие (опять!) выдачи Вашей и моей программы.
Это НЕ ошибка!!! Вот аргументы:
Есть два разных подхода: Ваш и мой.

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

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

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

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

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


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

Я утверждаю , что любой другой подход "есть дорога в Ад", то есть (163).
Отсюда вытекают важнейшие следствия.
174. Ish_2 1104 01.12.10 19:26 Сейчас в теме
(171)
Теперь конкретно Для Сергея.
(ничего не убирая! - не жульничайте!)...
Чтобы ее ( увидеть, Вам придется вывести не 100, а 100 001 ошибочных цепочек.


Кхе-кхе...
У меня действительно стоит выдавать только ПЕРВЫЕ 100 ошибок.
Заметьте , у меня содержится во временной таблице ПОЛНЫЙ граф ошибок , а выдается только 100.
Сколько хочу столько и выдам.
Я посчитал ,что 100 первых вполне достаточно для начала работы пользователя над ошибками.
Сделано это в демонстрационных целях и не более того .
Тестируя программу , я задал 1 000 000 ошибок и не дождался выполнения запроса по ошибкам (т.е. построения графа ошибок). С другой стороны , ничто не мешает БЫСТРО выдавать параллельно общее количество ошибок для информирования пользователя.
175. ildarovich 7850 01.12.10 22:46 Сейчас в теме
(169)
+(171) Завтра закончу, так как теперь нужно убрать дублирование функционала и заново протестировать...
176. Ish_2 1104 02.12.10 03:06 Сейчас в теме
(175) Понял. Только не спешите.
Это уже совсем другая обработка. И другая история.
А эту тему мы завершим.Ок.
177. ildarovich 7850 02.12.10 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. Ish_2 1104 02.12.10 12:15 Сейчас в теме
(177) Обсуждение закончено. После драки кулаками не машут.
Ваша обработка тестировалась честно с Вашего согласия и по известным правилам.
У Вас было достаточно времени в МОЕЙ ТЕМЕ привести ВСЕ СВОИ аргументы в пользу СВОЕЙ обработки.
Вы собрались писать НОВУЮ обработку (175). Обсуждать её в своей теме я не намерен.
179. ildarovich 7850 02.12.10 12:48 Сейчас в теме
(178) Игорь! Вы не выполнили условия нашего спора. Кроме мелких придирок к моей обработке не привели никаких аргументов в защиту своей позиции (прежде всего своих результатов сравнительного тестирование времени разузлования двух обработок на разных тестах). Как еще Вас стыдить, я не знаю. Желаю просто не отмахиваться от новых знаний. Если Вы воспользуетесь моими советами - сделаете свою обработку лучше. Ведь если бы Вы внимательно прочитали мою статью и приняли на свой счет, вы бы не сделали примитивной ошибки - не "попали на миллион". Независимо от результатов, решать задачу мне было интересно.

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

ВЫВОДЫ СТАТЬИ О ПРЕИМУЩЕСТВАХ ПРИВЕДЕННОГО ЗАПРОСА ПРОТИВ РЕКУРСИИ - НАГЛАЯ И СОЗНАТЕЛЬНАЯ ЛОЖЬ!!!
Арчибальд; huse; hogik; +3 Ответить
180. Ish_2 1104 02.12.10 18:32 Сейчас в теме
(179) Спокойно. Вы можете создать новую тему и там провести сравнительный анализ двух обработок и сказать , что Вы думаете о моей обработке и в чем преимущество Вашей. Подготовьтесь получше. Если в Вашей обработке не будет много ошибок , если статья покажется мне интересной - Я приду.
Попробуйте. Докажите свою правоту.
181. huse 03.12.10 00:51 Сейчас в теме
(179) может и не сознательная ))))
170. Ish_2 1104 01.12.10 17:26 Сейчас в теме
(168) Всё ! Проехали.
Господа , Сергей и Арчибальд, я был бы вам очень благодарен если бы вы
со всей пристрастностью объявили мне о недостатках моей обработки.
166. Арчибальд 2706 01.12.10 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. Ish_2 1104 01.12.10 16:16 Сейчас в теме
(166) Спасатель ? Все разговоры - от лукавого.

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

Жду ответа Сергея , чтобы задать следующий вопрос.
154. hogik 443 29.11.10 22:50 Сейчас в теме
Сергей & Игорь.
Позвольте и мне сказать.
Надеюсь, что вы оба прочтете.
Вы решаете разные задачи!
Игорь делает уклон на сферу СУБД, а Сергей (и Александр) на численные методы.
Игорю, думаю, надо было с самого начала определить задачу так, чтобы и мысли не было рассматривать "графины". Печально, но в теме СУБД очень мало мест где можно применять "математику". В задаче от Игоря её нет вообще.
Игорь сам-себя запутал и других людей запутал. О мотивах этой "запутки" я сказал выше по теме. У Игоря и в обсуждении на форуме, и в данной статье идет "полная путаница" терминов и задач.
Пример "разузлования" (условно!!!).
Колесо автомобиля.
Шина (1 шт.).
Обод (1 шт..
Камера (1 шт.).
Грузик (от 0 до 10 штук).
Но описано само изделие - его состав. А какая будет шина ничего не сказано. На этой позиции могут быть разная шина - производитель, сезонность, вес, цена, поставщик и т.д. Т.е. это (в нашем примере) жестко узел с степенью - четыре. Т.е. описан "каркас" изделия. И это дерево, естественно - без циклов. Часто, заранее, с подсчитанным количеством "входимости" позиций в "каркас". А количество изделий подсчитывается простым запросами с Sum()-ами. ;-)
Для работы с таким деревом требуется не выборка множества узлов, а получение одного узла "соотнесенного" с его родителем и детьми. Это делается не запросом и не "закачкой" в память информации - в СУБД это возможно, но это не есть корректные способы взаимодействия приложения с БД. Почему? Мне казалось, что я об этом сказал многократно в форуме до появления данной стать. Оказывается - нет :-(
А если в задаче строго дерево, то единственный тест (по классификации от Сергея) - под номером три. Всё остальное не имеет отношение к дереву. Т.е. это частные задачи с элементами "фокусов" не в сфере СУБД.
Сравните свои скорости на третьем тесте. Для деревьев с разными степенями и уровнями. И разойдитесь. В сфере СУБД, всё остальное не имеет смысла...
155. Ish_2 1104 29.11.10 22:54 Сейчас в теме
(154) Пока не мешайте. Мы уж как-нибудь закончим с Сергеем сами.
157. Ish_2 1104 29.11.10 23:58 Сейчас в теме
Что ж, бывает. Время позднее.
Пора заканчивать. Всем спасибо !
158. huse 30.11.10 01:33 Сейчас в теме
(0) ничего писать я больше не буду. ты самый умный - вот и пиши. я верю ты сможешь обосновать клиенту почему так медленно работает.
159. Ish_2 1104 30.11.10 09:34 Сейчас в теме
И с утра подведем короткое резюме.
Я благодарю авторов Huse,Арчибальда, Сергея , не только обсуждавших задачу "разузлования" , но и представившими свои разработки .
Для меня была важна сама форма эксперимента : открыто обсудить и протестировать в теме альтернативные разработки нескольких авторов.
Насколько это понравилось публике и самим авторам мне судить трудно. Но я старался, чтобы это было интересно.

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

Эти соображения и легли в основу обработки ЗапросПротивРекурсии.epf и обеспечили как её недостатки, так и достоинства.
182. huse 03.12.10 01:00 Сейчас в теме
А вообще чем дольше работает программа, тем у Заказчика больше уверенности, что программист написал сложную программу. Тут конечно автор темы всех победил. Особенно если он _честно_ попробует объяснить Заказчику как именно производится разузлование - то Заказчик будет восхищен эрудицей и величиной мозга Автора, ведь ни один Заказчик так до конца и не поймет что же там происходит на самом деле.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример использования Рекурсии как вычислительного приема приводить не буду. Надеюсь , ненужно.
190. Арчибальд 2706 08.12.10 10:30 Сейчас в теме
(188)
Реккурентность - это рекурсивное определение функции. Они широко распространены в математике.

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

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


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

Сдавайся, короче.
187. tango 506 07.12.10 18:07 Сейчас в теме
Игорь, ты рекурсивно строишь тело запроса, нихт ферштеен?
189. tango 506 08.12.10 10:28 Сейчас в теме
Есть, просто ты его довольно хитро (это комплимент) спрятал в запросы. Рекурсия - у тебя в запросах, и цикл ты прекращаешь, когда достигаешь конца именно рекурсии. Вот сейчас найду старенькую фишку - для упп, в предположении, что нет в спецификах нет кольцевых ссылок, и что специфики - сборочные (в тех условиях это было хорошее предположение). Там у меня в (явной) рекурсии на каждом уровне дерева создается запрос, выполняется, и, фактически, проверяется то же услолвие, что и у тебя. Ты вошел в рекурсию, создав первую таблицу, и "спрятал" ее, тесно переплетя с запросами. У меня - рекурсия явная, запросы - сами по себе. Но разница-то в чем, кроме того. что у тебя было время на 1сные изыски?
Прикрепленные файлы:
КомплектацияПолная.epf
192. Арчибальд 2706 08.12.10 10:33 Сейчас в теме
194. Ish_2 1104 08.12.10 15:26 Сейчас в теме
(192),(193) Мелькнула предательская мыслишка :
Арчибальд и Танго - хорошие люди, ерунду не скажут.
Может и ,правда, сдасться ?

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

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


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

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

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


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