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

Публикация № 78285

Разработка - Практика программирования

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

110

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

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

Специальные предложения

Комментарии
Избранное Подписка Сортировка: Древо
1. ILM 237 23.11.10 14:51 Сейчас в теме
Однозначно интересный подход, сейчас попробую его на реальных данных.
2. Арчибальд 2708 23.11.10 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/
Где-то тААк вООт...
user774630; hogik; anig99; cool.clo; +4 Ответить
7. Ish_2 1038 23.11.10 16:57 Сейчас в теме
(2) Твой код я посмотрю. А пока так:

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

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

Я ответил на него как мог.
10. Арчибальд 2708 23.11.10 17:08 Сейчас в теме
(7) Конечно же речь не о первенстве/авторстве. У себя я указываю, что алгоритм стандартный. Соответственно, у тебя тоже. А вот сколько таки секунд на тест #1 получилось? Иначе говоря, насколько создание временной таблицы и обход ее запросом быстрее/медленнее создания в памяти массива и обьхода его в цикле?
11. Ish_2 1038 23.11.10 17:34 Сейчас в теме
(10) Робею отвечать . Вроде бы старался в теме отобразить все параметры теста №1.
Для тебя лично :

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

P.S. На всякий случай, просмотрел тему (у меня IE8) - там четко написано и выделено Жирным щрифтом Тест № 1 "Десять", далее идет таблица с результатами тестирования , в первой строке таблицы две колонки :
файловый вариант --------------------- 25 -60 сек
26. Ish_2 1038 24.11.10 10:45 Сейчас в теме
(10) Ты уж уважь... Напиши сколько длится в твоей реализации Тест №1 на 77 на твоей машине, и если есть у тебя демо-конфигурация БП 1.6(2.0) , то сколько в ней длится тест №1 для обработки "ЗапросПротивРекурсии.epf".
Т.е. предлагаю обмениваться числовыми характеристиками.
Тогда всё упростится и истина , надеюсь, станет ближе.
27. Арчибальд 2708 24.11.10 12:15 Сейчас в теме
(26) ОК. Займусь. Сделаю регулярное дерево и попробую. Чуть позже.
28. Ish_2 1038 24.11.10 12:32 Сейчас в теме
(27) Спасибо. Но на всякий случай... А то тут у нас Сергеем как-то вышло недоразумение.
Обработка твоя должна быть универсальной , т.е. не "заточкой" для теста №1 с известной регулярной структурой, а эффективной для любого графа. Это значит , и то что алгоритм твой при начале работы - ничего не знает ( не обладает априорной информацией) о характере графа.
Извиняюсь , если обидел таким разжёвыванием.
53. Арчибальд 2708 25.11.10 17:32 Сейчас в теме
(28) Весь день отвлекали враги. Вот только теперь добрался до результатов.
Сразу оговорюсь: Таблицу, описывающую граф, я создаю не из справочника, а непосредственно. На тесте №1 замерить результат я не смог: он менее секунды. Тогда я к листьям из этого теста прицепил по 10 дуг со случайно выбранными концами (т.е. разузловываем не просто дерево, а с возможными циклами с 10 миллионами возможных путей длины 8). В этом случае разузлование длится около секунды, но заведомо меньше 2-х.
Работал локально, база ДБФ-ная. 1С не перезапускал. Одна хитрость: кроме ТЗ_Дуги я использовал ТЗ_Узлы с колонками "Отец" и "СписокДетей", т.е. описание графа избыточно, примерно как в первоначальном тексте http://infostart.ru/public/78032/
Прекращайте писать запросы!
Прикрепленные файлы:
54. Ish_2 1038 25.11.10 17:44 Сейчас в теме
(53) Честно сказать , ничего не понял.
Я полагал , что постановка аналогична той что в текущей теме . Дана таблица значений:
Владелец, Номенклатура, Количество - задается начальный корень "владелец" и всё - поехали !

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

Ты уж тогда опиши , что у тебя задано и что нужно найти.
Или представь обработку .ert
Для меня то , что ты написал полный ребус.
58. Арчибальд 2708 25.11.10 18:19 Сейчас в теме
(54) Дана ТаблицаЗначений Отец, Сын, Количество.
Есть конкретный отец.
По ней я делаю еще одну ТаблицуЗначений Отец, Дети
Дети - это СписокЗначений Сын,Строка(Количество) - мне в семерке неудобно искать всех сыновей каждый раз, я уж один раз ее (таблицу дуг) перелистаю.
Потом разузловываю. Все за 1 секунду.
Прикрепленные файлы:
Миллион.ert
59. Ish_2 1038 25.11.10 18:29 Сейчас в теме
61. hogik 429 25.11.10 19:49 Сейчас в теме
(58)
Александр, дополнение к (60) о "Прекращайте писать запросы!" из (53).
Методы "НайтиПоКоду(), НайтиЭлемент() и т.д" - в платформе реализуется запросами.
66. Ish_2 1038 26.11.10 08:08 Сейчас в теме
(58) Эффектное начало "Прекращайте писать запросы !" - возбудило интерес.
Я даже хлопнул в ладоши - " Это по-нашему ! Ай, да Арчибальд !"
Ты щелкнул "миллионный граф" , как и Сергей, - за секунду и даже не насторожился : этого сделать еще никому и нигде не удалось .

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

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

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

Вот и весь секрет : в миллион раз упростив задачу - ты решил её за секунду.



68. Арчибальд 2708 26.11.10 10:17 Сейчас в теме
(66) На входе алгоритма я имею Справочник.Наборы с реквизитами Отец, Сын (элементы справочника Номенклатурные позиции) и Количество. Это безызбыточное определение графа, бесспорно. Ну и что?
Для графов существует множество задач, и для решения их могут и должны использоваться разные представления. Для разузлования я выбрал глТЗ_Узлы, формирую эту единственную таблицу простейшим запросом (см. рис.) и при разузловании пользуюсь только ей. Никаких избыточных структур. Решал бы я другую задачу - возможно, я бы использовал еще какое-нибудь представление.
Ну, а дополнительное условие - не преобразовывать структуру - напоминает известную историю, когда у пациента удаляли гланды, а тот по условию должен был держать рот закрытым.
Прикрепленные файлы:
71. Ish_2 1038 26.11.10 11:46 Сейчас в теме
(68) Начинаем разбираться :

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

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

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

Серьезное ли это нарушение ? - Отвечаю: Да .
Достаточное ли основание , чтобы прекратить дальнейшее рассмотрение кода ? - Отвечаю : Да .
Вывод : автор обработки решает какую-то свою задачу , отличную от той, которая задана в теме.

