Вопросы на собеседовании (в очередной раз) - О работе

M>Я: Ок, я провалил вопрос. Можно узнать, что вы имели в виду, можно глубже раскрыть вопрос?
M>Мне: Нет, и так много времени потратили.
M>Ну, и вообще, всё норм с собеседованием?

Очевидно что интервьюер твои ответы вовсе не слушал и задавал вопросы чтобы побыстрее выставить тебя за дверь. Решение тебя не брать было принято еще до вопросов.

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

M>>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы
·>Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?..

Лучше, наверно, это не считать, не играть в наперстки — считать что здесь эти два числа равны (или не больше и не меньше).

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

M> Здравствуйте!

M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.

M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию

Может он тупо чего-то примитивное в инете вычитал. Google что-то выдает про проблемы:
https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F

Можно заметить, что 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);
        }
    }

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

SL>

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 ничего не демонстрирует кроме сего факта.

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

Пофиксил.
Результаты:

Iterative: 39 ms, recursiveSimple: 138 ms, recursiveAcc: 84 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 + SumRecursiveSimple(e.Next);
        }
    }

S>А вообще, C# не поддерживает tail-call. Так что, замер SumRecursiveAcc ничего не демонстрирует кроме сего факта.

Да, согласен. Но есть надежда на JIT-compiler.
Ну и разница во времени работы между двумя алгоритмами есть.

Здравствуйте, 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)

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

Ясно.
Видимо, рекурсивные алгоритмы, где возможен tail-call, не лучший пример.
Пример же с обходом полноценного дерева лень делать.

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

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

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

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

·>Бред, дело не в рекурсии, а в алгоритме. Без рекурсии тоже можно тупой алгоритм написать. А вот рекурсия без "промежуточных" результатов:
·>

·>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);
·>}
·>

Да, как раз то что я просил сделать. Хорошее решение, с передачей через стек промежуточных результатов (через val).

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

I>>Какая тут демагогия? Конкретная задача, требуется найти решение. Ваш пример это совсем не то, что я просил.

L>Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается.
То что я просил сделать, сделали вот здесь.

В вашем коде:

return fibonacci(index - 1) + fibonacci(index - 2);

Код, который привёл ".":

return fib(term - 1, val+prev, val);

разницу видно?

I>>Я вам и том и толкую, что рекурсия это лишь иструмент, и применять его надо, где он подходит.
L>Вот только не надо с умным видом декламировать прописные истины. Это не чат детского сада. И это не имеет никакого отношения к изначальной теме.
Я только повторил ваш тезис, с которым я согласился. Все претензии по декламированию только к себе.

I>>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.

L>Ошибку исправил.
После этого примера, пожалуй соглашусь.

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

SL>Ну и разница во времени работы между двумя алгоритмами есть.

Что доказывает, что при должном рвении все, что угодно можно сделать через одно место

А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно.

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

L>>Самая прямая. А мой пример — как раз вычисление этих самых чисел. Рекурсией. Правда, там мемоизация присутствует, но рекурсия от этого никуда не девается.
I>То что я просил сделать, сделали вот здесь.

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

I>В вашем коде:
I>

I>return fibonacci(index - 1) + fibonacci(index - 2);
I>

Это не мой код, а классика шаблонного метапрограммирования. Еще раз, там присутствует мемоизация промежуточных результатов (достается "бесплатно" с точки зрения расхода времени программиста), то есть промежуточные результаты считаются ровно один раз. Небольшой такой нюанс.

I>>>При плохой реализации алгоритма в таких задачах как расчёт числа Fibonachi промежуточные результаты расчитывается по нескольку раз, это влияет на скорость выполнения вычисления.
L>>Ошибку исправил.
I>После этого примера, пожалуй соглашусь.

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

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

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

В смысле? Возможны ли алгоритмы, где нельзя tail-call?
В моем примере SumRecursiveSimple: рекурсивный, но у него рекурсивный вызов — не последнее действие. Как тут tail-call делать?

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

L>Что доказывает, что при должном рвении все, что угодно можно сделать через одно место

Само собой, это ничего не доказывает.

Например, samius делал утверждение о tail-оптимизации и в подтверждение кинул код с результатами. Можно увидеть цифру и проверить ее самому.
И именно поэтому это что-то доказывает.

А фраза "все, что угодно можно сделать через одно место" — это вода

В моем примере используется стандартный контейнер из широко используемого фреймворка.
Выбранная задача проще некуда.
Реализации тоже проще некуда.

Буду рад хоть какому-то подтверждению указанных слов.
Пересмотрел код, вроде как для данной платформы улучшать там нечего

L>А теперь предлагаю попробовать написать то же самое, но с полноценным деревом. Сначала рекурсивно, а потом, так и быть, итеративно.

Так ждем

Заодно посмотрим, что имеется ввиду под "полноценным деревом" и чем оно полноценнее двусвязаного списка(который частный случай дерева).
Сначала можно рекурсивно, а потом, так и быть, итеративно.
И даже больше! Можно сначала итеративно, а потом рекурсивно! :D

Здравствуйте, 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.

	От:	turbocode
	Дата:	10.04.17 10:21
	Оценка:

	От:	Silver_S
	Дата:	10.04.17 10:41
	Оценка:

	От:	Silver_S
	Дата:	10.04.17 10:59
	Оценка:

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	10.04.17 11:05
Оценка:

	От:	·
	Дата:	10.04.17 11:08
	Оценка:

От:	StatujaLeha	на правах ИМХО
Дата:	10.04.17 19:19
Оценка:

От:	samius	http://sams-tricks.blogspot.com
Дата:	10.04.17 19:41
Оценка:	+1

	От:	landerhigh
	Дата:	11.04.17 21:20
	Оценка: