Ответ на »сообщение 601« (Lisp Hobbyist)
___________________________
Простите но автоматическая мемоизация это из области фантастики :))
Основывать свои утверждения на том что никто никогда не делал, и даже не имел планов,
это все равно что доказывать вечный двигатель, чего я конечно же не собираюсь делать так же как и французская академия. :))
Засим оставляю вас с вашими планами по автоматической мемоизации.
А пока что жду существенного ускорения предложенного вами первоначально алгоритма на любом из СУЩЕСТВУЮЩИХ языков.

Если хотите могу исправить свое первоначальное утверждение привести его к виду

На любом СУЩЕСТВУЮЩЕМ языке, первый алгоритм выдаст те же результаты по времени.

Так понятнее ? :))

Очень неприятно нарушать торжественное обещание не флеймить больше на тему чисел Фибоначчи, но я тут поэкспериментировал с memoization, и результат удивил даже меня:

(defun fib (n)
  (cond ((< n 3) 1)
        (t (+ (fib (1- n)) (fib (- n 2))))))

(defun memoize (f)
  (let ((ht (make-hash-table)) (old-f (symbol-function f)))
    (setf (symbol-function f)
          #'(lambda (x)
              (multiple-value-bind (v found) (gethash x ht)
                (if found
                    v
                  (setf (gethash x ht) (funcall old-f x))))))))

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

Пояснение для тех, кто не знает Лиспа. Вызов вида

(memoize 'f)

подменяет определение функции f: для нее создается анонимная функция-"обертка", которая при каждом вызове исходной функции с новым значением аргумента запоминает пару (аргумент, значение) в хэш-таблице. Соответственно, при повторном вызове функции ее значение не вычисляется, а берется из хэша. 

Такое "кэширование", с одной стороны, может существенно ускорить выполнение программ, а с другой --- весьма опасно неожиданными побочными эффектами (или их отсутствием в случае повторных вызовов).

Результаты --- см. ниже. Все замеры выполнялись на том же clisp 2.33 в режиме интерпретации. Следует оговорить особо, что в случае с другими реализациями Common Lisp фокус может не получиться, поскольку компиляция может иметь в данном случае далеко идущие последствия:

http://www.lispworks.com/documentation/HyperSpec/Body/03_bbc.htm


Within a function named F, the compiler may (but is not required to) assume that an apparent recursive call to a function named F refers to the same definition of F, unless that function has been declared notinline. The consequences of redefining such a recursively defined function F while it is executing are undefined.


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

Итак:

[2]> (time (fib 20))

Real time: 0.015625 sec.
Run time: 0.015625 sec.
Space: 0 Bytes
6765
[3]> (memoize 'fib)
#<CLOSURE :LAMBDA (X)
  (MULTIPLE-VALUE-BIND (V FOUND) (GETHASH X HT)
  (IF FOUND V (SETF (GETHASH X HT) (FUNCALL OLD-F X))))>
[4]> (time (fib 20))

Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 1696 Bytes
6765
[5]> (time (fib 200))

Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 14388 Bytes
280571172992510140037611932413038677189525
[6]> (time (fib 1000))

Real time: 0.015625 sec.
Run time: 0.015625 sec.
Space: 101044 Bytes
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875

ИМХО, ускорение вполне приличное (поедание памяти --- тоже :-). Аналогичный механизм может быть реализован "прозрачно", внутри исполняющей подсистемы любого "чистого" ФЯ. Естественно, в этом случае он может быть сделан сколь угодно интеллектуальным. Например, может быть организовано вытеснение редко используемых значений по принципу, аналогичному аппаратной кэш-памяти, либо же выбор кэшируемых значений динамически, по результатам измерения времени исполнения функций.

Ответ на »сообщение 586« (Jack Of Shadows)
___________________________

Что касается мемоизации, то это уже изменение алгоритма,

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

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

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


Опровергайте. Об этом я вас уже в третий раз наверное прошу :))

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


Ох, Jack, в своем стремлении меня уесть Вы сами роете себе яму. Во-первых, если Вы внимательно прочтете мое утверждение, то в нем нет ни слова о том, что реализация Haskell с memoization уже существует:

