AXForum  
Вернуться   AXForum > Прочие обсуждения > Курилка
All
Забыли пароль?
Зарегистрироваться Правила Справка Пользователи Сообщения за день Поиск Все разделы прочитаны

 
 
Опции темы Поиск в этой теме Опции просмотра
Старый 10.02.2017, 21:45   #41  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,371 / 445 (19) +++++++
Регистрация: 03.12.2001
Она и для фибоначчи замечательно выполняется:

X++:
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))
Старый 10.02.2017, 21:55   #42  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,371 / 445 (19) +++++++
Регистрация: 03.12.2001
И, извини, но я все-таки спрошу:

Цитата:
может, просто приведешь пример?
ну, или ссылки хотя бы )))
Цитата:
Для факториала как раз замечательно выполняется оптимизация хвостовой рекурсии даже вручную. На собеседовании могут давать факториал, а могут давать фибоначчи ))))
....
бывает, конечно, когда кандидат не врубается и предлагает "удалиться".
что ж... в этом случае вряд ли такому кандидату стоит задавать другие вопросы.
Так ты хотел узнать что такое оптимизация хвостовой рекурсии или устроить мне собеседование? Если первое - я постарался ответить.
За это сообщение автора поблагодарили: mazzy (2).
Старый 10.02.2017, 22:09   #43  
mazzy is offline
mazzy
Administrator
Аватар для mazzy
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
Most Valuable Professional
 
20,693 / 3296 (151) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Андре Посмотреть сообщение
Она и для фибоначчи замечательно выполняется:

X++:
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))
ленивые функциональщики ))))
собственно возвращаемся к моему посту:

Цитата:
Сообщение от mazzy Посмотреть сообщение
тут дело даже не в функциональном языке или процедурном.
тут дело в ленивых вычислениях.
...
именно ленивые вычисления и отсутствие побочных эффектов и позволяют так легко использовать рекурсию.
...
обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.
А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))
и вот я совсем не уверен, что оптимизация сработает с таким выражением.

И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли? ленивость и отсутствие побочных эффектов.

Если бы подобная ленивость была бы в обычном языке, то...
Сейчас в .net вводят LINQ и Lazy-интерфейсы... это конечно не то, но достаточно близко...

можешь рассказать подробнее как "это" работает?

Цитата:
Сообщение от Андре Посмотреть сообщение
Так ты хотел узнать что такое оптимизация хвостовой рекурсии или устроить мне собеседование? Если первое - я постарался ответить.
Спасибо что ответил.

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

в свое время я тебя приглашал, но у тебя была более привлекательная работа.
до сих пор жалею, что тогда не смог предложить тебе лучшие условия.
Старый 10.02.2017, 22:24   #44  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,371 / 445 (19) +++++++
Регистрация: 03.12.2001
Цитата:
А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))
и вот я совсем не уверен, что оптимизация сработает с таким выражением.

И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли? ленивость и отсутствие побочных эффектов.
Нет! При чем тут ленивость и при чем тут побочные эффекты.

Половина функциональных языков программирования принципиально не поддерживают ленивость. Вот от слова "вообще". Нет ее там. А в тех языках где есть - я 10 раз подумаю, прежде чем ее использовать. Потому что в языках с поддержкой ленивых вычислений надо четко представлять, где и в какой момент это вычисление произойдет. А иначе оно произойдет в самый непоходящий для пользователя момент (в виде проблем с производительностью). Нет в моем примере никакой ленивости.

Теперь побочные эффекты. Их здесь нет, но если этот код переписать на C# или Java - их тоже не появится. Им просто не откуда здесь взяться. Ну и вообще, если говорить про функциональные языки программирования - то из тех, что используются в production я знаю только 1 - haskell. Все остальные функциональные языки программирования допускают побочные эффекты.

Цитата:
А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))
В языке с поддержкой хвостовой ресурсии - не будет.

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

Цитата:
можешь рассказать подробнее как "это" работает?
Да вроде уже максимально подробно. Смотри - при вызове функции ты на стек помещаешь 4 вещи: адрес возрата и три параметра. Теперь происходит очередной рекурсивный вызов. По идее компилятор должен положить еще 4 параматера. Но он умный и видит, что после того, как ты вернешься из этого рекурсивного вызова то, что до этого лежало на стеке тебе просто уже не понадобится. Ну просто потому что после рекурсивного вызова уже нет никаких вычисленией. А значит текущие значения a, b и count можно смело снять со стека, заменив на новые.