12. Ish_2 1038 23.11.10 17:59 Сейчас в теме
(2),(3) Хм... Постарался внимательно перечитать еще раз .
Судя по всему , мы говорим каждый о чем - то своём.
В каждом предложении комментарии (2) , уверен , непонимание настолько зашкаливает , что я даже не знаю с какого места начинать разговор.
3. Арчибальд 2708 23.11.10 15:56 Сейчас в теме
6-уровневый 10-арный граф , имеющий 1 000 000 различных ветвей и при обходе такого графа таблица ВремТаблица6 на выходе цикла алгоритма содержит 1 000 000 записей.
Позволю себе не согласиться. По этой логике 2-уровневый 3-арный граф должен дать 9 записей. У меня гораздо больше получается... А циклов нет, прошу заметить.
Прикрепленные файлы:
6. ildarovich 6734 23.11.10 16:55 Сейчас в теме
(3) Там, видимо, была оговорка. Имелся в виду не граф, а дерево. Корень дерева - нулевой уровень.
8. Арчибальд 2708 23.11.10 17:01 Сейчас в теме
(6) Ну нет, автор постоянно в обсуждениях подчеркивал произвольность графа. Если бы речи шла о дереве - можно было бы организовать обход "вглубь" и помечать пройденные дуги. Сложность тогда почти пропорциональна количеству узлов/дуг.
4. ildarovich 6734 23.11.10 16:40 Сейчас в теме
(0) Игорь! Именно так я и представлял себе Ваше решение (по Вашим предварительным словам). Оставляйте "СГРУППИРОВАТЬ ПО"! - Именно это не дает экпоненциально расти времени работы Вашего алгоритма. А с контролем зацикливания лучше придумать что-либо другое! - Нужно просто оставлять во временной таблице пройденные узлы не в виде нарастающей строки пути, а как-либо по-другому...
5. Арчибальд 2708 23.11.10 16:49 Сейчас в теме
(4) Не выйдет. Если мы не помним весь путь, то цикла не обнаружим.
Кстати, время там не по экспоненте растет, а еще круче. Факториально.
9. ildarovich 6734 23.11.10 17:07 Сейчас в теме
(5) Я имел ввиду помнить не путь, а пройденные вершины - порядок ведь не важен, но эту мысль еще нужно обдумать.
По поводу роста времени я имел ввиду не рост в зависимости от числа уровней, обусловленной природой задачи, а дополнительный рост времени, обусловленный тем, что мы не сворачиваем таблицу после каждой итерации... хотя, Вы, наверное, правы.
13. ildarovich 6734 23.11.10 18:12 Сейчас в теме
(4) (5) Поторопился с выводами. Действительно, пока не придумывается как совместить контроль зацикливания и "сгруппировать по" в предложенном запросе.
Но! - Это легко контролировать при записи каждой спецификации! Так что такой контроль нужно просто перенести в другой модуль - вот такое решение!
14. Ish_2 1038 23.11.10 18:30 Сейчас в теме
(13) В статье я неслучайно отказался от рассмотрения этого вопроса:

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

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

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

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

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

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

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

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

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

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

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

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