>>> Реализация функционального языка (того же Haskell), в которой не пожалеют памяти на memoization, вероятно, сможет опровергнуть это утверждение.

Здесь утверждается лишь то, что такая реализация в принципе возможна и указано, что именно нужно сделать. Ее вероятные временнЫе характеристики могут быть примерно оценены из приведенных выше замеров производительности.  Они не достигают уровня производительности fib-tail, но они существенно лучше "наивного" вычисления fib (что и требовалось для опровержения Вашего тезиса). Что же касается того, существует она, или нет, то так уж случилось, что в математике не все доказательства существования конструктивны --- для того, чтобы убедиться в существовании иррациональных чисел "диагональным методом" Кантора вовсе не обязательно строить такое число до конца :-)

Во-вторых, раз уж мы углубились в дебри интересной науки под названием computer science, то давайте поступим в рамках общепринятых научных норм (обоснование утверждения ложится на его автора) и начнем с самого начала, с Вашего утверждения:

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

Раз уж Вы предлагаете утверждение, претендующее на общезначимость ("любой язык"), то сначала докажите его. Формально, в общем виде, подобно тому, как в общем виде доказывается нижний предел N * log(N) сложности сортировки сравнением ключей. Успехов в этом нелегком деле.

Ответ на »сообщение 599« (Geniepro)
___________________________

А ведь P4 2800 должен быть примерно в два раза быстрее, чем Celeron 1700 !
В том то и дело, что не должен. Во первых, при повышении частоты производительность растет нелинейно (к тому же 2800/1700 совсем не 2). А, во-вторых, у этих процессоров, скорее всего, еще и разная длина конвейера. Так что сравнивать на них скорость выполнения программ - совсем некорректно.

Ответ на »сообщение 598« (Geniepro)
___________________________
Хм, интересно... Повторил тесты Lisp Hobbyist'а:

(defun fib (n)
  (cond ((< n 3) 1)
        (t (+ (fib (1- n)) (fib (- n 2))))))

(defun fib-test (f)
  (loop for i in '(1 5 12 20 30 31 32)
    do (format t "~%~A -> ~A~%" i (time (funcall f i)))))

(fib-test #'fib)

Напомню, у него CLisp 2.33 и P4 2800, у меня CLisp 2.39 и Celeron 1700 - время выполнения почти совпало! разница - меньше 0.1 сек (в режиме интерпретации при запуске из оболочки)
А ведь P4 2800 должен быть примерно в два раза быстрее, чем Celeron 1700 !

CLisp 2.39 похоже сильно ускорен... Советую переходить на него... ;-)
Он выполняет программы в псевдокоде всего раз в 6 медленнее, чем чистый машинный код на Компонентном Паскале. А интерпретация исходного кода ещё в пять раз медленнее...

Да, я там раньше упоминал, что на Компонентном Паскале рекурсивный вариант ф-ции Фибоначчи при n=32 выполняется 1.36 сек. Оказывается, я тогда некоректный замер делал - определял ещё и сколько раз вызывается сама ф-ция. Эта лишняя операция сложения замедлила работу в 6 раз... На самом деле - 0.235 сек.

Кстати, C# выполняет эту ф-цию примерно в 2.5 раза быстрее, чем Компонентный Паскаль, и раз в 15 быстрее, чем CLisp 2.39 (псевдокод). Но это у меня так, на другом железе может быть и по другому...

Кстати, о переполнении стека в Дельфах. Я был сильно удивлён, когда

обнаружил, что рекурсивный QuickSort сдыхает на массиве со всего-то 20

тыс элементами, упорядоченными в обратном направлении...

Хотя там раньше где-то подсказывалось, как увеличить размер стека...
_____________

Эх, пытаюсь как-нить достать F# от Майкрософта, да что-то их сервак

глючит, не даёт мне ссылку на инсталлятор...

Люди добрые, помогите, если нетрудно, киньте рабочую ссылку, хочется

интегрировать ML в Студию...

Основная страница загрузки -

http://research.microsoft.com/fsharp/release.aspx

Но дальше окна с лицензией я пройти не могу - пишется про какую-то

