Здравствуйте, Iso12, Вы писали:
L>>А можно пример не из учебника или арсенала К.О, а встречающийся в реальной жизни? I>В математических вычислениях часто встречается.
"В математических вычислениях" — это и есть примеры из учебников. Конкретики хочется.
I>Что означает К.О. ?
Ваш капитан Очевидность, вестимо
L>>Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией. I>Если алгоритм с рекурсией самый быстрый и стек позволяет, то его и используйте. Код от этого будет проще и читабельней. Всему своё место. Или вы понимаете слово "Эффетивность" как-то по другому?
Я прошу пример реализуемого через рекурсию алгоритма, который эффективнее реализовать без оной.
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что.
В учебниках для детей, когда описывают рекурсию, всегда начинают с того,
что нужно решить вопрос остановки алгоритма. Возможно он хотел именно такую формулировку?
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как? M>Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны. M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ. M>Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал). M>Я — ок, сравним порядки величин, с разными порядками — сразу не равно, с одним — сравниваем с точностью (имхо, опять же заданной) M>Мне: нет. 10^6 парсек и 10^2 парсек в масштабах вселенной равны (ну или как-то так, я так понял)
Так есть, ТЗ или нет? То его нет, то оказывается что 10^26 * 3 и 10^18 * 3 это равные величины?
M>Ну, и вообще, всё норм с собеседованием?
Очень странное исходя из моего опыта, если не на junior позицию
Здравствуйте, landerhigh, Вы писали:
L>"В математических вычислениях" — это и есть примеры из учебников. Конкретики хочется.
Программируют не только БД, веб странички и т.п. но и математические расчёты и вычисления . Там и встречается.
I>>Если алгоритм с рекурсией самый быстрый и стек позволяет, то его и используйте. Код от этого будет проще и читабельней. Всему своё место. Или вы понимаете слово "Эффетивность" как-то по другому?
L>Я прошу пример реализуемого через рекурсию алгоритма, который эффективнее реализовать без оной.
Я уже выше привёл: если вы напишите мне функцию для расчёта числа Fibonachi, которая рекурсией считает быстрей чем обычным методом, буду вам очень признателен.
Ещё раз повторю свою мысль: расчёт будет выполнятся всегда быстрее, если вычисление необходимого промежуточного результата будет выполняться один раз и сохранятся для использования в других местах расчёта, чем этот промежуточный результат каждый раз в этих местах по новой вычислять.
Здравствуйте, Iso12, Вы писали:
L>>"В математических вычислениях" — это и есть примеры из учебников. Конкретики хочется. I>Программируют не только БД, веб странички и т.п. но и математические расчёты и вычисления . Там и встречается.
Поконкретнее, пожалуйста.
I>Я уже выше привёл: если вы напишите мне функцию для расчёта числа Fibonachi, которая рекурсией считает быстрей чем обычным методом, буду вам очень признателен.
Э нет, это уже демагогия пошла и натягивание совы на глобус. Рекурсивность вовсе не самоцель, а всего лишь инструмент.
Впрочем, на плюсах пожалуйста, как просили. С точки зрения рантайма — однозначно самый быстрый способ
I>Ещё раз повторю свою мысль: расчёт будет выполнятся всегда быстрее, если вычисление необходимого промежуточного результата будет выполняться один раз и сохранятся для использования в других местах расчёта, чем этот промежуточный результат каждый раз в этих местах по новой вычислять.
Pzz>8K — это роскошь. В такой контроллер можно прям настоящую программу затолкать.
Pzz>Мне тут приходилось программировать контроллер, в котором было только 128 байт. Причем когда мы договаривались об этой работе, мне сказали, что их там 256, а я сдуру поверил на слово. А когда вскрылась правда, было поздно что-то менять
Здравствуйте, Marty, Вы писали:
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Как вариант, в том, в стеке будет нужно (размер локальных переменных) x (глубина рекурсии) места, что не всегда оптимально. Скажем, при такой структуре:
int func(int arg)
{
char big_array[1024];
int val;
//compute val using big_array
return func(val)
}
Я не уверен, что оптимизатор догадается освободить место, занятое под big_array перед рекурсивным вызовом. И даже если здесь догадается, то в менее тривиальном примере уже нет.
Но вообще, задача похожа на "угадай, какую страницу задачника экзаменатор прочел за час до собеседования".
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить.
Я обычно всегда начинаю с тривиального варианта, явно проговаривая, что он тривиальный.
Тривиальный вариант — свести все к общему знаменателю каким-нибудь монстроидальным bigint-ом и в лоб сложить. Для 1000 чисел особой разницы не будет. Дальше уже можно рассуждать на тему оптимизации.
M>Ну, и вообще. Резюме моё то ли не читали, то ли все равно надо всё по пунктам пройти — был даден чек-лист из примерно 30 вопросов, по пунктам этого вопросника я письменно отвечал.
Не барское это дело — резюме читать. На самом деле, уже на этом пункте обычно можно разворачиваться. Если собеседующий не нашел времени прочесть ваше резюме, то в найме он явно не заинтересован и собеседование проводит для других целей.
Здравствуйте, opt1k, Вы писали:
O>Ты, мне кажется, излишне паришься. Как по мне, так ты собес прошёл неплохо, собеседующий просто хотел посмотреть как ты мыслишь. Имхо, мыслишь ты нормально. Есть, конечно, вариант, что собеседующий сам не знал ответы на свои вопросы, но я его не учитываю, предполагая что ты собеседовался в приличную компанию.
Спс, ободрил. Контора — , объявление тут нашел, в Питере в офисе в центре сидят несколько человек и всё. Говорят, работают на норвегов, с перспективой командировок и трудоустройства там.
Но, вообще, я когда шел, думал что-то посолиднее будет — пиджачек надел, цивилом прикинулся, папочку для солидности взял А там — по-простецки как-то. Вот думаю, может надо было в свитере и трениках ехать. А то может за мажора халявщика приняли
Здравствуйте, bazis1, Вы писали:
M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. B>Я обычно всегда начинаю с тривиального варианта, явно проговаривая, что он тривиальный. B>Тривиальный вариант — свести все к общему знаменателю каким-нибудь монстроидальным bigint-ом и в лоб сложить. Для 1000 чисел особой разницы не будет. Дальше уже можно рассуждать на тему оптимизации.
На те вопросы, где собесед чего-то еще ждал от меня, кроме того, что я сказал, я отвечал так: "вы похоже ждете от меня чего-то, что я считаю слишком очевидным, и в силу очевидности этих вещей для меня мне даже не приходит мысль об этом что-то говорить"
M>>Ну, и вообще. Резюме моё то ли не читали, то ли все равно надо всё по пунктам пройти — был даден чек-лист из примерно 30 вопросов, по пунктам этого вопросника я письменно отвечал. B>Не барское это дело — резюме читать. На самом деле, уже на этом пункте обычно можно разворачиваться. Если собеседующий не нашел времени прочесть ваше резюме, то в найме он явно не заинтересован и собеседование проводит для других целей.
Ну, пересекалось с резюме там только пара пунктов. Да и резюме я отсылал очень краткое. Но этот момент несколько напряг — можно было эти пункты просто по резюме обсудить, а не напрягать меня писаниной, чтобы потом все равно устно обсуждать
Здравствуйте, Zhendos, Вы писали:
M>>Мне: нет. 10^6 парсек и 10^2 парсек в масштабах вселенной равны (ну или как-то так, я так понял)
Z>Так есть, ТЗ или нет? То его нет, то оказывается что 10^26 * 3 и 10^18 * 3 это равные величины?
Да я и сам не понял
M>>Ну, и вообще, всё норм с собеседованием?
Z>Очень странное исходя из моего опыта, если не на junior позицию
Здравствуйте, Marty, Вы писали:
M>На те вопросы, где собесед чего-то еще ждал от меня, кроме того, что я сказал, я отвечал так: "вы похоже ждете от меня чего-то, что я считаю слишком очевидным, и в силу очевидности этих вещей для меня мне даже не приходит мысль об этом что-то говорить"
Вы некомандный . Так отвечать нельзя ни в коем случае, потому что этот ответ подразумевает, что Вы умнее собеседующего.
Ваша задача на корпоративном собеседовании — показать, что Вы:
а) Глупее собеседующего, смотрите на него снизу вверх и не претендуете на его место
б) Достаточно умны, чтобы выполнять работу, которую ему самому делать западло
Я в эти ворота в свое время головой побился зачетно.
Не хотите играть в этот цирк — качайте язык и ищите удалёнку на Штаты. Удаленщики обычно люди второсортные, но мозги им выносят меньше.
M>Ну, пересекалось с резюме там только пара пунктов. Да и резюме я отсылал очень краткое. Но этот момент несколько напряг — можно было эти пункты просто по резюме обсудить, а не напрягать меня писаниной, чтобы потом все равно устно обсуждать
Писанина нужна для отчетности. Вам же сороковник скоро, а Вы все как маленький
Здравствуйте, bazis1, Вы писали:
M>>На те вопросы, где собесед чего-то еще ждал от меня, кроме того, что я сказал, я отвечал так: "вы похоже ждете от меня чего-то, что я считаю слишком очевидным, и в силу очевидности этих вещей для меня мне даже не приходит мысль об этом что-то говорить" B>Вы некомандный . Так отвечать нельзя ни в коем случае, потому что этот ответ подразумевает, что Вы умнее собеседующего.
А как правильно отвечать? Чтобы и валенком прикинуться, и не совсем уж валенком?
L>>>"В математических вычислениях" — это и есть примеры из учебников. Конкретики хочется. I>>Программируют не только БД, веб странички и т.п. но и математические расчёты и вычисления . Там и встречается.
L>Поконкретнее, пожалуйста.
ну куда уж конкретнее.
I>>Я уже выше привёл: если вы напишите мне функцию для расчёта числа Fibonachi, которая рекурсией считает быстрей чем обычным методом, буду вам очень признателен.
L>Э нет, это уже демагогия пошла и натягивание совы на глобус. Рекурсивность вовсе не самоцель, а всего лишь инструмент. L>Впрочем, на плюсах пожалуйста, как просили. С точки зрения рантайма — однозначно самый быстрый способ
Какая тут демагогия? Конкретная задача, требуется найти решение. Ваш пример это совсем не то, что я просил.
Я вам и том и толкую, что рекурсия это лишь иструмент, и применять его надо, где он подходит.
I>>Ещё раз повторю свою мысль: расчёт будет выполнятся всегда быстрее, если вычисление необходимого промежуточного результата будет выполняться один раз и сохранятся для использования в других местах расчёта, чем этот промежуточный результат каждый раз в этих местах по новой вычислять.
L>Спасибо, кэп. Только при чем тут рекурсия?
При рекурсии в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.
Re[10]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, Iso12, Вы писали:
L>>Спасибо, кэп. Только при чем тут рекурсия? I>При рекурсии в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.
Бред, дело не в рекурсии, а в алгоритме. Без рекурсии тоже можно тупой алгоритм написать. А вот рекурсия без "промежуточных" результатов:
int fib(int term, int val = 1, int prev = 0)
{
if(term == 0) return prev;
if(term == 1) return val;
return fib(term - 1, val+prev, val);
}
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[10]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, Iso12, Вы писали:
I>ну куда уж конкретнее.
Ну, конкретики не будет, значит.
L>>Э нет, это уже демагогия пошла и натягивание совы на глобус. Рекурсивность вовсе не самоцель, а всего лишь инструмент. L>>Впрочем, на плюсах пожалуйста, как просили. С точки зрения рантайма — однозначно самый быстрый способ I>Какая тут демагогия? Конкретная задача, требуется найти решение. Ваш пример это совсем не то, что я просил.
Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается.
I>Я вам и том и толкую, что рекурсия это лишь иструмент, и применять его надо, где он подходит.
Вот только не надо с умным видом декламировать прописные истины. Это не чат детского сада. И это не имеет никакого отношения к изначальной теме.
L>>Спасибо, кэп. Только при чем тут рекурсия? I>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.
Здравствуйте, ·, Вы писали:
·>Без рекурсии тоже можно тупой алгоритм написать.
Мне кажется, что это сложнее, чем привести тупой рекурсивный к хвостовой оптимизации.
Можно, конечно, взять тупой рекурсивный и проэмулировать рекурсивный вызов стеком, но интересно именно "тупой алгоритм" написать с нуля. Пока не вышло.
Здравствуйте, samius, Вы писали:
S>·>Без рекурсии тоже можно тупой алгоритм написать. S>Мне кажется, что это сложнее, чем привести тупой рекурсивный к хвостовой оптимизации. S>Можно, конечно, взять тупой рекурсивный и проэмулировать рекурсивный вызов стеком, но интересно именно "тупой алгоритм" написать с нуля. Пока не вышло.
Вполне возможно, что для конкретной задачи, типа Фиббоначчи оно и правда, что многие могут сходу написать только эффективный цикл, но затрудняются с рекурсией, но это не является каким-то доказательством того, что "рекурсия медленнее" и т.п.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, ·, Вы писали:
·>Вполне возможно, что для конкретной задачи, типа Фиббоначчи оно и правда, что многие могут сходу написать только эффективный цикл,
Все же за требование "написать сходу" нужно гнать ссаными тряпками из профессии и лишать ученой степени/диплома.
Реализации алгоритмов либо берутся библиотечные, либо обязаны быть продуманными, просчтитанными и протестированными.
Здравствуйте, Marty, Вы писали:
M> Здравствуйте!
M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
M>Интересует, что в пп 1-2 я не понял?
M>Ну, и вообще, всё норм с собеседованием?
По 1) — подумалось — может от тебя нечто про мемоизацию услышать ждали? В рекурсивных реализациях алгоритмов часто приходится вычислять одно и то же много раз и с этим иногда как-то бороться надо.
Здравствуйте, landerhigh, Вы писали:
L>Здравствуйте, ·, Вы писали:
L>·>Вполне возможно, что для конкретной задачи, типа Фиббоначчи оно и правда, что многие могут сходу написать только эффективный цикл,
L>Все же за требование "написать сходу" нужно гнать ссаными тряпками из профессии и лишать ученой степени/диплома.
Не было требования "написать сходу". Это я написал что у меня не получилось написать с нуля тупую неэффективную реализацию Фибоначчи, не используюя при этом рекурсию.
) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны.
, объявление тут нашел, в Питере в офисе в центре сидят несколько человек и всё. Говорят, работают на норвегов, с перспективой командировок и трудоустройства там.
. Так отвечать нельзя ни в коем случае, потому что этот ответ подразумевает, что Вы умнее собеседующего.