Если ДА, то первым тестом от меня будет граф 1-10-10-10-10-10-10 со всеми уникальными значениями. Ведь у нас с Вами не заточки под тесты №1 и №2, а универсальные обработки для работы с графом. А для универсальных обработок
первое свойство - работоспособность и устойчивость. Вначале его проверим , а потом уж будем соревновать в скорости.
Договорились ?
21. ildarovich 6734 24.11.10 09:40 Сейчас в теме
(20) Договорились.
1. БП 1.6.
2. Мне потребуется денек (отвлекают тут меня) на тщательную отладку (на всякий случай).
3. Согласен.
4. Первый тест принимается.
5. Еще хотелось бы электровоз найти. Хотя бы без наименований в виде списка (Код-Код-Количество).
5. Приз - "плюсик" к статье от проигравшего победителю.
6. Разумные сроки на ответы (не часы).
22. Ish_2 1038 24.11.10 09:48 Сейчас в теме
(21) Отлично.Принимается.
Какой вариант выберем в качестве основного ?
Файловый или клиент-серверный ?
(обычно сравнения и тесты делаются для клиент-серверного варианта , как более устойчивого и предсказуемого на больших объёмах, но - дело Ваше)
23. ildarovich 6734 24.11.10 10:15 Сейчас в теме
(22) Файловый, если результаты не будут очевидно разными. Тогда решим заново.
(просто у меня трехзвенка только на работе)
25. Ish_2 1038 24.11.10 10:27 Сейчас в теме
(23) Отлично.
Теперь об удобстве сравнения и анализа. Сравниваемые обработки должны обладать таким развитым интефейсом,
чтобы пользователь мог быстро интерактивно проверить созданный граф, внести специальные ошибки и посмотреть результат. Не буду же я гадать правильно ли создан огромный граф рассматриваемой обработкой или нет ?
Т.е. я это должен сделать интерактивно как пользователь , а не ковыряя чужой код, и не ломая голову над созданным графом в виде таблицы.
Иначе пустые споры : "правильно-неправильно" затянутся , как у меня с Владимиром.
Предлагаю (но не настаиваю) скачать обработку ЗапросПротивРекурсии.epf и посмотреть как в ней решены вопросы контроля и какие созданы средства для быстрой проверки.
Еще раз - мы рассматриваем вопрос как создать удобные и быстрые средства контроля и анализ ошибок , а не сам алгоритм (он у каждого свой). Грубо говоря - договоримся и создадим оснастку
89. ildarovich 6734 26.11.10 16:28 Сейчас в теме
(25) Игорь! Я провел эксперименты. Ваши выводы и результаты по тесту №3 не подтверждаются. Вашу обработку брал из Вашей статьи, свою - из своей "Как не попасть на миллион". Заполнялку брал свою(приложена к моей статье).В результате на тесте с 1 111 111 позициями номенклатуры Ваша обработка работала 145 секунд, моя (рекурсия в оперативной памяти) - 115! Могу объяснить только тем, что Вы заполняли спецификации "слоями", так что две последовательно выбираемые спецификации лежат рядом или (чем еще?).
Прикрепленные файлы:
91. ildarovich 6734 26.11.10 16:50 Сейчас в теме
(89) В итоговой таблице (описании тестовых структур - не в результатах!) есть незначительные неточности. Вечером исправлю и дополню таблицу.
31. Ish_2 1038 24.11.10 18:17 Сейчас в теме
32. hogik 429 24.11.10 21:18 Сейчас в теме
(31)
Игорь.
Спасибо за замеры.
Однако в этих замерах "SQL сервер не перезапускался"(с).
Т.е. такие замеры меня не интересуют.
(0)
По публикации.
Автор, в очередной, раз доказал (показал) что один запрос лучше, чем много. ;-)
Для этого была выбрана одна из самых неудобных задач в теме реляционных СУБД - обход дерева. Добавлено несколько дополнительных условий, усложняющих решение задачи методом простого обхода дерева - проверка цикличности, подсчет "изделий". Использовались термины не относящиеся к сути задачи - "рекурсия", "разузлование", "спецификация". При сравнении различных методов (не алгоритмов!) обработки информации применялись подтасовки фактов. Например: замеры от разных людей в разных средах, самостоятельное "тестирование" рекурсии...
И сделан очевидный вывод, что лучше когда вся "тяжесть вычислений (99.9%) ложится на сервер БД"(с).
Автор не утруждается анализом "процессов" происходящих на сервере. Типа, "с глаз долой из сердца - вон". На мои просьбы провести "подсчет" количества операций ввода/вывода на сервере - не отвечает. Вопрос кэширования на стороне сервер автора не интересует. Допустим, мы выделили каждому пользователю свой сервер. Или поставили один - ооо-чень мощный компьютер (сервер). Но выделить каждому пользователю свою базу данных у нас, не очень, получится. Т.е. задача сервера - не только обеспечивать "мощей" пользователей, а еще и обеспечивать доступ к общим данным. И это одна из важнейших задач сервера БД. В разных СУБД (и их ЯМД) используются различны инструменты для обеспечения пользователям "одновременный" доступ к информации. Кроме самих инструментов СУБД используются еще и "смысловые" приемы при разработке приложений - специфичная схема БД, разбиение задачи на "отчет" (только чтение) и обновление, интерактивный или пакетный режим и т.д.
К чему, я это всё.
А к тому, что автору имеет смысл определиться - он "обход дерева" делает для отчета (выходной формы) или еще для чего. Судя по выбранным инструментам (запрос) - для отчета. Отчета для подсчета количества "изделий в спецификации". Посчитали - напечатали. А если в момент подсчета другой пользователь изменил "дерево"? Нельзя такое допускать в выбранном автором алгоритме раскручивания дерева (или можно?). Решения два - блокировать всю исходную таблицу, ведь "мы ничего не знаем о дереве"(с) или создавать полную копию исходной таблицы, блокируя ей на момент копирования. Первое - понятно. Т.к. 20 секунд блокировки при множестве желающих работать (не только отчетами) с "деревом" - многовато... Второе - лучше. Благо таблица маленькая и копируется только средствами центральной машины. Но тогда это "чистый отчет". Т.е. никакого воздействия данными отчета на исходную таблицы БД - невозможно. Но тогда почему её не передать клиенту, и не сделать обработку на машине пользователя любым, красивым, методом. Передача - один запрос, по сети за две секунды (для таблицы в 1111111 записей), а без сети - 1 секунда.
Но в реальной жизни с иерархическими структурами НАШИХ задач работает множество пользователей одновременно (интерактивно). Одни смотрят, другие обновляют. И СУБД должна обеспечивать всех пользователей достоверной информацией. Способы такого обеспечения известны - блокировки. Но это другая тема. ;-) В этом важно только одно - быстрое чтение/обновление минимального количества узлов дерева за одну "транзакцию". Т.е. в запросной технологии - запрос на узел дерева (грубо говоря). Без запросной технологии "чтение/обновление" узла без запроса. ;-) Но т.к. алгоритм обработки гораздо сложней чем подсчет изделий, то осмелюсь предположить, что на обработку одного узла придется выполнять либо множество запросов, либо осуществлять его обработку на стороне клиента.
Т.е. подводя итог моему, сумбурному, изложению предлагаю тему "Мы пишем запросы" переименовать в "Мы пишем отчеты запросами". А для отчетов самое оно - использовать запросы. Нужно только изменить схему базы данных под этот инструмент. Что в продуктах 1С и сделано. И никаких задач типа "обход дерева", "нарастающие итоги" и т.д. Для НАС таких задач просто не существует... ;-)
37. Ish_2 1038 25.11.10 05:30 Сейчас в теме
(32)
- Почём твоя скотина , ковбой ?
- Что Вы знаете о скотине , мистер ... В далекие времена , когда воды Миссисипи были полны и скотина бегала сама по себе...
- Почём твоя скотина , ковбой ?

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

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

Что же до минуса ... Никаких обид.
33. hogik 429 24.11.10 22:48 Сейчас в теме
(31)
Про Ваши замеры - "специально для меня".
По поводу строчки "вылетело SQL".
На "моей" СУБД стартовый объем занимаемой памяти - 254 мегабайт.
В процессе обхода дерева в миллиард вершин дошло до 320 мегабайт.
Рабочих таблиц не использую... ;-)
24. m_001 24.11.10 10:16 Сейчас в теме
Надеюсь автор не будет возражать ;) , если добавлю версию для УПП 1.3.5.1. на платформе 8.2. Просто мы давно перешли на УПП и работаем только с ним.
Так что посмотрите обработку для УПП в прикрепленном файле.
Разузлование проходит быстро, ошибки зацикливания тоже ищутся.
Прикрепленные файлы:
ЗапросПротивРекурсии_v82.epf
29. Ish_2 1038 24.11.10 14:29 Сейчас в теме
(24) Пропустил Ваш пост. Сообщение мне на e-mail чего -то не пришло. Виноват. Посмотрю.
30. Ish_2 1038 24.11.10 14:42 Сейчас в теме
(24) УПП у меня - нет . Но насколько я слышал , там должен быть Регистр где содержится ОсновнаяСпецификацияНоменклатуры. Т.е. спецификаций у номенклатуры может быть несколько. В моей же обработке они все сольются в одну, если их несколько. Это нездорово.
Поэтому , строго говоря , в код обработки должны быть внесены изменения :
во временную таблицу Спецификации (процедура КнопкаВыполнитьНажатие()) должны копироваться не все спецификации , а только те, для которых установлено в регистре что это основная спецификация . Примерно так .
Если сможете сделайте - я выставлю в теме это как Ваш файл .