Все равно не понятно ?
Старый 10.02.2017, 22:25   #45  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
686 / 521 (19) +++++++
Регистрация: 14.10.2004
Получается, что тот кусок кода, который я написал вчера ночью за две минуты, укладывая сына спать, не имея Аксапты под рукой, добавил мне минус в карму?
Старый 10.02.2017, 22:33   #46  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,371 / 445 (19) +++++++
Регистрация: 03.12.2001
Можно еще вот так попробовать расписать - вызовы функций, как они будут происходить

X++:
fib 5
fib-iter 1 0 5
fib-iter 1 1 4
fib-iter 2 1 3
fib-iter 3 2 2
fib-iter 5 3 1
fib-iter 8 5 0
-> 5
То есть, мы вызываем fib 5, оно вызывает fib-iter 1 0 5, оно вызывает fib-iter 1 1 4 и так далее, пока вызов fib-iter 8 5 0 не вернет 5-ку.

Обрати внимание, что каждый последующий вызов - он самодостаточен. То есть. когда fib-iter 8 5 0 вернет 5-ку ему эту 5-ку надо просто вернуть, а не делать с ней что-то еще вверх по стеку вызовов. Это потому, что у нас последний вызов в функции выглядит так:

X++:
(fib-iter (+ a b) a (- count 1))))
А вот если бы он выглядел как то так

X++:
a + (fib-iter (+ a b) a (- count 1))))
то рекурсию нельзя было бы оптимизировать. Так как при последнем рекурсивном вызове полученную 5-ку надо была вернуть вверх по стеку, чтобы сложить вот с этой 'a'. И так далее.

Вот. Все - лучше мне уже на форуме не объяснить

p.s.

Цитата:
И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли?
А повторных вычислений здесь нет, потому что алгоритм так написан. Ну, их просто не надо делать, как и том примере с циклом.

Цитата:
обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.
Вот - вот. Я собственно это и делаю (см выше стек вызовов, что я привел). Просто совместил это с рекурсией, которая при этом еще и хвостовая

Последний раз редактировалось Андре; 10.02.2017 в 22:41.
За это сообщение автора поблагодарили: mazzy (2).
Старый 10.02.2017, 23:01   #47  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
686 / 521 (19) +++++++
Регистрация: 14.10.2004
Маззи, пожалуйста не приводите мой код как пример дешевого программиста
Я выскочка с гуманитарным образованием.
Для людей с неправильным происхождением свойственно натыкаться на грабли на пути к совершенству. Сейчас я понял, что моя вчерашняя попытка написать пример была ошибкой. Но из-за некоторых таких попыток мне все-таки удалось кое-чего достичь в жизни. И я пока еще выживаю в конкурентной борьбе.
Я готов быть аутсайдером в окружении богов.
Готов получать 500 тыс рублей среди людей, которые получают миллион рублей.
Поэтому и встреваю в беседы великих
За это сообщение автора поблагодарили: mazzy (2), ax_mct (5).
Старый 10.02.2017, 23:13   #48  
mazzy is offline
mazzy
Administrator
Аватар для mazzy
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
Most Valuable Professional
 
20,693 / 3296 (151) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Андре Посмотреть сообщение
Это потому, что у нас последний вызов в функции выглядит так:

X++:
(fib-iter (+ a b) a (- count 1))))
А вот если бы он выглядел как то так

X++:
a + (fib-iter (+ a b) a (- count 1))))
то рекурсию нельзя было бы оптимизировать.
ааааааа. так вот почему ты передаешь два аргумента, где первый может потеряться...

т.е. от повторных вычислений можно избавиться и в обычных процедурных языках?
что-то типа такого
Код:
public var fib(var n)
{
   fibb-iter(1, 0, n);
}

private var fib-iter(var a, var b, var n)
{
   if(n <= 0)
      return b;
   else
      return fib-iter(a+b, b, n-1);
}
и получаем линейное, а не экспоненциальное время выполнения. и никаких повторных вычислений.
правда без "оптимизации хвостовой рекурсии" рекурсивные вызовы ограничены размером стека. а с оптимизацией стек вообще расти не будет.
так?

чертовы функциональщики... )))))

а разве функциональный язык не разворачивает всю эту байду в символьное супер-выражение, которое будет вычислено на самом последнем этапе?
Старый 10.02.2017, 23:15   #49  
mazzy is offline
mazzy
Administrator
Аватар для mazzy
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
Most Valuable Professional
 
