Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.
1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны.
Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.
Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал).
Я — ок, сравним порядки величин, с разными порядками — сразу не равно, с одним — сравниваем с точностью (имхо, опять же заданной)
Мне: нет. 10^6 парсек и 10^2 парсек в масштабах вселенной равны (ну или как-то так, я так понял)
Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?
Мне: Нет, и так много времени потратили.
Ну, то что я не большой специалист в вопросах численных расчетов с использованием чисел с плавающей точкой с мантиссой фиксированной размерности я и так знал. Но я лично не вижу большой проблемы в этом — вопрос недели, может двух, чтобы изучить вопрос.
Ну, и вообще. Резюме моё то ли не читали, то ли все равно надо всё по пунктам пройти — был даден чек-лист из примерно 30 вопросов, по пунктам этого вопросника я письменно отвечал. Гномиков не было, но была задача — написать программу подсчета количества слов в строке и букв 'B'. На бумажке, само собой Написал. Даже наверно скомпилировалось бы и работало
Еще устный экзамен по английскому тоже похоже провалил (птсьменный вроде сдал), но там мы вместе с собеседом поржали с моего английского
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"
Как много веселых ребят, и все делают велосипед...
Здравствуйте, ononim, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию O>Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"
Здравствуйте, Marty, Вы писали:
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно.
Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью
M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.
Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял".
Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
Ну и на самом деле все правильно ты сказал про физическое значение. Гораздо чаще встречаются факапы, вызванные тем, что плавающую точку применяют там, где ее нельзя применять, нежели интересности со сложением/вычитанием.
M>Мне говорят: физического значения нет. M>10^6 парсек и 10^2 парсек
Сами не знают, чего хотят. Использовать плавающую точку, чтобы хранить парсеки? О. майн. готт.
Здравствуйте, Marty, Вы писали:
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Имхо, глубина рекурсии — это основная потенциальная проблема. Честно погугил что еще подразумевают под проблемами — нашел вот это — т.е. по сути речь о повторном вычислении уже ранее вычисленного (решение — кэширование), но назвать это проблемой рекурсии хз, да и далеко не всегда рекурсия это вычисления.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
.. M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ. M>Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал).
Т.е. подразумевается речь о вещественных числах — возможно хотел услышать о константах epsilon — C++, DBL_EPSILON и проч. — Cи
L>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял". L>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?
Как много веселых ребят, и все делают велосипед...
Здравствуйте, landerhigh, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
L>На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно. L>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью
Да и проблемой рекурсивно использовать не-реентерабельную функцию имхо нельзя назвать, это просто ошибка.
Здравствуйте, std.denis, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
SD>может про проблемы распараллеливания рекурсивных алгоритмов?
M>>delta = a — b < epsilon, то равны.
SD>модуль забыл :P
Можно поподробнее?
Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался
Здравствуйте, pilgrim_, Вы писали:
_>Т.е. подразумевается речь о вещественных числах — возможно хотел услышать о константах epsilon — C++, DBL_EPSILON и проч. — Cи
Тоже подумал про машинное эпсилон, числа считаются равными в данной архитектуре, если |a-b|<eps. Вычисляется обычно итеративно, эпсилон делится на два, пока результат суммы 1+eps еще больше 1.
M> Здравствуйте!
M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как? M>Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны. M>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ. M>Мне говорят: физического значения нет. Нужно сравнить (видимо максимально точно, но не точнее, чем возможно — это я уже потом додумал). M>Я — ок, сравним порядки величин, с разными порядками — сразу не равно, с одним — сравниваем с точностью (имхо, опять же заданной) M>Мне: нет. 10^6 парсек и 10^2 парсек в масштабах вселенной равны (ну или как-то так, я так понял) M>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос? M>Мне: Нет, и так много времени потратили.
M>Ну, то что я не большой специалист в вопросах численных расчетов с использованием чисел с плавающей точкой с мантиссой фиксированной размерности я и так знал. Но я лично не вижу большой проблемы в этом — вопрос недели, может двух, чтобы изучить вопрос.
M>Ну, и вообще. Резюме моё то ли не читали, то ли все равно надо всё по пунктам пройти — был даден чек-лист из примерно 30 вопросов, по пунктам этого вопросника я письменно отвечал. Гномиков не было, но была задача — написать программу подсчета количества слов в строке и букв 'B'. На бумажке, само собой Написал. Даже наверно скомпилировалось бы и работало
M>Еще устный экзамен по английскому тоже похоже провалил (птсьменный вроде сдал), но там мы вместе с собеседом поржали с моего английского
M>Интересует, что в пп 1-2 я не понял? M>Ну, и вообще, всё норм с собеседованием?
На счет 2 — от тебя наверное хотели услышать, что полученная погрешность будет в худшем случае пропорциональна количеству элементов в суммах. Ну и за оценку epsilon при сравнении можно грубо взять половину младшего разряда мантиссы суммы, умноженную на n — количество эл-тов в массиве.
Здравствуйте, pilgrim_, Вы писали:
L>>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью _>Да и проблемой рекурсивно использовать не-реентерабельную функцию имхо нельзя назвать, это просто ошибка.
Случается, что собеседователи ожидают, что ответ будет совпадать с вычитанным в учебнике.
Здравствуйте, landerhigh, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
L>На ум приходит разве что не-реентрабельность функции, которую пытаются вызывать рекурсивно. L>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью
Да, это может быть. Не помню, по этому или по другому вопросу, я спросил — возможно вы что-то хотите услышать от меня то, что я считаю подразумевающимся, и просто не рассматриваю, и потому не понимаю, что еще вы хотите от меня услышать. Ну или как-то так
M>>Доп. вопрос: как выбрать epsilon? Я: нужно отталкиваться от физического значения величин и ТЗ.
L>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял". L>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z.
Ну да, о таких ловушках я в курсе. Наверно надо было разобраться, почему именно сумма, а не просто два с потолка взятых числа.
L>Ну и на самом деле все правильно ты сказал про физическое значение. Гораздо чаще встречаются факапы, вызванные тем, что плавающую точку применяют там, где ее нельзя применять, нежели интересности со сложением/вычитанием.
M>>Мне говорят: физического значения нет. M>>10^6 парсек и 10^2 парсек
L>Сами не знают, чего хотят. Использовать плавающую точку, чтобы хранить парсеки? О. майн. готт.
Здравствуйте, ononim, Вы писали:
O>Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?
Для начала нужно все же с физическим смыслом величин определиться, чтобы не решать несуществующую задачу. А в принципе, наверное, так и поступают. Мне не приходилось это сакральное знание применять на практике.
Здравствуйте, Marty, Вы писали:
M>Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался
Неделя? Если привык писать юнит-тесты, то достаточно знания, что из используемого представления вещественных чисел вытекают забавные вещи, чтобы очень быстро разобраться на примерах и подкрепить результат теорией. Ну или наоборот.
Здравствуйте, Marty, Вы писали:
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что.
Ну, может быть, надо было еще брякнуть что-нибудь про скорость исполнения, что рекурсивная версия скорее всего будет медленнее итеративной.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Надо было переспросить его о каких числах идет речь, целых или с плавающей точкой. Может быть имелись ввиду целые числа, а вы свернули на плавающую точку.
M>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос? M>Мне: Нет, и так много времени потратили.
Бегите от них.
Здравствуйте, std.denis, Вы писали:
M>>>>delta = a — b < epsilon, то равны. SD>>>модуль забыл :P M>>Можно поподробнее?
SD>ну обычный модуль же, чтобы знак отбросить: |a — b| < epsilon
Обычный модуль — это из разряда того, что просто подразумевается Я думаю, копать надо глубже
Здравствуйте, landerhigh, Вы писали:
M>>Я просто только краем уха где-то когда-то слышал о методах работы с числами с плавающей точкой, да и то уже позабыл. Я в этом проблемы не вижу, если уточнили бы проблему, за пару дней, ну, ок, за неделю, ну, с перекурами, то за две (если с помошниками — ну за месяц) бы разобрался
L>Неделя? Если привык писать юнит-тесты, то достаточно знания, что из используемого представления вещественных чисел вытекают забавные вещи, чтобы очень быстро разобраться на примерах и подкрепить результат теорией. Ну или наоборот.
А-ха-ха. Кто о чем, а ты о юнит тестах. А я — о сроках. Жизнь научила, что лучше срок поставить долгий, а потом перевыполнить и сделать быстрее, чем малый, а потом оправдываться о его несоблюдении
Здравствуйте, cserg, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. C>Ну, может быть, надо было еще брякнуть что-нибудь про скорость исполнения, что рекурсивная версия скорее всего будет медленнее итеративной.
Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут
M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как? C>Надо было переспросить его о каких числах идет речь, целых или с плавающей точкой. Может быть имелись ввиду целые числа, а вы свернули на плавающую точку.
С плавающей, с ней, родимой.
M>>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос? M>>Мне: Нет, и так много времени потратили. C>Бегите от них.
Денег вроде дают. Не так что бы очень, но некоторые перспективы есть.
Здравствуйте, ononim, Вы писали:
L>>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял". L>>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z. O>Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?
С массивами — проблема — когда я хотел поговорить о них, мне говорили, что есть два числа для сравнения, и только.
Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы
Здравствуйте, landerhigh, Вы писали:
L>>>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью _>>Да и проблемой рекурсивно использовать не-реентерабельную функцию имхо нельзя назвать, это просто ошибка.
L>Случается, что собеседователи ожидают, что ответ будет совпадать с вычитанным в учебнике.
Собеседователь вроде был адекватен, не тупил на моих ответах. Хотя, может он просто скипал незнакомое?
Здравствуйте, Marty, Вы писали:
M>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут
Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.
Здравствуйте, cserg, Вы писали:
M>>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут C>Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.
Зато место на стеке бесплатное. Не надо ничего в куче выделять
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
В такой формулировке вопрос странный. Точно также можно было бы спросить, какие проблемы могут быть при цикле while? Да какие угодно из-за кривости рук разработчика. Про рекурсию я бы ответил, что идеологически, алгоритм с использованием рекурсии должен быть глубиной O(log(n)). Т.е. все возможные алгоритмы devide & concure. И это правило не стоит нарушать. Например, считать факториал рекурсией — бред. Если правило не нарушено, то единственная проблема — иногда неудобно дебажить рекурсивные функции.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Думаю, что этот вопрос нормальный только есть в компании надо будет заниматься графикой или подобным. Во всех остальных случаях вопрос непонятно зачем задавался. Я бы ответил, что просто чисел не бывает. В зависимости от реальной решаемой проблемы числа могут быть натуральными, целыми, рациональными, вещественными и тд. В зависимости от требуемой точности и особенностей работы с ними могут быть и разные представления чисел в системе. Например, в некоторых случаях, можно вообще хранить числа в виде отдельного числителя и отдельного знаменателя. Тогда нет никакой проблемы сравнить суммы двух наборов этих чисел.
Ты, мне кажется, излишне паришься. Как по мне, так ты собес прошёл неплохо, собеседующий просто хотел посмотреть как ты мыслишь. Имхо, мыслишь ты нормально. Есть, конечно, вариант, что собеседующий сам не знал ответы на свои вопросы, но я его не учитываю, предполагая что ты собеседовался в приличную компанию.
Здравствуйте, Marty, Вы писали:
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Проблемы если не выполняется условие выхода из рекурсии (вообще или очень долго) или получается слишком глубокий стек. Всякая нереентерабельность — это не про рекурсию, это другое (например, обработчик прерывания — там рекурсией и не пахнет).
Вообще, вопрос странный. Я б давал куски хорошего и плохого кода и просил сказать какой хороший и какой плохой, а перечислять какие бывают проблемы вообще — это уже какое то поле чудес с Якубовичем, угадывать надо.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как? M>Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны.
Если числа суммированы до тебя и тебе дают только a и b — то их и сравнивай через ">" Очень странный вопрос в такой формулировке. Меня обычно спрашивали как суммировать чтоб потерять по дороге по-меньше — типа сначала отсортировать по возрастанию, и суммировать от меньших к большим, а тут —
Здравствуйте, Marty, Вы писали:
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Здравствуйте, Marty, Вы писали:
M>>>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут C>>Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.
M>Зато место на стеке бесплатное. Не надо ничего в куче выделять
Можно пример кода с рекурсией, где за счёт этого будет экономия.
Здравствуйте, Marty, Вы писали:
O>>Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл? M>С массивами — проблема — когда я хотел поговорить о них, мне говорили, что есть два числа для сравнения, и только. M>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы
Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?..
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, ononim, Вы писали:
O>Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"
По-моему, такого уже не бывает. Под стек просто резервируется сколько-то. Например, в ядре линукса под стек выделено 4К, куда уж меньше. Конечно, при программировании надо это учитывать, и не заводить на стеке больших массивов и структур.
Здравствуйте, Marty, Вы писали:
L>>Неделя? Если привык писать юнит-тесты, то достаточно знания, что из используемого представления вещественных чисел вытекают забавные вещи, чтобы очень быстро разобраться на примерах и подкрепить результат теорией. Ну или наоборот. M>А-ха-ха. Кто о чем, а ты о юнит тестах. А я — о сроках. Жизнь научила, что лучше срок поставить долгий, а потом перевыполнить и сделать быстрее, чем малый, а потом оправдываться о его несоблюдении
А меня жизнь научила не ставить сроки от балды, ни маленькие, ни большие
O>>Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии" Pzz>По-моему, такого уже не бывает. Под стек просто резервируется сколько-то. Например, в ядре линукса под стек выделено 4К, куда уж меньше. Конечно, при программировании надо это учитывать, и не заводить на стеке больших массивов и структур.
В некоторых контроллерах оперативной памяти всего 8КБ. И сюда нужно засунуть глобальные переменные, стек и хип.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, alzt, Вы писали:
M>>Зато место на стеке бесплатное. Не надо ничего в куче выделять A>Можно пример кода с рекурсией, где за счёт этого будет экономия.
Обход дерева без рекурсии требует дополнительной памяти.
Здравствуйте, ononim, Вы писали:
O>В некоторых контроллерах оперативной памяти всего 8КБ. И сюда нужно засунуть глобальные переменные, стек и хип.
8K — это роскошь. В такой контроллер можно прям настоящую программу затолкать.
Мне тут приходилось программировать контроллер, в котором было только 128 байт. Причем когда мы договаривались об этой работе, мне сказали, что их там 256, а я сдуру поверил на слово. А когда вскрылась правда, было поздно что-то менять
Здравствуйте, Marty, Вы писали:
M> Здравствуйте!
M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
Кроме как проблемы переполнения стека еще типичная проблема быстродействия.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
Здравствуйте, Gradiens, Вы писали:
G>Здравствуйте, Marty, Вы писали:
G>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
G>Но себеседование действительно странное.
А вот на это ни кто не обратил внимание, в задаче фигурируют просто числа, т.е. "сферические числа в вакууме".
Здравствуйте, Gradiens, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) G>Кроме как проблемы переполнения стека еще типичная проблема быстродействия.
Здравствуйте, Marty, Вы писали:
M> Здравствуйте!
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Тут уже много написали, но может хотели очевидного? Рекурсия не инлайнится (рантайм рекурсия).
Здравствуйте, landerhigh, Вы писали:
L>Здравствуйте, Gradiens, Вы писали:
M>>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) G>>Кроме как проблемы переполнения стека еще типичная проблема быстродействия.
L>А вот с этого места можно поподробнее?
На этот вопрос у меня два ответа.
Во-первых, не очень опытные коллеги не всегда представляют вычислительную сложность реализуемого при помощи рекурсии решения. Результат: "ой, зависло".
Во-вторых у рекурсии большие накладные расходы. Если взять надуманный пример расчета факториала в цикле, или с рекурсией, то количество операций умножения будет одинаково. Но для рекурсии накладные расходы для вызова методов офигенны (это ж надо регистры запушить в стек, параметр занести в регистр или стек, провести вызов, после произведенных вычислений вернуть все как было до вызова и вернуть управление вызывающему коду). В результате скорость будет отличаться на порядок.
M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
DB>Думаю, что этот вопрос нормальный только есть в компании надо будет заниматься графикой или подобным.
Здравствуйте, alzt, Вы писали:
M>>>>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут C>>>Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.
M>>Зато место на стеке бесплатное. Не надо ничего в куче выделять
A>Можно пример кода с рекурсией, где за счёт этого будет экономия.
Здравствуйте, Gradiens, Вы писали:
G>Во-первых, не очень опытные коллеги не всегда представляют вычислительную сложность реализуемого при помощи рекурсии решения. Результат: "ой, зависло".
Э... ты, наверное, хотел сказать, "ой упало"?
G>Во-вторых у рекурсии большие накладные расходы. Если взять надуманный пример расчета факториала в цикле, или с рекурсией, то количество операций умножения будет одинаково. Но для рекурсии накладные расходы для вызова методов офигенны
В мире существуют не только процессоры x86/x86_64.
G>В результате скорость будет отличаться на порядок.
Такие заявления слуедует подкреплять бенчмарками. А то есть мнение, что толкать регистры в стек полюбому выйдет быстрее обращения к памяти мимо процессорного кеша. Не гворя уже о том, что подготовка и поддержание структуры данных для итеративной обработки взамен простой рекурсии тоже обходится не бесплатно.
Здравствуйте, Gradiens, Вы писали:
M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как? G>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
Наверно не точно сформулировал, но я так понял, что нужно сравнить на равенство. Может в такой формулировке и кривовато звучит
Здравствуйте, Qulac, Вы писали:
Q>Здравствуйте, Gradiens, Вы писали:
G>>Здравствуйте, Marty, Вы писали:
G>>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
G>>Но себеседование действительно странное.
Q>А вот на это ни кто не обратил внимание, в задаче фигурируют просто числа, т.е. "сферические числа в вакууме".
Ну не знаю.. у сферических чисел должен быть тип.
Например, Int32. Тогда в качестве переменной суммы используем Int64 — и никаких проблем в принципе не будет.
Или, тип чисел в массиве Int64. Тогда для суммы Int64 использовать нельзя, а вдруг переполнится. Надо использовать какой-нить BigInteger (я — дотнетчик, на других платформах должны быть аналоги, ну или их придется писать самому
Если же у нас тип чисел — double — то может быть две проблемы. Переполнение, а также потеря точности при суммировании большого и маленького числа.
Но все равно, не бывает сферических чисел без физического смысла. А также не могу представить себе ситуацию, когда надо выполнить 10^100 + 10^-100. Даже если сложить диаметр вселенной (самое большое что есть в природе) с Планковской длиной (самое маленькое что есть в природе) — и то менее внушительный пример получится. Так что пример надуманный и годится только для затравки разговора, но никак не для реальных выводов.
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
SaZ>Тут уже много написали, но может хотели очевидного? Рекурсия не инлайнится (рантайм рекурсия).
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) G>Кроме как проблемы переполнения стека еще типичная проблема быстродействия.
Это не так. Любую рекурсию можно заменить на итеративный алгоритм с использованием структуры данных стек. Только в большинстве случаев, эта структура данных стек будет реализована с использованием динамической памяти, что уже дороже, чем использовать программный стек, так как память надо выделять, освобождать. Можно реализовать стек и без постоянного выделения памяти, но тогда уже нужно потратить время на то, чтобы заранее оценить, какой размер такой структуры данных нужен.
В качестве упражнения, можешь попробовать реализовать quick-sort не рекурсивно. А потом реализовать quck-sort так, чтобы выделение памяти в куче происходило только один раз.
Здравствуйте, Gradiens, Вы писали:
G>Здравствуйте, Qulac, Вы писали:
Q>>Здравствуйте, Gradiens, Вы писали:
G>>>Здравствуйте, Marty, Вы писали:
G>>>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
G>>>Но себеседование действительно странное.
Q>>А вот на это ни кто не обратил внимание, в задаче фигурируют просто числа, т.е. "сферические числа в вакууме".
G>Ну не знаю.. у сферических чисел должен быть тип. G>Например, Int32. Тогда в качестве переменной суммы используем Int64 — и никаких проблем в принципе не будет. G>Или, тип чисел в массиве Int64. Тогда для суммы Int64 использовать нельзя, а вдруг переполнится. Надо использовать какой-нить BigInteger (я — дотнетчик, на других платформах должны быть аналоги, ну или их придется писать самому G>Если же у нас тип чисел — double — то может быть две проблемы. Переполнение, а также потеря точности при суммировании большого и маленького числа.
G>Но все равно, не бывает сферических чисел без физического смысла. А также не могу представить себе ситуацию, когда надо выполнить 10^100 + 10^-100. Даже если сложить диаметр вселенной (самое большое что есть в природе) с Планковской длиной (самое маленькое что есть в природе) — и то менее внушительный пример получится. Так что пример надуманный и годится только для затравки разговора, но никак не для реальных выводов.
"сферические числа в вакууме" у программистов и есть любой тип чисел.
По рекурсии я бы выделил три пункта:
1. Глубина рекурсии, т.е. смотреть чтобы не было переполнения стека.
2. Условие по выходу из рекурсии, т.е. оно должно 100 % выполняться.
3. Эффективность, т.е. проверка на повторяемость вычислений (действий). Если одни и те же вычисления повторяются много раз, то рекурсию применять не стоит.
По числам с плавающей точкой, как тут уже сказали, сравнивать нужно по модулю:
bool bEqual = fabs(dSum1 — dSum2) < dEpsilon;
Здравствуйте, Iso12, Вы писали:
I>По рекурсии я бы выделил три пункта: I>1. Глубина рекурсии, т.е. смотреть чтобы не было переполнения стека. I>2. Условие по выходу из рекурсии, т.е. оно должно 100 % выполняться.
Это уже какое-то собеседование на должность КО получается.
I>3. Эффективность, т.е. проверка на повторяемость вычислений (действий). Если одни и те же вычисления повторяются много раз, то рекурсию применять не стоит.
То есть если программа только и делает, что занимается обходом деревьев, то делать это рекурсивно нельзя?
То что я имел ввиду, это например вычисление чисел Fibbonachi:
fib (0) = fib (1) = 1
fib (n) = fib (n – 1) + fib (n – 2), n = 2, 3, ...
L>То есть если программа только и делает, что занимается обходом деревьев, то делать это рекурсивно нельзя?
Тут всё зависит от того, что мы хотим получить: скорость выполнения или простоту кода. Если время выполнения критично и есть алгоритм, который это делает быстрей без рекурсии, то рекурсия здесь не уместна.
I>То что я имел ввиду, это например вычисление чисел Fibbonachi:
А можно пример не из учебника или арсенала К.О, а встречающийся в реальной жизни?
L>>То есть если программа только и делает, что занимается обходом деревьев, то делать это рекурсивно нельзя? I>Тут всё зависит от того, что мы хотим получить: скорость выполнения или простоту кода. Если время выполнения критично и есть алгоритм, который это делает быстрей без рекурсии, то рекурсия здесь не уместна.
Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией.
L>А можно пример не из учебника или арсенала К.О, а встречающийся в реальной жизни?
В математических вычислениях часто встречается.
Что означает К.О. ?
L>Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией.
Если алгоритм с рекурсией самый быстрый и стек позволяет, то его и используйте. Код от этого будет проще и читабельней. Всему своё место. Или вы понимаете слово "Эффетивность" как-то по другому?
Здравствуйте, 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>Все же за требование "написать сходу" нужно гнать ссаными тряпками из профессии и лишать ученой степени/диплома.
Не было требования "написать сходу". Это я написал что у меня не получилось написать с нуля тупую неэффективную реализацию Фибоначчи, не используюя при этом рекурсию.
M>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос? M>Мне: Нет, и так много времени потратили. M>Ну, и вообще, всё норм с собеседованием?
Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов.
Здравствуйте, ·, Вы писали:
M>>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы ·>Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?..
Лучше, наверно, это не считать, не играть в наперстки — считать что здесь эти два числа равны (или не больше и не меньше).
Здравствуйте, Marty, Вы писали:
M> Здравствуйте!
M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Можно заметить, что F(3) вычисляется три раза. Если рассмотреть вычисление F(n) при больших n, то повторных вычислений будет очень много. Это и есть основной недостаток рекурсии — повторные вычисления одних и тех же значений.
Здравствуйте, turbocode, Вы писали:
M>>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос? M>>Мне: Нет, и так много времени потратили. M>>Ну, и вообще, всё норм с собеседованием?
T>Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов.
Я конечно понимаю, что ты хочешь меня унизить, но два часа интервью на "побыстрее" ну никак не натянуть
Здравствуйте, Silver_S, Вы писали:
M>>>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы S_S>·>Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?.. S_S> Лучше, наверно, это не считать, не играть в наперстки — считать что здесь эти два числа равны (или не больше и не меньше).
На практике я бы при таких требованиях плавучку бы и не использовал — во избежание.
Но это я так... в качестве этюда интересуюсь — возможно ли. Например, отсортировать оба массива по убыванию, а потом сделать алгоритм напоминающий sorted merge join — брать и прибавлять элементы первого или вычитать элементы второго массивов в зависимости от знака текущей суммы. Сработает?..
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
T>>Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов. M>Я конечно понимаю, что ты хочешь меня унизить, но два часа интервью на "побыстрее" ну никак не натянуть
"солдат спит служба идет" — игра на собеседовании в одни ворота это всегда провал.
Здравствуйте, landerhigh, Вы писали: L>Я прошу пример реализуемого через рекурсию алгоритма, который эффективнее реализовать без оной.
Я взял в качестве дерева просто LinkedList<int> из .Net :D
Складываем элементы списка.
Тестировал итеративный алгоритм и два варианта рекурсии. Собиралось все с таргетом x86.
Результаты у меня такие:
Started!
Iterative: 38 ms, recursiveSimple: 80 ms, recursiveAcc: 92 ms
Код
class Program
{
static void Main(string[] args)
{
var runner = new Thread(Run, 1000 * 1024 * 1024);
runner.Start();
runner.Join();
}
static void Run()
{
var T = new Stopwatch();
var src = Generate(10);
SumIterative(src.First);
SumRecursiveSimple(src.First);
SumRecursiveAcc(src.First);
src = Generate(10000000);
Console.WriteLine("Started!");
int count = 100;
var iterative = 0l;
var recursiveSimple = 0l;
var recursiveAcc = 0l;
for (int i = 0; i < count; i++)
{
T.Restart();
SumIterative(src.First);
T.Stop();
iterative += T.ElapsedMilliseconds;
T.Restart();
SumRecursiveSimple(src.First);
T.Stop();
recursiveSimple += T.ElapsedMilliseconds;
T.Restart();
SumRecursiveAcc(src.First);
T.Stop();
recursiveAcc += T.ElapsedMilliseconds;
}
Console.WriteLine($"Iterative: {iterative/count} ms, recursiveSimple: {recursiveSimple/count} ms, recursiveAcc: {recursiveAcc/count} ms");
}
static LinkedList<int> Generate(int size)
{
var r = new LinkedList<int>();
var random = new Random();
for (int i = 0; i < size; i++)
{
r.AddLast(random.Next());
}
return r;
}
static int SumIterative(LinkedListNode<int> e)
{
var r = 0;
for (var curr = e; curr != null; curr = curr.Next)
r += curr.Value;
return r;
}
static int SumRecursiveAcc(LinkedListNode<int> e, int curr = 0)
{
if (e == null)
return curr;
return SumRecursiveAcc(e.Next, e.Value + curr);
}
static int SumRecursiveSimple(LinkedListNode<int> e)
{
if (e == null)
return 0;
return e.Value + SumRecursiveAcc(e.Next);
}
}
SL> static int SumRecursiveSimple(LinkedListNode<int> e)
SL> {
SL> if (e == null)
SL> return 0;
SL> return e.Value + SumRecursiveAcc(e.Next); /// Вызван не тот метод
SL> }
SL>
А вообще, C# не поддерживает tail-call. Так что, замер SumRecursiveAcc ничего не демонстрирует кроме сего факта.
Здравствуйте, StatujaLeha, Вы писали:
SL>Здравствуйте, samius, Вы писали:
S>>А вообще, C# не поддерживает tail-call. Так что, замер SumRecursiveAcc ничего не демонстрирует кроме сего факта.
SL>Да, согласен. Но есть надежда на JIT-compiler.
Нету, т.к. надежда JIT-compiler-а — OpCode.Tailсall. А без него он делать ничего сам не будет.
SL>Ну и разница во времени работы между двумя алгоритмами есть.
вот разница у меня
Iterative: 17 ms, recursiveSimple: 31 ms, recursiveAcc: 33 ms
FSharp: 17 ms
где
module FsModule1
let rec sumRec (n : System.Collections.Generic.LinkedListNode<int>) sum =
if obj.ReferenceEquals(n, null) then sum
else sumRec n.Next (sum + n.Value)
Re[11]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, StatujaLeha, Вы писали:
SL>Здравствуйте, samius, Вы писали:
SL>Ясно. SL>Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример.
А разве есть другие?
Re[11]: Вопросы на собеседовании (в очередной раз)
I>>Какая тут демагогия? Конкретная задача, требуется найти решение. Ваш пример это совсем не то, что я просил.
L>Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается.
То что я просил сделать, сделали вот здесь
разницу видно?
I>>Я вам и том и толкую, что рекурсия это лишь иструмент, и применять его надо, где он подходит. L>Вот только не надо с умным видом декламировать прописные истины. Это не чат детского сада. И это не имеет никакого отношения к изначальной теме.
Я только повторил ваш тезис, с которым я согласился. Все претензии по декламированию только к себе.
I>>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.
L>Ошибку исправил.
После этого примера
Здравствуйте, Iso12, Вы писали:
L>>Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается. I>То что я просил сделать, сделали вот здесь
Мне было лень ровно это же писать, ибо идея лежит насколько на поверхности, что даже дуб вроде меня ее видит как само собой разумеющееся.
I>В вашем коде: I>
Это не мой код, а классика шаблонного метапрограммирования. Еще раз, там присутствует мемоизация промежуточных результатов (достается "бесплатно" с точки зрения расхода времени программиста), то есть промежуточные результаты считаются ровно один раз. Небольшой такой нюанс.
I>>>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления. L>>Ошибку исправил. I>После этого примера
Числа Фибоначчи — просто такой странный пример, когда определение понятия является определениеам алгоритма, который можно один-в-один перенести в реализацию и оно даже будет работать. Но определение не обязано быть ни алгоритмом, ни оптимальным алгоритмом.
В смысле? Возможны ли алгоритмы, где нельзя tail-call?
В моем примере SumRecursiveSimple: рекурсивный, но у него рекурсивный вызов — не последнее действие. Как тут tail-call делать?
Re[11]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, landerhigh, Вы писали:
L>Что доказывает, что при должном рвении все, что угодно можно сделать через одно место
Само собой, это ничего не доказывает.
Например, samius делал утверждение о tail-оптимизации и в подтверждение кинул код с результатами. Можно увидеть цифру и проверить ее самому.
И именно поэтому это что-то доказывает.
А фраза "все, что угодно можно сделать через одно место" — это вода
В моем примере используется стандартный контейнер из широко используемого фреймворка.
Выбранная задача проще некуда.
Реализации тоже проще некуда.
Буду рад хоть какому-то подтверждению указанных слов.
Пересмотрел код, вроде как для данной платформы улучшать там нечего
L>А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно.
Так ждем
Заодно посмотрим, что имеется ввиду под "полноценным деревом" и чем оно полноценнее двусвязаного списка(который частный случай дерева).
Сначала можно рекурсивно, а потом, так и быть, итеративно.
И даже больше! Можно сначала итеративно, а потом рекурсивно! :D
Re[12]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, StatujaLeha, Вы писали:
SL>Само собой, это ничего не доказывает.
Да нет, как раз доказывает. Что при должном рвении и черное можно белым назвать.
SL>Например, samius делал утверждение о tail-оптимизации и в подтверждение кинул код с результатами. Можно увидеть цифру и проверить ее самому. SL>И именно поэтому это что-то доказывает.
SL>А фраза "все, что угодно можно сделать через одно место" — это вода
Нет, это констатация приведенного "примера", в котором применение рекурсии как минимум бессмысленно.
SL>В моем примере используется стандартный контейнер из широко используемого фреймворка. SL>Выбранная задача проще некуда.
И бессмысленнее тоже некуда
SL>Буду рад хоть какому-то подтверждению указанных слов.
Каких именно?
L>>А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно. SL>Так ждем
Так вот это я тебе предлагаю. Простейшая задача — есть дерево. С ветками и листьями. Обойти depth first. Или width first. Рекурсивно. А потом итеративно. Сравнить производительность. И накладные расходы. Сделать вывод о применимости рекурсивных алгоритмах и их преимуществах (и недостатках).
SL>Заодно посмотрим, что имеется ввиду под "полноценным деревом" и чем оно полноценнее двусвязаного списка(который частный случай дерева).
Здравствуйте, StatujaLeha, Вы писали:
SL>Здравствуйте, samius, Вы писали:
S>>А разве есть другие?
SL>В смысле? Возможны ли алгоритмы, где нельзя tail-call?
Угу SL>В моем примере SumRecursiveSimple: рекурсивный, но у него рекурсивный вызов — не последнее действие. Как тут tail-call делать?
SumRecursiveSimple — это не алгоритм, а частная реализация. Алгоритмом здесь является что-то вроде "значение каждого элемента списка прибавить к результирующей сумме". Таким образом, SumRecursiveSimple, SumRecursiveAcc, ... ForeachSum, AggregateSum, ParallelForSum — формы записи одного алгоритма. Способы обхода и итерирования — специфичные особенности каждой реализации. И среди всех способов записи обязательно (на сколько я понимаю) найдется рекурсивная с потенциальной возможностью tail-call оптимизации. В данном случае такой является SumRecursiveAcc.
Re[13]: Вопросы на собеседовании (в очередной раз)
Здравствуйте, 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 формы, используемой компиляторами. Тогда такой учебник вряд ли достоин внимания в этом вопросе.
В любом случае будет любопытно взглянуть. Не подскажете название?