И еще одна просьба : приведите , пожалуйста пример насколько быстро разузловывается "самая большая Ваша номенклатура".
34. WKBAPKA 211 25.11.10 00:15 Сейчас в теме
ребята, я уже попкорн весь съел... это у вас из серии: что первым было, курица или яицо? ;)
Capitullo; +1 Ответить
70. prizrak58 26.11.10 11:26 Сейчас в теме
под конфигурации Комплексная автоматизация не работает, выдает ошибку:
{Форма.Форма(34)}: Ошибка при вызове метода контекста (Выполнить): {(2, 14)}: Поле не найдено "Спец.Ссылка.Владелец"
Спец.Ссылка.<<?>>Владелец КАК Владелец,
Запрос.Выполнить();
по причине:
{(2, 14)}: Поле не найдено "Спец.Ссылка.Владелец"
Спец.Ссылка.<<?>>Владелец КАК Владелец,
35. WKBAPKA 211 25.11.10 00:26 Сейчас в теме
на самом деле, всегда эффективнее будет работа с памятью... запросы от платформы к платформе могут иметь разную производительность, все зависит от реализации... работа же с памятью практически всегда будет эффективнее ... объем информации в данном случае не имеет значение, т.к. на себя эту задачу берет операционная система... ко всему прочему, как описывается в некоторых учебниках по запросам к 1С, когда запросы преобразовываются в TSQL могут быть выбраны разные планы, в этом случае запрос может выполняться часами... имхо, то что я читал... отсюда могу сделать вывод, что решать данную задачу запросами будет не эффективно, с точки зрения скорости...
36. hogik 429 25.11.10 00:56 Сейчас в теме
(35)
"работа же с памятью практически всегда будет эффективнее ... объем информации в данном случае не имеет значение, т.к. на себя эту задачу берет операционная система..."(с)
Ярослав.
Поиск волшебных палочек продолжается? ;-)
У Игоря - "запросы". У Вас - "операционная система".
В моём сообщении #33 не опечатка в части количества записей.
Т.к. у меня формат таблицы от "1С 7.7", то это около 77 гигабайт.
В "1С 8.х", думаю, размер записи больше будет.
Читайте таблицу в память, считайте время закачки, покупайте новый "сервер"...
40. WKBAPKA 211 25.11.10 09:11 Сейчас в теме
2(36): причем тут волшебная палочка ? я имел ввиду, что все что касается работы с памятью прикладным программистам не доступно, что за это отвечает операционная система и что код будет работать быстрее, если это будет работа с массивами данных в памяти, а не запросы...
41. Ish_2 1038 25.11.10 09:38 Сейчас в теме
(40)
"код будет работать быстрее, если это будет работа с массивами данных в памяти, а не запросы..."


Истин общих - нет.
Если рассматривать вопрос в контексте данной темы , то в статье как раз и показано что запрос эффективнее, чем использование рекурсии в оперативной памяти. И намного.
См. Рис.9 в теме.
60. hogik 429 25.11.10 19:17 Сейчас в теме
(40)
Ярослав.
1) "все что касается работы с памятью прикладным программистам не доступно"(с)
Доступно.
2) "за это отвечает операционная система"(с)
Допустим. Но размер используемой памяти "заказывает приложение". Существуют ограничения количественные и "качественные" (одновременный доступ к данным с разных ЭВМ). И для уменьшения потребного размера необходимо в памяти иметь только нужную и возможную информацию. Этим, в частности, и занимается СУБД. А если в одной таблице, например, лежат "деревья" для разных "тепловозов" и требуется обработать конкретный "тепловоз" - надо отобрать нужные данные из таблицы БД. В схеме БД в постановке от Игоря - отобрать нужные данные равносильно решить конечную задачу.
3) "за это отвечает операционная система и что код будет работать быстрее"(с)
Для обсуждаемой темы, нет никакой связи в ответственности ОС-а и скорости кода.
4) "если это будет работа с массивами данных в памяти, а не запросы..."(с)
Безусловно. Остаётся НУЖНЫЕ данные рационально положить в память.
(53)
"Прекращайте писать запросы!"(с)
Александр.
А если нету никаких других средств обработки данных в БД?
И даже в НАШЕЙ "1С 7.7" SQL-ной версии всё делается запросами.
Для примера (примера !!!).
Метод ВыбратьЭлементы().
В DBF-ной версии ничего не выбирается. Это только установка на первую запись множества. А в SQL-ной версии это передача от сервера клиенту всего множества элементов справочника. А если они все не нужны приложению? А если приложение вызывает этот метод многократно?
42. huse 25.11.10 09:48 Сейчас в теме
(0) Если сделать рекурсию с кэшем - это будет самое быстрое разузлование. Так как задача разузловки для каждого вида узла будет решаться только один раз.

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

ЗЗЫ. Если говорить о задаче разузловки - я бы использовал рекурсию, запросы и кэш (либо ввиде временной таблицы, либо ввиде соответствия).
43. Ish_2 1038 25.11.10 10:08 Сейчас в теме
(42)
Если сделать рекурсию с кэшем - это будет самое быстрое разузлование.

Как гипотеза - принимается.
Добиться каких-то практических результатов от специалистов по TSQL не удалось.
Сам испытываю от такого подхода предельный скепсис, но буду рад , если появятся какие-то решения уже скорее не на ИС.
44. huse 25.11.10 10:18 Сейчас в теме
(43) Я решал подобную задачу на 7.7 - деталей было около 3-х тысяч. Глубина примерно 5-6 узлов (диван, модуль, каркас, элемент каркаса, деталь, технологическое объединение деталей, материал). Переход от плана производства диванов до потребности в сырье делался около 5-10 минут (за давностью уже не помню). В качестве кэша использовал СписокЗначений.
46. Ish_2 1038 25.11.10 10:28 Сейчас в теме
(44) Что-то подобное делал и я , лет 8-9 назад. Глубина такая же 5-6.
Но от рекурсии отказался из-за тормозов и не поленился написать вложенный 6 раз цикл.
Так было быстрее. Правда , потом оказалось , что одно изделие имеет уровень 7...

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