20,693 / 3296 (151) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от mazzy Посмотреть сообщение
т.е. от повторных вычислений можно избавиться и в обычных процедурных языках?
Интересно, а как Silence свою рекурсию написал?
может, зря я на него бочку качу...

Цитата:
Сообщение от Silence Посмотреть сообщение
ЗЫ. Помню дали задачку, вывести ряд Фибоначи. Нарисовал рекурсию. Не понравилось. Видать не поняли.
Старый 10.02.2017, 23:24   #50  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,371 / 445 (19) +++++++
Регистрация: 03.12.2001
Цитата:
и получаем линейное, а не экспоненциальное время выполнения. и никаких повторных вычислений.
правда без "оптимизации хвостовой рекурсии" рекурсивные вызовы ограничены размером стека. а с оптимизацией стек вообще расти не будет.
так?
Да. Я правда подозреваю, что хороший оптимизатор это в цикл преобразует.

Цитата:
а разве функциональный язык не разворачивает всю эту байду в символьное супер-выражение, которое будет вычислено на самом последнем этапе?
Зависит от языка. Есть языки где вообще нет ленивых вычислений. Есть языки, где можно "включить" ленивость используя специальные выражения (ключевое слово lazy в F#), есть языки где все лениво по умолчанию (Haskell).
За это сообщение автора поблагодарили: mazzy (2).
Старый 10.02.2017, 23:32   #51  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
686 / 521 (19) +++++++
Регистрация: 14.10.2004
Маззи, а как вам такой вариант?
X++:
static void Job46(Args _args)
{
     int j;
     
     real fibonaci(int n)
     {
        real    first = 0;
        real    second = 1;
        real    result = 0;
        int     i;
        for (i = 0; i < n; i++)
        {
            result = first + second;
            second = first;
            first = result;
        }
        return result;
    }
    ;
    for (j = 0; j < 50; j++)
    {
        info(strfmt("%1", fibonaci(j)));
    }
}
За это сообщение автора поблагодарили: mazzy (2).
Старый 10.02.2017, 23:32   #52  
mazzy is offline
mazzy
Administrator
Аватар для mazzy
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
Most Valuable Professional
 
20,693 / 3296 (151) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Ace of Database Посмотреть сообщение
Получается, что тот кусок кода, который я написал вчера ночью за две минуты, укладывая сына спать, не имея Аксапты под рукой, добавил мне минус в карму?
не знаю. это вам решать.

ваш кусок кода выполняет вычисления за один проход без повторных вычислений. что является достижением. и потребляет фиксированную память.
вот только int32 и панковский while(true)... ну и int2str...
живите теперь с этим. ))))
Старый 10.02.2017, 23:35   #53  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
686 / 521 (19) +++++++
Регистрация: 14.10.2004
Цитата:
Сообщение от mazzy Посмотреть сообщение
не знаю. это вам решать.
вот только int32 и панковский while(true)... ну и int2str...
живите теперь с этим. ))))
Нет, теперь я отрекусь от этого! Я постоянно меняюсь.
Старый 10.02.2017, 23:38   #54  
mazzy is offline
mazzy
Administrator
Аватар для mazzy
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
Most Valuable Professional
 
20,693 / 3296 (151) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Ace of Database Посмотреть сообщение
Маззи, а как вам такой вариант?
вложенные то циклы зачем? раньше был один. и это было хорошо.

и снова без комментариев в коде нет комментариев по поводу используемого типа real )
и магическая константа в коде... константу-то можно было бы и прокомментировать.

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

заодно это и было бы обоснованием для магической константы ))))

Последний раз редактировалось mazzy; 10.02.2017 в 23:44.
Старый 10.02.2017, 23:49   #55  
Ace of Database is offline
Ace of Database
Участник
Аватар для Ace of Database
 
686 / 521 (19) +++++++
Регистрация: 14.10.2004
Цитата:
Сообщение от mazzy Посмотреть сообщение
вложенные то циклы зачем?
.....
заодно это и было бы обоснованием для магической константы ))))
Вложенный цикл - для наглядности. Просто я выделил получение n-ного члена последовательности в отдельную процедуру. Чтобы показать, как можно вычислить отдельный член последовательности. Для будущего использования этого алгоритма. Если задача получения отдельных членов не стоит, а надо просто получить сразу всю последовательность, то конечно можно ее сразу вывести в инфолог в одном цикле.

