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

Всё таки, ФП не освобождает о необходимости думать оо оптимальных алгоритмах...


Эту мысль наверное надо 1000 раз повторить. Уж сколько я говорил что ФЯ наиболее удалены от машины, то есть все ФЯ алгоритмы это алгоритмы в которых мыслит человек а не машина.
Они предназначены для прогона на гипотетическом идеальном компьютере.
А современные машины весьма далеки от такого идеала.
Поэтому чистые функциональные алгоритмы всегда будут медленнее специально переписанных под недостатки современного железа.

Поэтому чисто функциональная запись алгоритма чисел Фибоначи, всегда будет тормозить по сравнению с итерационной.
Хотя для человека в 10 раз легче прочитать рекурсивный алгоритм фибоначи нежели эту головоломку из 3 вложенных циклов.

Сравните:

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

и

(defun fib (n)
  (declare (integer n))
  (loop repeat (1+ 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)))

Первый пример: функциональный, легкий для чтения, записи, и понимания. Медленный при исполнении.
Второй пример: императивный, трудный для чтения, записи и понимания. В миллионы раз более быстрый при исполнении.

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

К счастью прогресс в процессорах и памяти привел сегодня к тому что во все большем количестве задач мы можем позволить себе заплатить скоростью исполнния, и заполучить легкость записи и чтения алгоритмов.
Не всегда, не везде, но с каждым днем во все большем и большем количестве случаев.
Так например прикладные задачи (особенно web development) уже давно в пределах досягаемости ФЯ (в терминах эффективности исполнения конечно). То есть несмотря на то что ФЯ будут медленнее при исполнении, их скорость все равно выше чем скорость других элементов системы (а именно интернет соединение).

Именно с этой области начинается внедрения ФП в широкие массы.
Во первых - задачи web некритичны по скорости для языка. (Другие элементы системы все равно медленнее)
Во вторых - нет GUI, то есть нет загвоздки в отсутствии визуальных инстурментов для построения GUI, что является главной проблемой для использования ФЯ на практике сегодня.

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

Я использую простенькую лисповую библиотеку WebActions.
Ну и сейчас присматриваюсь к другой библиотеке UCW.
Уж очень она крутая :))

fib 1000
4346655768693745643568852767504062580256466051737178040248172908953655
5417949051890403879840079255169295922593080322634775209689623239873322
471161642996440906533187938298969649928516003704476137795166849228875


Да, честно говоря, не привычно работать с такими числами. Обычные языки ведь не поддерживают такую арифметику, хотя тот же Алгол-68 - поддерживает:

PR precision=200 PR

INT n = 1000;

LONG LONG INT f, f1, f2;

IF n < 3 THEN f := 1
ELSE
  f1 := 1; f2 := 1; f := f1 + f2;
  FROM 3 TO n DO
    f := f1 + f2; f2 := f1; f1 := f
  OD
FI;

print (("fib(", n, ") = ", new line, f))

fib(      +1000) =
        +4346655768693745643568852767504062580256466051737178040248172908
9536555417949051890403879840079255169295922593080322634775209689623239873
322471161642996440906533187938298969649928516003704476137795166849228875

Как и сборку мусора...

И почему Алгол-68 был незаслужено забыт?.. :-(
Всё-таки это не столько язык программирования, сколько алгоритмический язык... :-)

Дамс, попробовал я Visual Haskell - http://www.haskell.org/visualhaskell/VHS.msi