С другой стороны , конечно , это всего лишь эксперимент одного автора на ИС . И не более того.
В свободное время, смеха ради попробуйте реализовать Тест №1 и запустите свою обработку графа.
Может быть , Вы меня опровергнете ?
Опубликую в теме сразу : так мол и так, Huse доказал... и опроверг все построения автора.
Обещаю.
49. huse 25.11.10 12:53 Сейчас в теме
(48) а твоя обработка требует разузлование.dt?
50. Ish_2 1038 25.11.10 12:58 Сейчас в теме
(49) Виноват , не понял. Что такое разузлование.dt ?
Моя обработка запускается в любой конфигурации БП1.6(2.0) для платформы 1с8.
Ничего не требует. По кнопке запускается тестовое заполнение миллионного теста и "кнопка выполнить". Всё. См. Рис.9 темы.
56. huse 25.11.10 17:50 Сейчас в теме
(50) понял - вечерком разверну - сделаю свой вариант в твоей обработке.
51. cool.clo 25.11.10 13:18 Сейчас в теме
(44) Абсолютно похожим образом решал немного другую задачу - необходимо было нескольких сайтах свести номенклатуру, отсортировать по всем вложенным категориям(их где-то 6-7) и внести для всех общую артикулизацию. Также делал кэш (в смысле тоже СписокЗначений). Действительно с кэшем было веселее(когда я его сделал сам поначалу удивился как быстро). НО! Номенклатуры всего-то было тысяч 20..., поэтому я думаю рекурсия здесь не самый оптимальный метод. Согласен с Ish_2. В 1С я думаю этот метод просто не самый быстрый. (имею ввиду 8, поскольку с 7.7 не имел дела, вообще раньше делал небольшие учетные программки на Delphi (+SQL). 1С в функционале просто беспощадно выигрывает, но вот скорость надо сказать - вопрос кто выигрывает спорный, несмотря на то, что программы совершенно разные , да и программист я не ахти. )
45. SatanClaws 127 25.11.10 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. Ish_2 1038 26.11.10 08:51 Сейчас в теме
(45) А можно поподробнее ? Как ставилась задача и как решалась ?
Здесь я вижу один из альтернативных подходов к задачам , подобным "разузлованию" :
откажемся от встроенных возможностей платфомы 1с как неэффективных ! -
и во внешней обработке обратимся к базе 1с через ADO- соединение.
Ну и как ? Насколько помогло ? Каков максимальный граф ? и каково время обработки графа ?
86. SatanClaws 127 26.11.10 14:11 Сейчас в теме
(67)
Да это кусок из 1С++ класса, строящий фильтр по условию вхождения в группу справочника.

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

ЗЫ там, кстати, еще и ошибка сделана - одного Нолока не хватает.
Пойду убьюсь исправлю.
87. Ish_2 1038 26.11.10 15:08 Сейчас в теме
52. kim241 25.11.10 13:22 Сейчас в теме
В рекурсивном примере добавьте индекс для таблицы значений и скорость резко взлетит ;)
55. huse 25.11.10 17:48 Сейчас в теме
А откуда вообще предпосылка, что рекурсия медленная? Ведь другими словами Вы хотите сказать, что вызов функции в 8-ке медленный.
57. Ish_2 1038 25.11.10 17:53 Сейчас в теме
(55) Строго говоря , прав только опыт. И чем больше опытов - тем лучше.
(56) Ага. Так легче будет разбираться.
63. Ish_2 1038 25.11.10 22:08 Сейчас в теме
(62) Это ты сгоряча. Попробуй накидать такую процедуру .
65. Ish_2 1038 26.11.10 05:31 Сейчас в теме
(64) Да , согласен. Задача редкая и актуальна для крупных предприятий.
69. Арчибальд 2708 26.11.10 10:28 Сейчас в теме
+68 Т.о. "запросно-лобовой" подход к задаче разузлования совпадает с подходом "что тут думать, трясти надо". И трясем 20 секунд. Мой же вариант - сначала полсекунды "подумать" (преобразовать представление графа), а потом за полсекунды разузловать его.
"Запрос в БД - это сила. Рекурсия - это зло ."
Может, рекурсия и зло. Иногда. Но запрос - отнюдь не всегда сила. В контексте статьи - это зло.
72. Ish_2 1038 26.11.10 11:57 Сейчас в теме
(69) Да , не торопись ты с лозунгами. Разберись со своей обработкой.
83. Ish_2 1038 26.11.10 13:02 Сейчас в теме
(69) Прочти , пожалуйста (80) и (82).
Я просто хочу быть понятым.
У тебя на входе Справочник.Наборы , который я как-то хитро неизвестным тебе образом задал. В нем не один граф, в нем все графы номенклатуры предприятия.
Задаю тебе точку входа и ВСЁ.
Если ты рассмотришь задачу под таким углом зрения - ты всё поймешь. Именно так она ставится в реальных задачах разузлования. Так она стоит и у меня.
Другие разновидности задачи - ТРИВИАЛЬНЫ.

(81) Мало того , тест № 2 (20 уровней), такой же миллионник как и Тест№1, приведен здесь для того , чтобы утверждать универсальность обработки:
представленная обработка обработает граф произвольного вида до 20 уровня с миллионом уникальных узлов за время за 120-300 сек + время копирования справочника+время выгрузки миллиона элементов на форму в табличное поле.
Итого примерно 120-400 сек.
84. huse 26.11.10 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. Ish_2 1038 26.11.10 13:49 Сейчас в теме
88. Ish_2 1038 26.11.10 15:14 Сейчас в теме
(84) Код не смотрел. До этого не дошло. Провел два эксперимента.

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

2. Взял Тест №1. Интерактивно ( табличное поле Спецификации это позволяет) внес в спецификации зацикливание. Дальше смотри рисунок .
2.
Прикрепленные файлы:
125. huse 28.11.10 18:12 Сейчас в теме
(88) Красавец ))) ты бы еще задачу полностью переформулировал и потом что то доказывал. Ошибки я могу собирать - не интересно. Разница в количестве - в разной обработке ошибочной ситуации. Одинаковой и быть не может - мы по разному куб разбираем.

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

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

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

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

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

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

Пока же результаты (88) настолько красноречиво играют против рекурсии , что по-моему каких-то комментариев более не нужно.

92. Ish_2 1038 26.11.10 17:19 Сейчас в теме
Давайте по порядку.

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

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

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

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

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

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

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

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

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

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

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

