<?php // Полная загрузка сервисных книжек, создан 2025-01-05 12:44:55
global $wpdb2;
global $failure;
global $file_hist;
///// echo '<H2><b>Старт загрузки</b></H2><br>';
$failure=FALSE;
//подключаемся к базе
$wpdb2 = include_once 'connection.php'; ; // подключаемся к MySQL
// если не удалось подключиться, и нужно оборвать PHP с сообщением об этой ошибке
if (!empty($wpdb2->error))
{
///// echo '<H2><b>Ошибка подключения к БД, завершение.</b></H2><br>';
$failure=TRUE;
wp_die( $wpdb2->error );
}
$m_size_file=0;
$m_mtime_file=0;
$m_comment='';
/////проверка существования файлов выгрузки из 1С
////файл выгрузки сервисных книжек
$file_hist = ABSPATH.'/_1c_alfa_exchange/AA_hist.csv';
if (!file_exists($file_hist))
{
///// echo '<H2><b>Файл обмена с сервисными книжками не существует.</b></H2><br>';
$m_comment='Файл обмена с сервисными книжками не существует';
$failure=TRUE;
}
/////инициируем таблицу лога
/////если не существует файла то возврат и ничего не делаем
if ($failure){
///включает защиту от SQL инъекций и данные можно передавать как есть, например: $_GET['foo']
///// echo '<H2><b>Попытка вставить запись в лог таблицу</b></H2><br>';
$insert_fail_zapros=$wpdb2->insert('vin_logs', array('time_stamp'=>time(),'last_mtime_upload'=>$m_mtime_file,'last_size_upload'=>$m_size_file,'comment'=>$m_comment));
wp_die();
///// echo '<H2><b>Возврат в начало.</b></H2><br>';
return $failure;
}
/////проверка лога загрузки, что бы не загружать тоже самое
$masiv_data_file=stat($file_hist); ////передаем в массив свойство файла
$m_size_file=$masiv_data_file[7]; ////получаем размер файла
$m_mtime_file=$masiv_data_file[9]; ////получаем дату модификации файла
////создаем запрос на получение последней удачной загрузки
////выбираем по штампу времени создания (редактирования) файла загрузки AA_hist.csv, $m_mtime_file
///// echo '<H2><b>Размер файла: '.$m_size_file.'</b></H2><br>';
///// echo '<H2><b>Штамп времени файла: '.$m_mtime_file.'</b></H2><br>';
///// echo '<H2><b>Формирование запроса на выборку из лога</b></H2><br>';
////препарируем запрос
$text_zaprosa=$wpdb2->prepare("SELECT * FROM `vin_logs` WHERE `last_mtime_upload` = %s", $m_mtime_file);
$results=$wpdb2->get_results($text_zaprosa);
if ($results)
{ foreach ( $results as $r)
{
////если штамп времени и размер файла совпадают, возврат
if (($r->last_mtime_upload==$m_mtime_file) && ($r->last_size_upload==$m_size_file))
{////echo '<H2><b>Возврат в начало, т.к. найдена запись в логе.</b></H2><br>';
$insert_fail_zapros=$wpdb2->insert('vin_logs', array('time_stamp'=>time(),'last_mtime_upload'=>$m_mtime_file,'last_size_upload'=>$m_size_file,'comment'=>'Загрузка отменена, новых данных нет, т.к. найдена запись в логе.'));
wp_die();
return $failure;
}
}
}
////если данные новые, пишем в лог запись о начале загрузки
/////echo '<H2><b>Попытка вставить запись о начале загрузки в лог таблицу</b></H2><br>';
$insert_fail_zapros=$wpdb2->insert('vin_logs', array('time_stamp'=>time(),'last_mtime_upload'=>0, 'last_size_upload'=>$m_size_file, 'comment'=>'Начало загрузки'));
////очищаем таблицу
$clear_tbl_zap=$wpdb2->prepare("TRUNCATE TABLE %s", 'vin_history');
$clear_tbl_zap_repl=str_replace("'","`",$clear_tbl_zap);
$results=$wpdb2->query($clear_tbl_zap_repl);
///// echo '<H2><b>Очистка таблицы сервисных книжек</b></H2><br>';
if (empty($results))
{
///// echo '<H2><b>Ошибка очистки таблицы книжек, завершение.</b></H2><br>';
//// если очистка не удалась, возврат
$failure=TRUE;
wp_die();
return $failure;
}
////загружаем данные
$table='vin_history'; // Имя таблицы для импорта
//$file_hist Имя CSV файла, откуда берется информация // (путь от корня web-сервера)
$delim=';'; // Разделитель полей в CSV файле
$enclosed='"'; // Кавычки для содержимого полей
$escaped='\
однозначно чтобы понять рекурсию, надо понять рекурсию
Может так правильней 😉
Процедура ИзменитьПометкиПодчиненных(Строка)
Для Каждого Подчиненный Из Строка.Строки Цикл
Подчиненный.Пометка = пГлавный.Пометка;
ИзменитьПометкиПодчиненных(Подчиненный);
КонецЦикла;
КонецПроцедуры
(1) Это поможет:-)))
Но, как доказано где-то когда-то и вроде как математически, любую задачу решаемую рекурсивно, можно решить итеративно и наоборот. Причем в 1С, уж в семерке так точно, рекурсия более затратна, чем цикл:-)
З.Ы. Ниче против статьи и ее автора не имею, просто ремарка:-)
(2) Вобще то да, пара строчек балласта убрано 🙂
(3)>Но, как доказано где-то когда-то и вроде как математически, любую задачу решаемую рекурсивно, можно решить итеративно и наоборот.
Вот и скелет доказательства:
f(n+1)=g(f(n))
означает просто
f(n+1)=g(g(g(……g(1)….)
что реализуется циклом
f=g(1);
for i=1 to n loop
f=g(f);
endloop
И далее индукция по n…
(3) рекурсия более понятна. На счет затратно сомневаюсь :). Хотелось бы увидеть замену рекурсии для варианта автора.
(6) Замерь две функции из первого поста отсюда:
И убедишься.
(7) что на счет примера автора
(8) Что насчет замера? Какие результаты, в семерке, в восьмерке?
(7) Для приведенного примера ИМХО рекурсия не нужна. Для примера автора пожалуйста
(9) Так можно увидеть вариант автора без рекурсии
(10) Причем тут одно к другому, давайте разбираться последовательно, Вы выразили сомнения в том, что рекурсия затратнее цикла, Вам предложен чистый эксперимент, без инородных влияющих факторов. Каковы результаты?
(12) В приведенном примере рекурсия не нужна.
Вы пишите «Причем в 1С, уж в семерке так точно, рекурсия более затратна, чем цикл:-)» т.е. утверждаете что рекурсия более затратна, хотелось бы видеть для варианта автора
Предлагаю простое сравнение, нужно написать программу которая выводит числа от 1 до 100 с помощью цикла и с помощью рекурсии и сделать замер производительности.
(6, 10) В чем вопрос-то? Как обойти дерево без рекурсии? Или насколько различаются по затратам рекурсивный обход и нерекурсивный?
(14) Чем плох для сравнения этот пример:
(15) Как обойти дерево без рекурсии, а то человек волнуется и все одно и тоже повторяет, своих ошибок признать не хочет:-)))
А кто-нибудь замерял глубину стека в 1С?
Итак, с использованием рекурсии:
Процедура ВывестиЧисло(пЧисло)
Если пЧисло > 100 Тогда
Возврат;
Иначе
Сообщить(Строка(пЧисло));
пЧисло = пЧисло + 1;
ВывестиЧисло(пЧисло);
КонецЕсли;
КонецПроцедуры
ВывестиЧисло(1);
0,1154 сек.
Без использования рекурсии
Для Счетчик = 1 По 100 Цикл
Сообщить(Строка(Счетчик));
КонецЦикла;
0,1118 сек.
Почти одинаково, но рекурсия все же работает немного быстреее
(19) рекурсия работает немного медленнее
(16) тем что там рекурсия не нужна. ИМХО когда рекурсия необходима ее замена не будет эффективней.
(19) Пример жесть!!! :)))) пожалуйста НА ПРИМЕРЕ АВТОРА ТЕМЫ
(22) сейчас попробую
(17) «Как обойти дерево без рекурсии, а то человек волнуется и все одно и тоже повторяет, своих ошибок признать не хочет:-)))» в чем моя ошибка поясните пожулайста.
(17)Заводим два списка ссылок: на текущий уровень и на подчиненный. Первоначально первый список содержит сылку на корень, второй пуст.
Цикл пока не пуст первый список
Цикл по элементам первого списка
Тело: пометить подчиненные и загнать их во второй список
Конец вложенного цикла
Второй список сделать первым
Завести второй пустой список
Конец внешнего списка.
рекурсия 0,092427
цикл 0,056335
Но это ни о чем не говорит, да в цикле быстрее, но зато рекурсия дает дополнительные возможности. Если дерево очень большое, или размер дерева неизвестен кроме рекурсии ничего больше использовать просто нельзя.
(21),(22) Значит первое мы определили, при прочих равных рекурсия затратнее цикла, надеюсь Вы согласитесь:-) Причем родители в справочнике тоже дерево, по сути, чтоб Вы не питали иллюзий:-) Я про пример из форума, куда я давал ссылку, а если Вам лень замерить, то с Вами трудно говорить:-) Это раз:-)
Второе, для того, чтобы мне поиграться с обходом дерева значений, т.к. оно есть только в восьмерке, мне придется дома найти и поставить восьмерку и посмотреть, какие методы и т.п. есть у этого объекта или что оно там, ибо восьмерку в глаза не видел, так что вам придется подождать пока я найду, поставлю, поиграюсь с восьмеркой. Или восьмерошники выдадут быстрее. Так что подождите. Но по поводу затратности рекурсии по сравнению с циклом при прочих равных мы убедились или еще сомневаемся?:-)))
(26) См. 25 пост ;))
(27) а можно это выразить в коде
(22) +28, о вот выдали быстрее, чем я дома поставил восьмерку:-))) Пост 25-й Вас удовлетворил?:-))
(30) меня не очень, хотелось бы увидеть это в коде
(29) Ну, ты сказал:)))
Описания осьмерочного языка под рукой нет.
Устроит в семерке обход дерева, где корень и ветви имеют тип СписокЗначений, а листья — другой тип?
(32) устроит, только вот как в семерке можно реализовать дерево, там же такого объекта нет ?
(32) на 1cpp что ли ?
(26) На чем тестил? А часто ли размер дерева известен? 🙂
(25) Не мерял, но почти уверен рекурсия будет эффективней
(28) «Значит первое мы определили, при прочих равных рекурсия затратнее цикла, надеюсь Вы согласитесь:-)» нет там совсем другой случай там рекурсия не нужна НА ПРИМЕРЕ АВТОРА ПОЖАЛУЙСТА
Для примера автора: рекурсию в 4 строки себе представляют все, а заменить рекурсию сложнее
Полный обход дерева каталогов как раз подходит для рекурсии
«Лучше рекурсия чисто в эстетическом плане и в понимании кода, а фактически хуже (т.к. время на запись активации функции и размещения её на стэк всяка медленнее чем обычный jump). Т.к. для данной задачи производительность не критична, лично я голосую за рекурсию.»
Взято отсюда:
(35) тестил на
в текущей версии 2.3 используется рекурсия,
в более старой версии 2.1 используется цикл,
дерево совершенно одинаковое (4 уровня, одинаковое количество элементов), тестил на одной и той же базе, на одном и том же компьютере
(33) В семерке есть все:)))
//Корень — это и есть корень
ТекСписок=СоздатьОбъект(«СписокЗначений»);
СледСписок=СоздатьОбъект(«СписокЗначений»);
ТекСписок.ДобавитьЗначение(Корень);
Пока ТекСписок.ДлинаСписка()<>0 Цикл
Для й=1 по ТекСписок.ДлинаСписка() Цикл
Ссылка=ТекСписок.ПолучитьЗначение(й);
Если ТипЗначенияСтр(Ссылка)<>»СписокЗначений» Тогда
//Это лист. Делаем с ним, что хотим, типа стамим пометку
Иначе //Это ветка. Вносим в список след. уровня
СледСписок.ДобавитьЗначение(Ссылка);
КонецЕсли;
КонецЦикла;
ТекСписок=СледСписок;
СледСписок=СоздатьОбъект(«СписокЗначений»);
КонецЦикла;
(0) И конструкцию «Для Каждого … Из …» заменить на «Для … По …».
Это даст хороший прирост скорости.
(26) Таки можно?
Все это ерунда.
Конструкции типа:
Показать полностью
Непонятны и трудночитаемы. Выйгрыш на дереве в 4-5 вложенности будет минимальным, при вложенности 1000 страшно представить себе этот код.
Во общем наш выбор: рекурсия!
(41) См. пост 36. И 39 тоже.
Кодеры, блин…
(39) надо будет попробовать
(40) дерево значений созданное из списков значений рулит однозначно ))), семерка действительно может все )))
(42) И что? Можете пример для 30 уровней вложенности привести?
Выигрыш в долю микросекунды на маленьком дереве меня не интересует, если придется потратить десятки минут на то чтобы разобраться в 100 там, где достаточно 10.
в 100 строчка кода имелось ввиду.
Давайте исходит из примера автора т.к. для 90% приведенных случаев рекурсия не нужна в том числе и в варианте форума от Душелова. Я чуток знаю низкий уровень (assembler) вызов функции это очень мало операций
push АдресВозврата;
push ПеременнаяХ;
Jmp АдресПроцедуры;
+
Внутри процедуры
Одно вычитание (сдвиг стека)
и возврат
Если выигрыш и будет, то ничтожный и есть много других факторов размер кэша и прочее.
(37) а что делать если число уровней неизвестно
(44,45) Я ж и привел в 25 и 38. Количество уровней не лимитировано. А авторский текст, процитированный в (41) — жесть, что я попытался выразить в 42 посте…
ВоооООтоЧемрееееЕчь…
(44) в приведенном примере всего 4 уровня, причем в где изначально использовалась процедура из (41) размер дерева и структура фиксированы (корень, коллекции, объекты, таблицы). Если дерево больше, я согласен что надо использовать рекурсию. Да собственно и в этом примере она целесообразнее. Но если дерево небольшое, и размер его фиксирован, то не принципиально что использовать.
Речь о том что рекурсия эффективней в тех случаях когда она реально необходима, пример полный обход дерева каталогов диска
Преимущество рекурсии: читабельность, модифицируемость, разница в скорости ничтожна и в большинстве случаев влияют другие факторы
Что пишет MSDN:
Рекурсивные процедуры
Рекурсивная процедура — это процедура, которая вызывает сама себя. Как правило, это не самый эффективный способ написания кода.
**** Рассмотрение рекурсивных процедур
— Ограничивающие условия.
Необходимо разработать рекурсивную процедуру для проверки по крайней мере одного условия, которое может прервать рекурсию, а также необходимо рассмотреть случаи, когда такое условие не выполняется в течение разумного числа рекурсивных вызовов. Без, по крайней мере, одного условия, которое может быть выполнено без ошибок, возникает большой риск выполнения в бесконечном цикле.
— Использование памяти.
Приложение имеет ограниченный объем пространства для локальных переменных. Каждый раз, когда процедура вызывает саму себя, она использует больше этого пространства для дополнительных копий ее локальных переменных. Если этот процесс будет продолжаться неопределенно долго, он в конечном счете вызовет ошибку StackOverflowException.
— Эффективность.
Почти всегда можно заменить цикл для рекурсии. Цикл не имеет дополнительных издержек аргументов передачи, инициализации дополнительного хранилища и возврат значений. Производительность может быть гораздо выше без рекурсивного вызова.
— Взаимная рекурсия.
Можно наблюдать очень низкую производительность или даже бесконечный цикл, если две процедуры вызывают друг друга. Такой макет представляет те же проблемы, что и одна рекурсивная процедура, но это может быть сложнее обнаружить и отладить.
— Тестирование.
Если Вы пишете рекурсивную процедуру, необходимо проверить ее очень внимательно, чтобы убедиться в в том, что она всегда удовлетворяет некоторому граничному условию. Следует также убедиться в том, что в результате слишком большого количества рекурсивных вызовов вы не израсходуете всю доступную память.
(49) Набор «последовательность+Ветвление+цикл» является ДОСТАТОЧНЫМ для любого алгоритма. Это постулат. Поэтому случаев, когда рекурсия НЕОБХОДИМА просто не существует. Другое дело, что рекурсия зачастую элегантней выглядит…
Вопрос:
— Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует памяти, линейно возрастающей с вызовом процедур? Насколько я понимаю, в момент вызова процедуры в стек помещаются параметры процедуры. А если их нет? Адрес возврата?
Ответ:
— Да. Так или иначе запоминается адрес возврата.
Локальные переменные ещё.
Взято тут:
(52) В ряде случаев рекурсия бывает выгоднее.
Рассматривается решение задачи «ханойская башня». Ее содержательная постановка такова. В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров.
В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.
Беспокоиться о близком конце света не стоит. Задача эта не под силу и современным компьютерам. Число ходов в ней равно 264, а это, как известно, большое число, и компьютер, работающий в сотню миллионов раз быстрее монахов, не справится с этой задачей в ближайшие тысячелетия.
….
В рекурсивном варианте исчезли все трудности, связанные с выбором хода и соблюдением правил. Выбор выполняется почти автоматически, поскольку слияние частных решений не нарушает правил. В этом еще одна мощь рекурсии.
….
Можно показать, что последовательность ходов, реализуемая рекурсивным алгоритмом, является оптимальной, так что никакой другой алгоритм не может решить задачу за меньшее число ходов.
Согласен с рекомендациями, но сам знаешь что есть случаи когда рекурсия лучший выбор, пример полный обхода дерева. А все эти факторы влияют по разному в разных случаях гдето например «эффективность использования памяти» сходит на нет.
(53) 264 = 2**64? ;)))
Итак к чему мы пришли:
вариант приведенный в (41) основан на циклах, выполняется быстрее рекурсии, но не подходит для слишком больших деревьев или деревьев с неизвестным количеством уровней;
собственно рекурсия, очень простой и читабельный код, подходит для деревьев любого размера но может вызвать переполнение стека и выполняется медленнее варианта построенного на циклах;
вариант предложенный Арчибальдом, построен на циклах, поэтому не имеет недостатков рекурсии, подходит для деревьев любого размера, но код его менее читабельный чем рекурсия, к тому же требует адаптации к 8-ке.
(53)Там, главное, не перепутать (чтобы кольца в конце оказались на второй, а не на третьей пирамиде). Поэтому цепочку действий оптимальнее «раскручивать» с конца, т.е. рекурсивно. Без рекурсии мы вынуждены работать с начала…
Тема безрекурсивного вывода дерева ФС не раскрыта.
ps
Если что, то под древовидным выводом я понимаю такой вывод в котором видна родственная связь элементов
(58) Рекурсивного вывода, кстати, тоже…
(56) Осталось только все выводы учесть в шапке статьи как оказалось все не однозначно :)))
Кстати про недостаток рекурсии «переполнение стека» это происходит при большом уровне вложенности что крайне редко. ИМХО «замены» потребляют не меньше памяти
(60) Адаптирую вариант Арчибальда под 8-ку (если получиться), сделаю замеры производительности по всех вариантах, вот тогда и допишу концовку статьи со сравнением. А пока еще не все ясно.
(59)
Перем гТекст;
Процедура ВывестиПодчиненные(Каталог, Отступ=»»)
Перем Атрибуты;
Состояние(Каталог);
_ФС = СоздатьОбъект(«ФС»);
ИмяФайла = _ФС.НайтиПервыйФайл(Каталог+»*»);
Пока ПустаяСтрока(ИмяФайла) = 0 Цикл
Если Лев(ИмяФайла, 1) <> «.» Тогда
гТекст.ДобавитьСтроку(Отступ+ИмяФайла);
_ФС.АтрибутыФайла(Каталог+ИмяФайла,,Атрибуты);
Если Сред(Атрибуты, 4, 1) = «1» Тогда
ВывестиПодчиненные(Каталог+ИмяФайла+»», Отступ+» «);
КонецЕсли;
КонецЕсли;
ИмяФайла = _ФС.НайтиСледующийФайл();
КонецЦикла;
КонецПроцедуры
Процедура Сформировать()
гТекст = СоздатьОбъект(«Текст»);
ВывестиПодчиненные(«C:»);
гТекст.Показать(«C:»);
КонецПроцедуры
(59) твой ход
На 8-ке:
Процедура КнопкаВыполнитьНажатие(Кнопка)
ОбходДереваКаталоговРекурсия(«D:DISTRIB»)
КонецПроцедуры
Процедура ОбходДереваКаталоговРекурсия(Каталог)
НайдФайлы = НайтиФайлы(Каталог,»*.*»);
Для Каждого Файл Из НайдФайлы Цикл
Состояние (Файл.ПолноеИмя);
Если Файл.ЭтоКаталог() Тогда
ОбходДереваКаталоговРекурсия(Файл.ПолноеИмя);
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Вместо «Состояние (Файл.ПолноеИмя);» можно вставить любой код
(63) Да не интересно мне. Ясно же, что решаемо, и достаточно просто.
В цикл преобразуется только хвостовая рекурсия.
Остальные виды рекурсий в общем виде пробразуются в «цикл + стек».
Рассматривая языки более приближенные к процессору, чем 1С (такие как С / С++), стоит отметить, что организация стека при рекурсивном вызове заключается лишь в изменении стекового регистра. А вот организация объекта-стека при безрекурсивном цикле может быть довольно-таки сложна и включать в себя работу с динамической памятью (выделение/перевыделение), копировании объектов в стек и обратно и тп. Так что имхо на С и С++ для нетривиальных рекурсий довольно неплохие шансы побить их безрекурсивные аналоги.
(0) комментарии к последнему выводу
«Перейдем к недостаткам. Использование рекурсии с большой глубиной может привести к переполнению стека и ошибке в работе программы. В случае использования рекурсии быстродействие программы уменьшается сравнительно с использованием циклов. Следовательно, если количество уровней вложенности дерева относительно небольшое, а количество строк большое, то целесообразнее использовать циклы.»
Неверный вывод. Для большой глубины замены рекурии будут также переполнять память.
«Следовательно, если количество уровней вложенности дерева относительно небольшое, а количество строк большое, то целесообразнее использовать циклы». Один из недостатков рекурсии доп. вызов функции, но он производится только при шаге в глубь.
(66) да и зачем реализовывать тоже самое что уже реализовано внутри «call» (вызова процедуры)
Обновил статью, добавил в начало несколько простых примеров для лучшего понимания, провел тестирование производительности и получил определенные выводы.
В общем для деревьев с большим количеством строк и малым количеством уровней оптимальнее использовать циклы. Выигрыш в быстродействии.
Для деревьев с малым количеством строк и большим количеством уровней оптимальнее использовать рекурсию. Выигрыш в читабельности и размере кода.
Для деревьев с большим количеством строк и большим количеством уровней оптимальнее использовать рекурсию. Выигрыш в читабельности и размере кода но снижение быстродействия.
Для деревьев с малым количеством строк и малым количеством уровней нет разницы что использовать.
Для деревьев с неизвестным заранее количеством уровней можно только использовать рекурсию.
(68) можно увидеть примеры на которых вы тестировали т.к. я в них сомневаюсь если это «ВывестиЧисла(пЧисло)» то тогда понятно.
Для тех случаев когда рекурсия необходима она не имеет значительной потери в скорости, а должна даже выигрывать и неважно сколько в дереве уровней и строка рекурсия будет эффективной.
Еще пример для рекурсии расчет выражений например:
«С=A+B; A=10; B=A+7»
Для обхода дерева с неограниченным количеством уровней как в твоем примере для 8.х никто не привел пример. Как мне кажется я потрачу на это больше часа и точно не будет быстрее твоего варианта.
А пример 38 омеет очень много операций он не будет быстрым
В конце статьи есть ссылка на обработку на которой я тестировал. Дерево небольшое, около 1000 строк, 4 уровня. Можешь сам попробовать. Там просто нужно заменить процедуру ИзменитьПометкиПодчиненных() на один а затем на другой вариант и посмотреть что будет быстрее. А насчет вывода чисел — так это только пример, для лучшего понимания, практического значения он не имеет.
(70) около 1000 строк было на той конфигурации, на которой я тестировал, на других может быть и больше (в зависимости от количества метаданных и таблиц)
(71) Проверил. Для замены на 4 ре цикла рекурсия медленне на 30-50%. Это проблема 1С т.к. в любом «нормальном» языке программирования операция установки пометки будет в десятки раз дольше вызова функции. Можно написать что для известного числа уровней цикл быстрее на Х %. Но нужно не забывать о читаемости т.к. на 30000 строк (я просто запустил 10 раз) на моем компе ушло 1,2 сек на рекурсию и 0.89 на циклы.
Опять же если говорить о неизвестном размере дерева (как часто бывает) вопрос открытый.
(72) а есть ли зависимость между количеством уровней дерева и быстодействием, или например между количеством строк и быстродействием ? Тоже вопрос открытый.
(72) пожалуй что наиболее доступное дерево с неизвестным заведомо размером это файловая система
Н-да…. Ну ладно, похоже Вы вдовоем друг друга (YVolohov, Evg-Lylyk) уговорите в верности чего угодно:-))) Ну да ладно…. Если Вам интересно и приятно, то почему бы и нет:-)
(75) Человек старался, тестировал, пришел к определенным выводам, причем достаточно интересным. Почему он не заслуживает плюсика?
(76) Вы в этом плане молодец, я не спорю. Но выводы, т.е. ИМХО, чуть позже и плюс тоже, хорошо? А пока я на море ополоснусться (мне пять минут ходу):-)
(75) Если что то неверно расскажи. А мне плюсов не жалко у меня их много :)))
(68)
> Для деревьев с неизвестным заранее количеством уровней можно только использовать рекурсию.
Автор с упорством, достойным лучшего применения, отрицает очевидное. Приведен же ясный пример в 11 строк обхода произвольного дерева.
+79 О как! Оказывается и в самой статье появился вывод о неизбежности рекурсии. Это уже прямая ложь, заслуживающая жирного минуса…
ТаааАквоооОоот…
(79) (80) Публично покаюсь, если сможешь применить этот код к восьмерочному дереву. Лично у меня не получилось.
(81)К дереву на Лиспе код тоже не применим. Код опровергает утверждение статьи, цитирую
» Подведем итоги. В результате этого небольшого исследования мы выяснили, что рекурсию целесообразно использовать для работы с деревьями, имеющими большое количество уровней вложенности или деревьями, количество уровней вложенности которых не определено. В последнем случае применение рекурсии – ЕДИНСТВЕННО возможный механизм.»
По поводу восьмерки. Вы хотите заявить, что восьмерка не позволяет создать ссылку на элемент (ветку) дерева? Или, что приведенный мной алгоритм неуниверсален (годится не для всяких деревьев)? Или, что дерево в восьмерке не такое как все?
//*******************************************
Процедура Сформировать()
Корень = СоздатьОбъект(«СписокЗначений»);
Ветка1 = СоздатьОбъект(«СписокЗначений»);
Ветка2 = СоздатьОбъект(«СписокЗначений»);
Для Счетчик = 1 По 10 Цикл
Корень.ДобавитьЗначение(1);
Ветка1.ДобавитьЗначение(11);
Ветка2.ДобавитьЗначение(12);
КонецЦикла;
Корень.УстановитьЗначение(4,Ветка1);
Корень.УстановитьЗначение(6,Ветка2);
//Корень — это и есть корень
ТекСписок=СоздатьОбъект(«СписокЗначений»);
СледСписок=СоздатьОбъект(«СписокЗначений»);
ТекСписок.ДобавитьЗначение(Корень);
Пока ТекСписок.РазмерСписка()<>0 Цикл
Для й=1 по ТекСписок.РазмерСписка() Цикл
Ссылка=ТекСписок.ПолучитьЗначение(й);
Если ТипЗначенияСтр(Ссылка)<>»СписокЗначений» Тогда
Сообщить(Строка(Ссылка));
Иначе //Это ветка. Вносим в список след. уровня
СледСписок.ДобавитьЗначение(Ссылка);
КонецЕсли;
КонецЦикла;
ТекСписок=СледСписок;
СледСписок=СоздатьОбъект(«СписокЗначений»);
КонецЦикла;
КонецПроцедуры
Вот твой алгоритм на семерке вместе с небольшим деревом, которое он должен просто обойти. При попытке его использовать компьютер просто зависает. Дерево очень простое — корень и две ветки.
Протестируй сам. Да, еще функцию ДлинаСписка я заменил на РазмерСписка, а то выбрасывало ошибку, а больше я ничего не менял.
(83) Ну, конечно. По Иначе нужно в СледСписок заносить не сам список, а его элементы
Для йй=1 по Ссылка.РазмерСписка() Цикл
СледСписок.ДобавитьЗначение(Ссылка.ПолучитьЗначение(йй));
КонецЦикла;
Прошу пардону. Но минус не сниму.
А вот плюсик за тестирование выдам…
(85) Вот сейчас действительно заработало ))) Дерево обходит полностью, правда порядок обхода несколько другой чем у рекурсии или циклов.
Если корень дерева отметить как 1, подчиненные второго уровня как 11, 12, 13, 14 , третьего уровня 111, 112, 113, 114 и т. д. то цикл или рекурсия обходят так:
1 — 11 — 111 — 112 -113 -114 -12 — 112 — 113 — 114 а этот алгоритм так —
1 — 11 — 12 — 13 — 14 — 111 — 112 -113 — 114 — 121 — 122 — 123 и т.д.
Но это не играет особенной роли, если потомок не должен наследовать каких-либо свойств именно от своего предка. При установке или снятии пометки такого не требуется, поскольку все потомки наследуют свойство (состояние пометки) от общего предка (корня). Так что ты прав — альтернативный рекурсии алгоритм существует.
Сейчас попробую сделать то же для восьмерки.
(87)Ну да, рекурсия по каждой ветке лезет до листьев, а здесь каждый уровень последовательно обходится. Кстати, номер уровня можно фиксировать и записывать свойство, зависящее и от корневого значения, и от номера уровня.
При рекурсии труднее иметь номер уровня под рукой :))
Процедура ИзменитьПометкиПодчиненных(пГлавный)
СтрокиДереваА = Новый Массив;
СтрокиДереваБ = Новый Массив;
СтрокиДереваА.Добавить(пГлавный);
Пока НЕ (СтрокиДереваА.Количество() = 0) Цикл
Для Каждого СтрокаДерева Из СтрокиДереваА Цикл
СтрокаДерева.Пометка = пГлавный.Пометка;
Для Каждого СтрокаДереваПодчиненная из СтрокаДерева.Строки Цикл
СтрокиДереваБ.Добавить(СтрокаДереваПодчиненная);
КонецЦикла;
КонецЦикла;
СтрокиДереваА = СтрокиДереваБ;
СтрокиДереваБ = Новый Массив;
КонецЦикла;
КонецПроцедуры
А вот и код на восьмерке, все работает, проверял. Не знаю только как это будет выглядеть с позиций быстродействия, нужно будет протестировать.
Просто пару уточнений по статье:
«Оба фрагмента кода приведены исключительно для примера. При попытке их выполнить возникнет бесконечный цикл и, как результат, произойдет зависание системы.»
Будет не бесконечный цикл, а бесконечная рекурсия. При бесконеном цикле (ниже пример) — зависания не будет, просто будет крутиться и все, но это не зависание.
Пока 1=1 Цикл
КонецЦикла;
«Рекурсию следует использовать там, где с помощью циклов решить задачу невозможно или нецелесообразно.»
Нет таких задач, чтобы невозможно. А вот целесообразно, пока видел только пример про Ханойские башни.
«Если максимальное количество уровней дерева неизвестно или так велико, что использовать вложенные циклы просто неэффективно, код получиться слишком громоздкий, да еще и повторяющийся?»
Это вроде как понятно, что не сильно уж и громоздкий, а про эффектиность — рекурсия будет всегда затратней по дереву.
Ну и все последующие утверждения, про циклы и их невозможность использовать в дереве или их большую затратность по сравнению с рекурсией в зависимости от глубины и ширины дерева тоже не верно.
А по поводу читабельности и более легкого понимания рекурсии.
Вы пробовали простому пользователю (желательно не шибко умному и не шибко математичному) объяснить циклы, а потом рекурсию? Как думаете, что он быстрее поймет? Да и со студентами также. Циклы сразу понятны, а рекурсия не сразу всем доступна и понятна становится…. Она тяжелей воспринимается в среднем обущающимися, чем понятие цикла…
Ну насчет бесконечного цикла или рекурсии то это не принципиально, можно сказать «бесконечное повторение одного фрагмента кода», суть от этого не меняется.
Зависание или не зависание — тоже непринципиально. В конечном итоге во время выполнения такой программы нельзя будет выполнять другие программы (отчеты, обработки) и вообще что либо делать.
Насчет невозможности решения задачи другим путем — согласен, можно найти и другие варианты. А вот целесообразность уже другое дело, это можно прояснить только тестированием.
Насчет громоздкости кода — попробуйте себе представить код с девятнадцатью вложенными циклами (для обхода двадцатиуровневого дерева).
Насчет большей затратности циклов по сравнению с рекурсией — то я утверждал как раз обратное. Циклы быстрее рекурсии. И если в дереве сто тысяч элементов и скажем всего три уровня то нужно использовать циклы. Скорость выполнения увеличиться и код будет не очень большим.
А вот если в дереве три сотни элементов и двадцать уровней то попробуйте обойти все эти уровни с помощью вложенных циклов. Код будет просто кошмарным а выигрыш в скорости выполнения для дерева с тремястами элементами будет неактуальным, поскольку составит ничтожные доли секунды.
Насчет понимаемости рекурсии то тут я согласен. Циклы понять легче. А вот читабельность кода — другое дело. Сравните размеры последней и предпоследней процедуры в статье.
(92) > Насчет громоздкости кода — попробуйте себе представить код с девятнадцатью вложенными циклами (для обхода двадцатиуровневого дерева).
Вы так и не поняли, что 19-ть вложенных циклов делать не нужно;-)
Остальные Ваши возражения, что принципиально, что нет, по другим уточнениям из поста 91-го тоже вызывают улыбку;-)
Н-да, похоже действительно спорить с Вами бесполезно;-) Сорри, но со статьей не согласен, пока минус…
А я и не говорю что обязательно нужно делать 19 вложенных циклов и что это единственный выход, посмотрите лучше (90). Несколько вложенных циклов это один из выходов, подходящий для деревьев с небольшим количеством уровней и большим количеством элементов.
А улыбка это хорошо, полезно для здоровья. )))
(94)На мой вкус, Вы еще плюс заработали. За то, что спор не перерос в скандал. Вообще-то это подразумевается, но пока, к сожалению, проблематично.
А за статью минус оставляю.
(89) «При рекурсии труднее иметь номер уровня под рукой :))» легко перед вызовом процедуры рекурсии увеличить счетчик и его передать в процедуру… все..
(92) хм… при бесконечном (или непредсказуемо большом) цикле может произойти зависание пргораммы, а при бесконечной рекурсии крах системы.
(101) если мне не изменяет память, то в 1с 8 уровни вложенности рекурсии ограничены…
(0) Плюс не ставлю, так как банально, но и минус тоже, т.к. подробно и встречал 1с прогеров, которые элементарные вещи в программировании не знают.
(108) Статья хороша тем , что позволила выявить позиции участников последующей дискуссии : кто , как и какие аргументы предъявляет.
Что же касается предмета статьи , то подача материала мне понравилась.