Предназначен для интеграции GHC в Visual Studio 2003 (7.1), однако о номере версии VS на сайте ничего не было сказано. У меня стоит VS 2005 (8.0) и Visual Haskell не захотел в неё интегрироваться.
А жаль - на скриншоте всё так красиво выглядит... :-(
Зря три часа закачивал, эх...:-((

(Такая же лажа у меня и с компилятором Зоннона вышла - ему тоже нужна VS 2003 и в VS 2005 он не пашет :-(( )

Однако в комплекте Visual Haskell всё-таки есть GHC pre-relise 6.5. Попробовал скомпилить им рекурсивный вариант Фибоначчи - чудо не состоялось! Время выполнения зависит так же, экспоненциально...

Всё таки, ФП не освобождает о необходимости думать оо оптимальных алгоритмах... ;-)

Просьба к модераторам!

Пожалуйста поправьте мой предыдущий пост - »сообщение 588« (Geniepro)

Разбейте, если не трудно, число

4346655768693745...

на три строки, а то как-то неудобно вышло... :-(

Заранее спасибо!

Ответ на »сообщение 581« (Lisp Hobbyist)
___________________________

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


Кстати, да, время вычисления у Jack'а апроксимируется формулой

time = 4,047e-8*exp( 0,477*n)

а количество вызовов самой себя в рекурсивной ф-ции Фибоначчи - формулой

ncall = 0,449*exp( 0,481*n)

Показатель степени практически одинаковый!
То есть, хоть и очень быстро, но тоже рекурсивно, без преобразования в итерацию...
________________________

Вариант Trurl'а должен выглядеть так:

fib n = fibs!!n
  where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

fib 1000
434665576869374564356885276750406258025646605173717804024817 290895365554179490518904038798400792551692959225930803226347 7520968962323987332247116164299644090653318793829896964 9928516003704476137795166849228875

Теперь правильно. С единицей вместо нуля ряд идёт со сдвигом - вычисляется следующее число Фибоначчи...

Ответ на »сообщение 582« (Max Belugin)
___________________________
Что вообще отказываются от отношения частное-общее?
Нет, никто не отказывается. Просто для этого используются другие механизмы - type classes в хаскеле.
Вот тут есть небольшая глава  Haskell vs OOP  http://haskell.org/haskellwiki/Why_Haskell_matters
где это обьясняется.

Ответ на »сообщение 585« (Lisp Hobbyist)
___________________________

О чем и шла речь в изначальном вопросе: сможет ли Лисп-система сотворить чудо и оптимизировать такой код?


Некорректный наезд.
Во первых НИ ОДИН язык не сможет вам сотворить чудо и моментально выполить приведенный вами алгоритм на больших числах.
Опять спрашиваю, при чем тут лисп ?
Приведите результаты любого языка, включая хаскель на этом алгоритме.
Если приведете сильно отличающийся результат - признаю свою ошибку и соглашусь с вами.
Но требовать от лиспа оптимизации того что не может быть оптимизированно НИ НА ОДНОМ ДРУГОМ ЯЗЫКЕ! - это перебор.

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

Во вторых компилятор лиспа таки соптимизировал исполнение этого алгоритма, причем весьма существенно. Цифры я приводила. Вы просили пример оптимизации компилятором - я его привел. Соптимизировано беле чем в 10 раз!!
Конечно не в миллион раз, как вы требовали (ЧУДА!!) Вполне на уровне любого другого компилятора.
Если это не так - приведите результаты другого языка, другого компилятора.

Как можно наезжать на язык и требовать от него ЧУДА (то есть того что никто больше делать не может) я не понимаю.


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


Опровергайте. Об этом я вас уже в третий раз наверное прошу :))
Идентичную запись на хаскеле того алгоритма который вы гоняли на лиспе, я привел.
Компилируйте, прогоняйте и результаты в студию.
Но вот только заменять ее на другой алгоритм фибоначи не надо.
Или если заменяете, тогда уж повторите замеры на лиспе с новым алгоритмом тоже (что вы кстати уже проделали) Результат одинаковый.
При чем тут лисп ? При чем тут оптимизация компилятора?

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

Приведенная вами функция на цифрах более 50 сдыхает. Однако какое это имеет отношение к производительности лиспа ? Это особенности конкретно этого алгоритма.

О чем и шла речь в изначальном вопросе: сможет ли Лисп-система сотворить чудо и оптимизировать такой код? Я так и ответил, что не может, приведя, для наглядности, соотв. время исполнения. Но вслед за этим появляется Ваше  »сообщение 569«, что компиляция ускоряет выполнение этой программы с таким выводом:

Как видите все в порядке с оптимизацией рекурсии в лиспе :))

Как прикажете это понимать? Зачем было публиковать эти данные, зная о том, что все равно с ростом величины аргумента никакая компиляция уже не поможет и на самом деле никакой оптимизации здесь нет?

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

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

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

Ответ на »сообщение 581« (Lisp Hobbyist)
___________________________
Ваши наездя на меня безосновательны.

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


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


Во-вторых, говоря о ФП, Вы почему-то упорно сводите его к Лиспу.


Вы ошибаетесь, я не свожу ФП к лиспу, я рассматриваю ФП на примере лиспа. То есть на примере того ФЯ которым я пользуюсь на практике.
Если вы или кто то другой имеет опыт работы на других ФЯ, я буду только рад у вас поучиться.
Много раз говорил и еще раз повторяю. Это не моя личная трибуна, и не тема о лиспе.
Это тема о ФЯ, и не моя вина что практически только я активно в ней учавствую.
Если бы вместе со мной здесь говорили программисты хаскеля и окамла, впечатления узурпирования темы лиспом у вас не сложилось бы. Но опять же - это не моя вина. Я в меру своих ничтожных знаний пытаюсь упомянуть хаскель в тех случаях, когда этого требует контекст.


Дело в том, что существенную часть стандарта ANSI Common Lisp занимают сугубо императивные средства.


Говорилось.

Как следствие, разработчики компиляторов просто не в состоянии реализовать все те оптимизации, которые могут себе позволить разработчики реализаций чистых ФП-языков.

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


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


Практически повторили то что я вынес в заголовок темы :))
И хотя глупо приводить цитатц из ЗАГОЛОВКА ТЕМЫ, но мне уже ничего другого не остается.
Читайте:

Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.


Далее.

Но рекламировать Лисп в контексте чистого ФП - некорректно


Опять вы на меня безосновательно наезжаете. В свете всего вышесказанного, я надеюсь понятно что ни о каком чистом AG в лиспе и речи не идет. В конце концов в приведенной вами функции фибоначи используется LOOP :))


Во-вторых, Jack, я же просил выдать мне результаты измерений для куда больших чисел, например, для 100, 200 или 1000. Что-то мне подсказывает, что это неспроста.


Конечно неспроста. Приведенная вами функция на цифрах более 50 сдыхает. Однако какое это имеет отношение к производительности лиспа ? Это особенности конкретно этого алгоритма.
В конце концов вы сами только что привели пример другого алгоритма фибоначи. И он отрабатывает моментально.

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

Для чтобы не быть голословным:

Приведенный вами алгоритм фибоначи на лиспе:

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

Аналогичный алгоритм на хаскеле:

fibb (0) = 1
fibb (1) = 1
fibb (n) = fibb (n - 2) + fibb (n - 1)

Запускаете и наслаждаетесь бесконечным ожиданием.
Так при чем тут лисп ?

Ответ на »сообщение 581« (Lisp Hobbyist)
___________________________
>>> Почему это отличается от результата Trurl --- не знаю. :-)

Ну, это легко устранить. :-)

> fib 999 
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875