Re[13]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 12.04.17 21:27
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Да нет, как раз доказывает. Что при должном рвении и черное можно белым назвать.


Черное всегда можно назвать белым. Тут доказательств не надо

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

L>Нет, это констатация приведенного "примера", в котором применение рекурсии как минимум бессмысленно.


Я напомню. По результатам испытаний они одинаковы, по 17 ms: http://rsdn.org/forum/job/6753349.1
Автор: samius
Дата: 10.04.17

Так что хватит уже воду бездоказательно лить. "как минимум бессмысленно"... железный аргумент.
Конкретно эти две реализации — одна не лучше и не хуже другой.

И второе.
Тут я совсем в непонятках.
Сообщение http://rsdn.org/forum/job/6750431.1
Автор: landerhigh
Дата: 07.04.17
: "Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией."
А тут уже пишется, что в моем примере рекурсия бессмысленна. Выходит, что итерация ок
Т.е. ты в блокнотике уже записал мою итеративную реализацию обхода LinkedList<int>?

L>И бессмысленнее тоже некуда


Хороший подход: нечего возразить по существу, назови задачу бессмысленной.


SL>>Буду рад хоть какому-то подтверждению указанных слов.


L>Каких именно?


1. Было написано, что в моем исходном примере разница в производительности объясняется тем, "что при должном рвении все, что угодно можно сделать через одно место".
В примере кода мало. Думаю, не составит труда сделать все через "правильное место". Верно же?
2. Было предложение "попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно."
Кода как не было, так и нет
Время идет, а мы так и не узнали, что такое "полноценное дерево" и на сколько оно полноценнее LinkedList<int>.

L>Так вот это я тебе предлагаю. Простейшая задача — есть дерево. С ветками и листьями. Обойти depth first. Или width first. Рекурсивно. А потом итеративно. Сравнить производительность. И накладные расходы. Сделать вывод о применимости рекурсивных алгоритмах и их преимуществах (и недостатках).


Код кинешь?

У тебя в подписи ссылка на сайт www.blinnov.com
Статьи с тегом ".Net" там есть. Я же правильно полагаю, что можно ожидать от автора этого сайта владения навыками разработки на платформе .Net?

L>Да, а змея — это частный случай крокодила.


Да ради бога! Мне не жалко
Re[14]: Вопросы на собеседовании (в очередной раз)
От: landerhigh Пират http://www.blinnov.com
Дата: 12.04.17 22:03
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Я напомню. По результатам испытаний они одинаковы, по 17 ms: http://rsdn.org/forum/job/6753349.1
Автор: samius
Дата: 10.04.17

SL>Так что хватит уже воду бездоказательно лить. "как минимум бессмысленно"... железный аргумент.
SL>Конкретно эти две реализации — одна не лучше и не хуже другой.

Одна таки хуже. Почему, сам догадаешься?

SL>Сообщение http://rsdn.org/forum/job/6750431.1
Автор: landerhigh
Дата: 07.04.17
: "Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией."

SL>А тут уже пишется, что в моем примере рекурсия бессмысленна. Выходит, что итерация ок
SL>Т.е. ты в блокнотике уже записал мою итеративную реализацию обхода LinkedList<int>?

Записал, конечно. Только в другой блокнотик.

L>>И бессмысленнее тоже некуда

SL>Хороший подход: нечего возразить по существу, назови задачу бессмысленной.

По существу — рекурсивное сложение элементов списка как минимум бессмысленно. А как максимум <догадаться факультативно>.

L>>Так вот это я тебе предлагаю. Простейшая задача — есть дерево. С ветками и листьями. Обойти depth first. Или width first. Рекурсивно. А потом итеративно. Сравнить производительность. И накладные расходы. Сделать вывод о применимости рекурсивных алгоритмах и их преимуществах (и недостатках).

SL>Код кинешь?

Берешь первый попавшийся стек протокола, основанного на ASN.1, смотришь. А троллям я не подаю. С аргументом "список — тоже дерево" спорить сложно.
www.blinnov.com
Re[15]: Вопросы на собеседовании (в очередной раз)
От: StatujaLeha на правах ИМХО
Дата: 13.04.17 18:28
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>Одна таки хуже. Почему, сам догадаешься?


Пожалуй, я останусь при своем мнении: они одинаковы.

L>По существу — рекурсивное сложение элементов списка как минимум бессмысленно. А как максимум <догадаться факультативно>.


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

L>Берешь первый попавшийся стек протокола, основанного на ASN.1, смотришь.


Так твое предложение, возьми и реализуй Чего на других спихивать свои "гениальные задумки"?