Константа 50 - тоже для наглядности. Просто красивое число для примера вывода первых 50 членов последовательности.
За это сообщение автора поблагодарили: mazzy (2).
Старый 10.02.2017, 23:52   #56  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,371 / 445 (19) +++++++
Регистрация: 03.12.2001
Прошу прощения, но не удержался:

X++:
let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.take 50
А вот получение первых 50-ти членов на F#. Ленивое, как ты, mazzy, и хотел

Последний раз редактировалось Андре; 11.02.2017 в 00:04.
Старый 11.02.2017, 00:02   #57  
mazzy is offline
mazzy
Administrator
Аватар для mazzy
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
Most Valuable Professional
 
20,693 / 3296 (151) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Some? почему some?
вернее, а что значит Some в данном контексте?

и почему целые 0, 1?
а целые в F# скольки разрядные? как F# относится к переполнению целого?

Цитата:
Сообщение от Андре Посмотреть сообщение
Ленивое, как ты, mazzy, и хотел
я не то, чтобы хотел.
я опасался, что построенное супер-выражение в стек ляжет.

причем лобовое решение fib(n-1)+fib(n-2) скорее всего быстро переполнит стек и в функциональном языке за счет повторных подстановок в результирующее супер-выражение.
Старый 11.02.2017, 00:51   #58  
mazzy is offline
mazzy
Administrator
Аватар для mazzy
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
Most Valuable Professional
 
20,693 / 3296 (151) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
int - 32 разряда
суффикс I означает bigInt
some(a,b) означает some(tuple(a,b)), что означает nullable tuple(a,b)
tuple(a,b) в контексте функции unfold означает: a - текущее состояние, b - следующее состояние.

так? ахренеть!

еще фибоначчи на F#
https://msdn.microsoft.com/en-us/vis...n-%5Bfsharp%5D
http://www.blogs.sigristsoftware.com...-Sequence.aspx

мдя...

=========================
а как это ленивое чудо потребляет память?
Старый 11.02.2017, 07:11   #59  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,371 / 445 (19) +++++++
Регистрация: 03.12.2001
Цитата:
int - 32 разряда
суффикс I означает bigInt
some(a,b) означает some(tuple(a,b)), что означает nullable tuple(a,b)
tuple(a,b) в контексте функции unfold означает: a - текущее состояние, b - следующее состояние.

так? ахренеть!
А его поэтому с самого начала и не стал писать. Слишком много ньюансов, которые уже надо знать. Тут это скорее, чтобы показать насколько функциональный код может быть более компактным, нежели императивный.

0I,1I - как ты правильно заметил, что BigInteger, а точнее, обертка вот над этой .NET структурой: https://msdn.microsoft.com/ru-ru/lib...v=vs.110).aspx

Цитата:
The T:System.Numerics.BigInteger type is an immutable type that represents an arbitrarily large integer whose value in theory has no upper or lower bounds.
X++:
fun (x, y) -> Some(x, (y, x + y))
Вот это функция, которая на вход принимает некое текущее состояние, а на выходе может быть (ну, если получится) вернет пару значений: очередной элемент последовательности и новое состояние.

Эта функция (как видно по ее названию) противоположна более популярной функции fold (которая в python называется reduce, а в C# LINQ - aggregate):

Цитата:
Seq.fold (fun acc elem -> acc + elem) 0 seq
Здесь мы сворачивает последовательность в одно число путем указания функции - "как именно это делать - суммировать". Вот LINQ:

Цитата:
seq.Aggregate(0, (acc, elen) => acc + elem);
unfold - противоположна - из неких начальных значений обратно разворачивает последовательность.

Теперь про Some - я там выше написал, что эта функция "постарается" вернуть очередное значение. Но компилятор понимает, что это не всегда возможно. И хочет, чтобы ты это понимал и не забывал и предлагает использовать тебе "option type" - аналог монады MayBe из других языков программирования.
Старый 11.02.2017, 08:52   #60  
mazzy is offline
mazzy
Administrator
Аватар для mazzy
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
Most Valuable Professional
 
20,693 / 3296 (151) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Андре Посмотреть сообщение
Слишком много ньюансов, которые уже надо знать.
угу.
http://coub.com/view/b8if4
)
 

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход

Рейтинг@Mail.ru
Часовой пояс GMT +3, время: 01:49.
Powered by vBulletin® v3.8.5. Перевод: zCarot
Контактная информация, Реклама.