А все таки пришлите свою заполнялку для дерева 1 111 111, чтобы я мог убедиться в послойном заполнении, можете проверить мою - работает не три часа, в 1,5 - рекурсия ;) !
94. Ish_2 1038 26.11.10 17:49 Сейчас в теме
(93)
1.требования вывода в табличный документ - у меня нет. Если есть то укажите.
Результат разузлования должен выводится на форму в виде табличного поля (таблицы значений).
2. Как же пользователь узнает где ошибка в графе ? как он её будет искать ?
У меня выдаются первые 100 ошибок в виде графа - причем именно там где они произошли (можете убедиться ) и пользователь может интерактивно их тут же исправить. Скажите как я проконтролирую правильность вашей обработки если мне выдастся просто сообщение для миллионного графа : элемент такой -то ? где его искать и в каких местах спецификации если он повторяется в 1000 спецификаций и лишь в одной из них он зацикливается ??
В условии задачи указана БП 1.6 - в этой конфигурации в справочнике Номенклатуры коды уникальны.
Что предложите ?
98. ildarovich 6734 26.11.10 18:18 Сейчас в теме
(94) Предложу подумать
1. Сколько цепочек будет выведено как циклические (без ограничений 100), если в тесте №2 ввести в две спецификации нижнего уровня две разных номенклатуры первого (уровни с нуля) уровня. Как выбрать ошибочную связь? (На самом деле в цепочках нужно посчитать дуги и проверить только самые часто встречающиеся - такой результат будет самым точным, но такой анализ выходит за рамки задачи).
Я бы предложил для поиска ошибок отдельную процедуру (функцию), на вход которой подается ошибочный узел из моего диагноза.
Вывод перепишу.
100. Ish_2 1038 26.11.10 18:32 Сейчас в теме
(98) А зачем думать ? Посмотрите как выводятся ошибки у меня в ЗапросПротивРекурсии.epf .
В демо БП запустите обработку. Заполните тестовый пример Тест № 1.
В табличном поле спецификации появится сформированное дерево с корнем Тест № 1.
Интерактивно открывайте любую ветку появится форма элемента справочника "СпецификацияНоменклатуры" -
исправляйте её как хотите. Вносите зацикливания и смотрите на странице панели "Ошибки",
что получится после "кнопки выполнить".
Прикрепленные файлы:
104. hogik 429 26.11.10 18:55 Сейчас в теме
(100)
Не удержусь - отвечу.
"Интерактивно открывайте любую ветку появится форма элемента справочника"(с)
Посадите на Ваш алгоритм двух пользователей.
Интерактивно... :-)
106. Ish_2 1038 26.11.10 19:26 Сейчас в теме
(104) Хорошо , что не удержались !
Только , Вадимир, в 8-ке два пользователя параллельно могут открыть форму элемента справочника.
При записи, правда, у последнего из двух попытавшихся записать этот элемент возникнут проблемы .
109. hogik 429 26.11.10 19:55 Сейчас в теме
(106)
Игорь, спасибо за пояснения отличий 8-ки от 7-ки. ;-)
Но, не про "проблемы" записи я Вам напомнил.
Прочтите, пожалуйста, моё сообщение #32 целиком.
Там есть слова: "Т.е. никакого воздействия данными отчета на исходную таблицы БД - невозможно". Готов дать пояснения...
P.S. Еще раз не удержусь - напишу.
Мне очень понравилось сравнение НАШЕЙ темы с "ковбоем, мистером и скотиной".
Однако у "скотины" кроме цены есть еще масса характеристик.
И если "мистер" собирается покупать "скотину" для людей или себя, то он, прежде всего смотрит на "скотину". А уже потом справляется о цене. И обсуждает разные нюансы выращивания "скотины".
А если "м..." собирается перепродать "скотину" и наварить на этом, то это уже другое название покупателя на букву "м". Его интересует прежде всего цена...
110. Ish_2 1038 26.11.10 20:00 Сейчас в теме
(109) Диалог двух персонажей и главный вопрос :

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

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

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

Я скачал обработку Сергея из его темы с названием что-то вроде : "Супер-быстрая обработка для БП 1.6".
Постараюсь сегодня доложить результаты .
95. Арчибальд 2708 26.11.10 17:51 Сейчас в теме
(92)
Арчибальд, мне нужно от тебя словесное уведомление ,
1. Что на входе алгоритма (процедура Разузловать()) у тебя только справочник Отборы структурой Отец , Сын, Количество и одна выбранная Позиция номенклатуры и ВСЕ !

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

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

Дополнительно: я явно указываю предельную длину цепочки. При превышении цепочка обрезается. Однако этот момент не критичен, можно этого и не делать - работоспособность сохраняется.
Прикрепленные файлы:
96. Ish_2 1038 26.11.10 18:06 Сейчас в теме
(95)Правильно ли я понял . Пример если в графе есть ветка:
Корень-Эл357-Эл31-Эл11-...Эл20- Эл54-Эл78--...Эл20.

Эту строку - ветку от корня я увижу целиком ? как сейчас на экране ?
так , как в моей обработке (только в строковом виде ) ?
P.S. Прошу поверить это не дурь и не придирки -
иначе я не проверю правильность контроля зацикливания.
не найдет её и пользователь, который работает со спецификациями, тот для которого всё и предназначено.
97. Ish_2 1038 26.11.10 18:14 Сейчас в теме
(95)+ Сам посуди , элемент Эл20 может в встретиться в 1000 спецификаций и лишь в одной из них он зациклен. Я его тогда не найду по информации "Корень - Эл20"
99. Арчибальд 2708 26.11.10 18:26 Сейчас в теме
(97) Зачем мне все ветки? Если в графе есть дуга с началом в Эл20 и концом в любом из предков Эл20, скажем, Эл50, ты предлагаешь мне перечислить все цепочки от Эл50 до Эл20? Ошибка-то одна, ее и фиксим, т.е. обрезаем дугу и сообщаем ее начало и конец (см. рисунок в 95 посте). А сколько различных циклов порождает эта ошибка - зачем это считать?
Оставьте свое сообщение

См. также

Агрегатные функции СКД, о которых мало кто знает 321

Статья Программист Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования

Пользуетесь ли Вы всеми возможными агрегатными функциями, которые предоставляет система компоновки данных? Если Вы используете только: СУММА, КОЛИЧЕСТВО, МИНИМУМ, МАКСИМУМ, СРЕДНЕЕ, то эта статья для Вас.

05.09.2019    10375    ids79    42       

Три костыля. Сказ про фокусы в коде 122

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Разработка

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

03.09.2019    7932    YPermitin    68       

Отслеживание выполнения фонового задания 134

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования Универсальные функции Разработка

Запуск фонового задания из модуля внешней обработки. Отслеживание выполнения задания в виде прогресса, расположенного на форме.

17.08.2019    8560    ids79    14       

Функции СКД: ВычислитьВыражение, ВычислитьВыражениеСГруппировкойМассив 245

Статья Программист Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования

Подробное описание и использование внутренних функций системы компоновки данных: Вычислить, ВычислитьВыражение, ВычислитьВыражениеСГруппировкойМассив, ВычислитьВыражениеСГруппировкойТаблицаЗначений.

08.08.2019    10807    ids79    24       

СКД - наборы данных и связи между ними, создание собственной иерархии, вложенные отчеты 126

Статья Программист Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования Разработка

Набор данных объект. Использование в схеме компоновки нескольких наборов данных. Различные варианты связи наборов: объединение, соединение. Использование иерархии в отчетах на СКД. Создание собственной иерархии, иерархия детальных записей. Использование вложенных схем в отчетах на СКД.

26.07.2019    9682    ids79    6       

