Здравствуйте, landerhigh, Вы писали:
L>Да нет, как раз доказывает. Что при должном рвении и черное можно белым назвать.
Черное всегда можно назвать белым. Тут доказательств не надо
Именно поэтому в этой ветке код и выкладывался, чтобы желающие могли у себя запустить и сравнить цифры.
А цифры они ни белые, ни черные.
L>Нет, это констатация приведенного "примера", в котором применение рекурсии как минимум бессмысленно.
Так что хватит уже воду бездоказательно лить. "как минимум бессмысленно"... железный аргумент.
Конкретно эти две реализации — одна не лучше и не хуже другой.
: "Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией."
А тут уже пишется, что в моем примере рекурсия бессмысленна. Выходит, что итерация ок
Т.е. ты в блокнотике уже записал мою итеративную реализацию обхода LinkedList<int>?
L>И бессмысленнее тоже некуда
Хороший подход: нечего возразить по существу, назови задачу бессмысленной.
SL>>Буду рад хоть какому-то подтверждению указанных слов.
L>Каких именно?
1. Было написано, что в моем исходном примере разница в производительности объясняется тем, "что при должном рвении все, что угодно можно сделать через одно место".
В примере кода мало. Думаю, не составит труда сделать все через "правильное место". Верно же?
2. Было предложение "попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно."
Кода как не было, так и нет
Время идет, а мы так и не узнали, что такое "полноценное дерево" и на сколько оно полноценнее LinkedList<int>.
L>Так вот это я тебе предлагаю. Простейшая задача — есть дерево. С ветками и листьями. Обойти depth first. Или width first. Рекурсивно. А потом итеративно. Сравнить производительность. И накладные расходы. Сделать вывод о применимости рекурсивных алгоритмах и их преимуществах (и недостатках).
Код кинешь?
У тебя в подписи ссылка на сайт www.blinnov.com
Статьи с тегом ".Net" там есть. Я же правильно полагаю, что можно ожидать от автора этого сайта владения навыками разработки на платформе .Net?
L>Да, а змея — это частный случай крокодила.
Да ради бога! Мне не жалко
Re[14]: Вопросы на собеседовании (в очередной раз)
SL>Так что хватит уже воду бездоказательно лить. "как минимум бессмысленно"... железный аргумент. SL>Конкретно эти две реализации — одна не лучше и не хуже другой.
: "Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией." SL>А тут уже пишется, что в моем примере рекурсия бессмысленна. Выходит, что итерация ок SL>Т.е. ты в блокнотике уже записал мою итеративную реализацию обхода LinkedList<int>?
Записал, конечно. Только в другой блокнотик.
L>>И бессмысленнее тоже некуда SL>Хороший подход: нечего возразить по существу, назови задачу бессмысленной.
По существу — рекурсивное сложение элементов списка как минимум бессмысленно. А как максимум <догадаться факультативно>.
L>>Так вот это я тебе предлагаю. Простейшая задача — есть дерево. С ветками и листьями. Обойти depth first. Или width first. Рекурсивно. А потом итеративно. Сравнить производительность. И накладные расходы. Сделать вывод о применимости рекурсивных алгоритмах и их преимуществах (и недостатках). SL>Код кинешь?
Берешь первый попавшийся стек протокола, основанного на ASN.1, смотришь. А троллям я не подаю. С аргументом "список — тоже дерево" спорить сложно.
Здравствуйте, landerhigh, Вы писали:
L>Одна таки хуже. Почему, сам догадаешься?
Пожалуй, я останусь при своем мнении: они одинаковы.
L>По существу — рекурсивное сложение элементов списка как минимум бессмысленно. А как максимум <догадаться факультативно>.
Есть задача: вернуть сумму чисел из списка.
Есть две реализации алгоритма, которые работают за одинаковое время. Размер кода сопоставим.
Не вижу ни одной причины отдавать предпочтение какому-либо варианту.
L>Берешь первый попавшийся стек протокола, основанного на ASN.1, смотришь.
Так твое предложение, возьми и реализуй Чего на других спихивать свои "гениальные задумки"?
L>А троллям я не подаю.
Подавать мне не надо. Да тебе пока и нечего
L>С аргументом "список — тоже дерево" спорить сложно.
Это не аргумент. Это факт.
А пример работы с "полноценным" деревом ты предложил реализовать, но почему-то сам не стал.
Похоже, так мы и не узнаем, что же это за "полноценное" дерево... И действительно ли оно "полноценнее" обычного двусвязного списка.
PS А за предложение огромное спасибо! Даже не знаю, чтобы я без него делал
Здравствуйте, landerhigh, Вы писали:
L>На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно. L>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью
Он хотел услышать о многоэтажных стектрейсах в, казлаось бы, линейном коде.
L>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял". L>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z. L>Ну и на самом деле все правильно ты сказал про физическое значение. Гораздо чаще встречаются факапы, вызванные тем, что плавающую точку применяют там, где ее нельзя применять, нежели интересности со сложением/вычитанием.
Тут задача явно на умение считать погрешности вычислений. Это примерно как считать сложности алгоритмов, но только для погрешностей. Я думаю тут просто какая-нибудь специфическая вакансия, для которой это нужно понимать. Тут нужно сложить числа в массиве и получить 2 числа, результат и погрешность (которая зависит от данных), а потом уже сравнивать.
Re[13]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, DreamMaker, Вы писали:
DM>Здравствуйте, samius, Вы писали:
SL>>>Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример. S>>А разве есть другие?
DM>разумеется есть.
Раз есть, так где же они?
DM>попробуйте запрограммировать, например, такую незатейливую целочисленную функцию:
DM>A(m,n) = DM> n+1, если m==0 DM> A(m-1, 1), если m>0, n==0 DM> A(m-1, A(m,n-1)), если m>0, n>0
Попробовал
let rec A m n cont =
match m, n with
| 0, _-> n + 1 |> cont
| _, 0 when m > 0 -> A (m-1) 1 cont
| _, _ when m > 0 && n > 0 ->
A m (n-1) (fun x -> A (m-1) x cont)
| _, _ -> failwith ""
DM>...и посчитать, например, А(4,4)... если, конечно, ваш комп и компилятор не треснут
треснуть вряд ли им грозит. tail-call стек не жрет. Но времени таки жалко.
А с вас алгоритм, не сводящийся к tail-call.
Re[15]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, samius, Вы писали:
DM>>разумеется есть. S>Раз есть, так где же они?
в учебниках по CS. классический пример я привел.
S>Попробовал
если б это было собеседование, то вы его провалили.
DM>>...и посчитать, например, А(4,4)... если, конечно, ваш комп и компилятор не треснут S>треснуть вряд ли им грозит. tail-call стек не жрет. Но времени таки жалко.
ну-ну..
приведенная ф-ция не является примитивно рекурсивной со всеми вытекающими отсюда следствиями.
ее не получится сделать хвостовой (с константной памятью, разумеется).
и А(4,4) посчитать в лоб тоже не получится. потому как битиков в этом незатейлевом числе больше чем элементарных частиц во вселенной.
In P=NP we trust.
Re[16]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, DreamMaker, Вы писали:
DM>Здравствуйте, samius, Вы писали:
DM>>>разумеется есть. S>>Раз есть, так где же они?
DM>в учебниках по CS. классический пример я привел.
А я привел классический контрпример.
S>>Попробовал
DM>если б это было собеседование, то вы его провалили.
Конечно. Ведь я сделал то, в чем собеседующий уверен что такое сделать нельзя.
DM>>>...и посчитать, например, А(4,4)... если, конечно, ваш комп и компилятор не треснут S>>треснуть вряд ли им грозит. tail-call стек не жрет. Но времени таки жалко.
DM>ну-ну..
DM>приведенная ф-ция не является примитивно рекурсивной со всеми вытекающими отсюда следствиями. DM>ее не получится сделать хвостовой (с константной памятью, разумеется).
Разумеется, условие про константную память вы упомянули после того, как я свел функцию к tail-call.
DM>и А(4,4) посчитать в лоб тоже не получится. потому как битиков в этом незатейлевом числе больше чем элементарных частиц во вселенной.
Ну так а тут никто и не говорил что tail-call посчитает все что даже нельзя посчитать.
Re[17]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, DreamMaker, Вы писали:
DM>Здравствуйте, samius, Вы писали:
DM>>>в учебниках по CS. классический пример я привел. S>>А я привел классический контрпример.
DM>только он неверный
В чем неверный?
DM>читайте учебники
Тут вилка. Либо вы сами что-то не то поняли в учебнике, тогда читайте снова.
Либо учебник отвергает возможность построения SSA формы, используемой компиляторами. Тогда такой учебник вряд ли достоин внимания в этом вопросе.
В любом случае будет любопытно взглянуть. Не подскажете название?