ошибку сервера...

http://research.microsoft.com/research/downloads/download.aspx?FUID={70EB059F-DC3D-47E1-B8CA-9CED69F33C66}

Ответ на »сообщение 595« (Сварог)
___________________________

И пусть мне кто-то станет рассказывать, что рекурсия неудобно реализуется в Делфи


Рекурсия быстренько сдыхает в дельфи с переполнением стека. Пример я уже здесь приводил.

Что касается приведенных вами алгоритмов, то второй вариант таки труднее для понимания.
По крайней мере для меня. :))

Ответ на »сообщение 593« (Geniepro)
___________________________

Вряд ли стандартный Apache будет выполнять код на Лиспе или Окамле?


Ну стандартный Апач и PHP не выполняет. :)) Для этого используется плагин mod_php
Соответственно в случае с лиспом mod_lisp
Ну или можно воспользоваться одним из opensource лисп web серверов. AllegroServe, Araneida, LightHttpD

Ответ на »сообщение 594« (Сварог)
___________________________

function fib1(n :integer) :integer;
begin
    if (n<3) then
    begin
          Result := 1;
    end
              else
          Result := fib1(n-1) + fib1(n-2);
end;

и

function fib2(n :integer) :integer;
var
  i, k1, k2, k :integer;
begin
    k1 := 1;
    k2 := 1;
    k := 1;
    for i := 2 to n-1 do
    begin
          k := k2+k1;
          k1 := k2;
          k2 := k;
    end;
    Result := k;
end;

И пусть мне кто-то станет рассказывать, что рекурсия неудобно реализуется в Делфи или что второй вариант реализации функции труднее для понимания, чем первый :)))))))))))))))))

Ответ на »сообщение 593« (Geniepro)
___________________________


А как выполняются веб-программы с использованием этих библиотек на ФЯ?
Ведь для них, наверное, нужны какие-то специализированные веб-серверы?
Вряд ли стандартный Apache будет выполнять код на Лиспе или Окамле?
А уж от веб-браузеров и подавно не дождётесь... :-)

Гм... я почему-то всегда думал, что библиотеки выполняет ОС компьютера, а не Apache или веб-браузер...

Ответ на »сообщение 592« (Jack Of Shadows)
___________________________

Второй пример: императивный, трудный для чтения, записи и понимания. В миллионы раз более быстрый при исполнении.


Да, совершенно верно. Хотелось бы ещё добавить, что в таких алгоритмах легко совершить ошибку.
Ряд чисел Фибонначи выглядит ведь так:

1, 1, 2, 3, 5, 8, 13, ...

для значений n (соответственно):

1, 2, 3, 4, 5, 6, 7, ...

Ваша же функция (итеративная) даёт ряд:

1, 2, 3, 5, 8, 13, 21, ...

для тех же n.
Не хотелось бы показаться невежливым, но, по-моему, Ваша функция должна выглядеть так:

(defun fib (n)
  (declare (integer n))
  (loop repeat n
        for f  of-type integer = 0 then (+ f0 f1)
        for f0 of-type integer = 0 then f1
        for f1 of-type integer = 1 then f
        finally (return f)))

PS. Кстати, а зачем Вы поставили (1+ n) вместо n? ;-)
_____________________

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

Ну, не всегда... Вот вспомните опять тот алгоритм Queens, приведённый Trurl'ем - он ведь выполнен в чисто рекурсивном стиле - и понять его не так то просто. А попытка повторить его на Паскале или Си, имхо, обречена на провал...
Хотя, впрочем, итеративный вариант этого же алгоритма ничуть не проще для восприятия...
А ведь это очень простая задачка...
_____________________

Так что те кому требуется делать web приложения - советую обратить пристальное внимание на web библиотеки лиспа, окамла, питона и руби.
Это шанс не просто поигратсья, а на деле работать с ФЯ.

А как выполняются веб-программы с использованием этих библиотек на ФЯ?
Ведь для них, наверное, нужны какие-то специализированные веб-серверы?
Вряд ли стандартный Apache будет выполнять код на Лиспе или Окамле?
А уж от веб-браузеров и подавно не дождётесь... :-)