СКД - использование расширений языка запросов, секция ХАРАКТЕРИСТИКИ 136

Статья Программист Нет файла v8 v8::СКД Бесплатно (free) Инструментарий разработчика Практика программирования Разработка

Автоматическое и не автоматическое заполнение полей компоновки данных. Использование расширений языка запросов для СКД «{…}», секция ВЫБРАТЬ, секция ГДЕ, параметры виртуальных таблиц. Автоматизированное использование дополнительных данных в запросе: секция ХАРАКТЕРИСТИКИ.

17.07.2019    8943    ids79    24       

"Меньше копипаста!", или как Вася универсальную процедуру писал 170

Статья Программист Стажер Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования Разработка

Программист Вася разбирает подход создания универсальных методов на примере программного вывода СКД.

04.07.2019    6308    SeiOkami    48       

Создание отчетов с помощью СКД - основные понятия и элементы 198

Статья Программист Нет файла v8 v8::СКД Бесплатно (free) Практика программирования Математика и алгоритмы

Основные принципы работы СКД. Понятия схемы компоновки и макета компоновки. Описание основных элементов схемы компоновки: наборы данных, поля, вычисляемые поля, ресурсы, параметры.

25.06.2019    17846    ids79    17       

Многопоточное ускорение однопользовательских нагрузок в 1С + Microsoft SQL Server 2017 176

Статья Программист Нет файла v8 v8::Запросы Бесплатно (free) Практика программирования Разработка

Взаимодействие с Microsoft SQL Server нередко вызывает трудности у 1С-ников, а потому интересны любые моменты, связанные с его использованием. О своем опыте работы с новым SQL Server 2017 участникам конференции Infostart-2018 рассказал директор ООО «Аналитика софт» Дмитрий Дудин.

11.06.2019    11647    dmurk    134       

Регистры накопления. Структура хранения в базе данных 174

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования Разработка

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

16.05.2019    17396    YPermitin    27       

Выполнение внешней обработки в фоновом задании 147

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования Разработка

Подробное описание подхода к созданию длительной операции на основе внешней обработки. Реализация протестирована на 1С 8.3.12.1714 (x64).

11.05.2019    10005    Eret1k    22       

Выгрузка документа по условию 5

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Разработка

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

25.04.2019    4896    m-rv    2       

Как прикрутить ГУИД к регистру сведений 23

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Перенос данных из 1C8 в 1C8 Разработка

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

16.04.2019    7463    m-rv    16       

О расширениях замолвите слово... 192

Статья Программист Стажер Нет файла v8 Бесплатно (free) Практика программирования Разработка

О чём стоит задуматься при принятии решения о создании расширения конфигурации…

07.04.2019    16505    ellavs    122       

Git-репозитории для 1С-кода (опыт использования при небольших проектах) 200

Статья Программист Стажер Нет файла v8 Windows Бесплатно (free) Практика программирования Разработка

Инструкции по взаимодействию с Git-репозиторием, которые писались для тех наших программистов, которые вообще никогда не работали с Git (руководства в духе "Как получить код из git-репозитория?", "Как отправить код в git-репозиторий")...

28.03.2019    12847    ellavs    83       

Трюки с внешними источниками данных 164

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования Разработка

Некоторые трюки для преодоления ограничений внешних источников данных.

14.03.2019    12952    YPermitin    52       

Возможности типовых шаблонов ограничения доступа на уровне записей (RLS) 163

Статья Программист Нет файла v8 v8::Права Бесплатно (free) Практика программирования БСП (Библиотека стандартных подсистем) Роли и права

Краткий обзор применения типовых шаблонов ограничения доступа на уровне записей в конфигурациях, созданных на базе БСП: #ПоЗначениям, #ПоНаборамЗначений, #ПоЗначениямРасширенный, #ПоЗначениямИНаборамРасширенный

03.02.2019    15703    ids79    9       

EnterpriseData – часть 2. Процесс выгрузки данных 127

Статья Программист Нет файла v8 v8::УФ Россия Бесплатно (free) Практика программирования Обмен через XML

Основные этапы выгрузки данных через ED, обработчики событий выгрузки, правила обработки данных, правила конвертации объектов, конвертация свойств первого и второго этапов, процедуры БСП, используемые при выгрузке данных, структура «КомпонентыОбмена».

26.12.2018    12814    ids79    27       

Новый подход к обмену данными EnterpriseData 203

Статья Программист Нет файла v8 v8::УФ Россия Бесплатно (free) Практика программирования Обмен через XML

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

14.12.2018    21634    ids79    72       

Партионный учет товаров в конфигурациях УТ, КА, ЕРП 154

Статья Программист Бизнес-аналитик Бухгалтер Нет файла v8 v8::УФ ERP2 УТ11 КА2 Россия УУ Учет ТМЦ Бесплатно (free) Управленческий учет (прочее) Бухгалтерский учет

История развития, особенности реализации в текущих версиях ЕРП 2.4, КА 2.4, УТ 11.4, методы оценки стоимости запасов, примеры расчета стоимости списания

08.12.2018    22681    ids79    47       

Учет товаров по сериям в типовых конфигурациях УТ 11.4, КА 2.4, ЕРП 2.4 124

Статья Программист Бухгалтер Нет файла v8 v8::УФ ERP2 УТ11 КА2 Россия УУ Учет ТМЦ Бесплатно (free) Бухгалтерский учет Управленческий учет (прочее)

Возможности и настройки подсистемы серийного учета, отражение данных по сериям в регистрах и отчетах системы, выявленные нюансы

02.12.2018    22375    ids79    98       

Программное заполнение пользовательских параметров и отборов СКД 135

Статья Программист Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования

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

13.11.2018    19956    Unk92    18       

Автоматические и управляемые блокировки применительно к типовым конфигурациям 1С 126

Статья Программист Нет файла v8 v8::blocking 1cv8.cf Бесплатно (free) Математика и алгоритмы Практика программирования

Основные принципы работы с режимами автоматических и управляемых блокировок в 1С Предприятие 8. Теория и применение в типовых конфигурациях: БП, УТ, ЕРП

10.11.2018    20989    ids79    40       

Вспомогательные инструкции в коде 1С 104

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования

Помогаем редактору кода 1С помогать нам писать и анализировать код.

15.10.2018    20581    tormozit    100       

Произвольный код в фоновом режиме 165

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования

Задача: реализовать выполнение произвольного кода в фоновом режиме без изменения конфигурации, т.е. во внешней обработке.

03.09.2018    14701    nikita0832    41       

Основные понятия и механизмы оптимизации клиент-серверного взаимодействия в 1C 144