L>А троллям я не подаю.


Подавать мне не надо. Да тебе пока и нечего

L>С аргументом "список — тоже дерево" спорить сложно.


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

PS А за предложение огромное спасибо! Даже не знаю, чтобы я без него делал
Re: Вопросы на собеседовании (в очередной раз)
От: borya_ilin  
Дата: 14.04.17 08:31
Оценка:
числа сравнивать так:
if (fabs(a - b) <= DBL_EPSILON * fmax(fabs(a), fabs(b))) {
  // будем считать равны
}

суммировать алгоритмом Кэхэна

про рекурсию не знаю какие там проблемы кроме стека
Re[2]: Вопросы на собеседовании (в очередной раз)
От: chaotic-kotik  
Дата: 22.04.17 07:21
Оценка:
Здравствуйте, landerhigh, Вы писали:

L>На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно.

L>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью

Он хотел услышать о многоэтажных стектрейсах в, казлаось бы, линейном коде.

L>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял".

L>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
L>Ну и на самом деле все правильно ты сказал про физическое значение. Гораздо чаще встречаются факапы, вызванные тем, что плавающую точку применяют там, где ее нельзя применять, нежели интересности со сложением/вычитанием.

Тут задача явно на умение считать погрешности вычислений. Это примерно как считать сложности алгоритмов, но только для погрешностей. Я думаю тут просто какая-нибудь специфическая вакансия, для которой это нужно понимать. Тут нужно сложить числа в массиве и получить 2 числа, результат и погрешность (которая зависит от данных), а потом уже сравнивать.
Re[13]: Вопросы на собеседовании (в очередной раз)
От: DreamMaker  
Дата: 24.04.17 05:29
Оценка:
Здравствуйте, samius, Вы писали:

SL>>Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример.

S>А разве есть другие?


разумеется есть.
попробуйте запрограммировать, например, такую незатейливую целочисленную функцию:

A(m,n) =
n+1, если m==0
A(m-1, 1), если m>0, n==0
A(m-1, A(m,n-1)), если m>0, n>0

...и посчитать, например, А(4,4)... если, конечно, ваш комп и компилятор не треснут


нормальный вопрос для собеседования — что это за функция? для джедаев: таки посчитать А(4,4)
In P=NP we trust.
Re[14]: Вопросы на собеседовании (в очередной раз)
От: samius Россия http://sams-tricks.blogspot.com
Дата: 24.04.17 07:24
Оценка:
Здравствуйте, 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]: Вопросы на собеседовании (в очередной раз)
От: DreamMaker  
Дата: 24.04.17 13:57
Оценка: -1
Здравствуйте, samius, Вы писали:

DM>>разумеется есть.

S>Раз есть, так где же они?

в учебниках по CS. классический пример я привел.

S>Попробовал


если б это было собеседование, то вы его провалили.


DM>>...и посчитать, например, А(4,4)... если, конечно, ваш комп и компилятор не треснут

S>треснуть вряд ли им грозит. tail-call стек не жрет. Но времени таки жалко.

ну-ну..

приведенная ф-ция не является примитивно рекурсивной со всеми вытекающими отсюда следствиями.
ее не получится сделать хвостовой (с константной памятью, разумеется).
и А(4,4) посчитать в лоб тоже не получится. потому как битиков в этом незатейлевом числе больше чем элементарных частиц во вселенной.
In P=NP we trust.
Re[16]: Вопросы на собеседовании (в очередной раз)
От: samius Россия http://sams-tricks.blogspot.com
Дата: 24.04.17 15:02
Оценка:
Здравствуйте, 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  
Дата: 26.04.17 13:39
Оценка:
Здравствуйте, samius, Вы писали:


DM>>в учебниках по CS. классический пример я привел.

S>А я привел классический контрпример.

только он неверный

читайте учебники
In P=NP we trust.
Re[18]: Вопросы на собеседовании (в очередной раз)
От: samius Россия http://sams-tricks.blogspot.com
Дата: 26.04.17 14:42
Оценка:
Здравствуйте, DreamMaker, Вы писали:

DM>Здравствуйте, samius, Вы писали:



DM>>>в учебниках по CS. классический пример я привел.

S>>А я привел классический контрпример.

DM>только он неверный

В чем неверный?

DM>читайте учебники

Тут вилка. Либо вы сами что-то не то поняли в учебнике, тогда читайте снова.
Либо учебник отвергает возможность построения SSA формы, используемой компиляторами. Тогда такой учебник вряд ли достоин внимания в этом вопросе.
В любом случае будет любопытно взглянуть. Не подскажете название?
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.