Статья Программист Нет файла v8 Россия Бесплатно (free) Математика и алгоритмы Практика программирования

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

23.08.2018    21448    Rain88    42       

Повышаем эффективность разработки правил обмена 124

Статья Программист Нет файла v8 КД ОС Бесплатно (free) Практика программирования Перенос данных из 1C8 в 1C8

Как повысить скорость и качество разработки правил обмена? Как вести групповую разработку правил обмена? Как облегчить сопровождение правил обмена после передачи в эксплуатацию? Об этом и многом другом вы можете узнать из этой статьи.

25.06.2018    19390    olegtymko    47       

Введение в механизм представлений в ЗУП ред. 3 153

Статья Программист Нет файла v8 v8::СПР ЗУП3.x Бесплатно (free) Практика программирования

В нашей организации на первом же телефонном собеседовании на должность разработчика по ЗУП ред. 3 вас обязательно спросят о том, что такое "Представления".

04.06.2018    24532    xrrg    82       

Как сделать запрос на изменение данных 75

Статья Программист Нет файла v8 v8::Запросы 1cv8.cf Бесплатно (free) Практика программирования

В статье приведены особенности внутренней архитектуры и примеры работы с расширением языка запросов 1С.

01.06.2018    21287    m-rv    21       

Строим графы средствами 1С (без GraphViz) 42

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования

Множество статей на Инфостарте описывают, как работать с компонентой GraphViz, чтобы построить ориентированный граф. Но практически нет материалов, как работать с такими графами средствами 1С. Сегодня я расскажу, как красиво строить графы с минимальным пересечением. Нам этот метод пригодился для отрисовки алгоритмов в БИТ.Финансе, т.к. типовой механизм не устраивал. Еще это может быть полезно для визуализации различных зависимостей: расчета себестоимости, графы аффилированности компаний и т.д. Надеюсь, эта статья поможет сделать мир 1С красивее и гармоничней:) Итак, поехали...

23.05.2018    17066    slozhenikin_com    19       

Распределение расходов пропорционально продажам 9

Статья Программист Пользователь Нет файла v8 v8::ОУ УТ10 УУ Финансовый учет и бюджетирование (FRP) Учет доходов и расходов Бесплатно (free) Практика программирования

Финансовая модель. Распределение административных расходов по подразделениям пропорционально продажам за месяц. Дополнительные реквизиты против бизнес-процессов!

13.05.2018    11414    Rustig    9       

Просмотр временных таблиц запроса в отладчике без изменения кода 126

Статья Программист Нет файла v8 v8::Запросы 1cv8.cf Бесплатно (free) Практика программирования

Данный способ можно использовать для просмотра содержимого временных таблиц запросов (менеджеров временных таблиц) без внесения изменений в код.

24.04.2018    24636    avfed@rambler.ru    19       

Минимализмы 3 353

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Универсальные функции

Очередная серия "минимализмов" [http://infostart.ru/public/306536/, https://infostart.ru/public/460935/]. Также, как и в предыдущих статьях, здесь приведена подборка коротких оригинальных авторских решений некоторых задач. Ранее эти решения были разбросаны по моим комментариям к чужим публикациям.

19.02.2018    35761    ildarovich    44       

Этюды по программированию. Взаимодействие с Microsoft Word 109

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования

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

11.12.2017    25929    milkers    23       

Метод формирования движений в типовых регистрах нетиповыми регистраторами 31

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования

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

05.12.2017    21378    itriot11    34       

1С: Конвертация данных 3. Инструкции и примеры. EnterpriseData (универсальный формат обмена) 724

Статья Программист Нет файла v8 КД Бесплатно (free) Перенос данных из 1C8 в 1C8 Практика программирования Обмен через XML

Что такое КД3? Как начать использовать? Полезные дополнения к документации. Что нужно исправить в типовых обработках и конфигурации. Как изменить правила обмена не снимая конфигурацию с поддержки. Как отлаживать правила обмена?

19.11.2017    138268    MaxS    251       

Заполнение данных по ИНН контрагента с помощью альтернативного сервиса огрн.онлайн 131

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования

Код для заполнения данных по ИНН контрагента из ЕГРЮЛ с сайта огрн.онлайн.

01.11.2017    22794    slava_1c    49       

Программные перечисления, ч.2: приемы кэширования при разработке 67

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования

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

30.10.2017    21146    unichkin    18       

Разбираемся с настройками компоновки данных 159

Статья Программист Нет файла v8 v8::СКД 1cv8.cf Бесплатно (free) Практика программирования

Краткая шпаргалка по программной работе с настройками СКД

29.10.2017    24137    json    9       

Работа с Excel 289

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Загрузка и выгрузка в Excel

Собрал различные полезности для работы с Excel из 1С. Иногда приходится форматировать документ Excel программно из 1С. Так вот, чтобы не искать постоянно на просторах интернета как сделать левое выравнивание в ячейке Excel из 1С и т.п. решил опубликовать это...

23.10.2017    24947    arakelyan    39       

Добавление команд печати в конфигурациях на БСП 2.4.3 (в частности, в самописных документах в Бухгалтерии 3.0 после релиза 3.0.52.35) 143

Статья Программист Нет файла v8 v8::БУ БП3.0 Россия Бесплатно (free) Печатные формы документов Практика программирования БСП (Библиотека стандартных подсистем)

В статье https://infostart.ru/public/237013/ пользователя nick max рассматривался список действий для подключения команд печати в Бухгалтерии 3.0, работающей на БСП 2.3.6. В новом релизе Бухгалтерии 3.0.52.35 от 15.09.2017г. стала использоваться БСП 2.4.3, из-за чего произошли изменения в процедурах общих модулей, связанных с механизмом печати, и в процедурах их вызова в формах документов и в формах списков. Рассмотрим их.

18.09.2017    47035    bugtester    43       

Отказ от работы с временными файлами при работе с двоичными данными или Потоки как простая замена ADODB.Stream и временным файлам 127

Статья Программист Нет файла v8 Россия Бесплатно (free) Практика программирования

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

12.09.2017    18326    vardeg    31       

Как сделать из &НаКлиентеНаСервереБезКонтекста почти &НаКлиентеНаСервере 125

Статья Программист Нет файла v8 1cv8.cf Россия Бесплатно (free) Практика программирования

Как сделать метод формы, доступный на клиенте и на сервере одновременно, и сохранить при этом удобство разработки

10.09.2017    34313    tormozit    72       

Ускоряем 1С: модули с повторным использованием возвращаемых значений 136

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования

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

04.09.2017    43269    m-rv    60