Программирование под linux

[marvin]

Надеюсь, не грех похвастаться. :-) Nemerle. Во второй функции используется макрос Memoize, реализующий соответствующую оптимизацию.

Код:

using Nemerle;
using System;
using System.Diagnostics;

namespace Fibonacci
{
  module Main
  {
    static Fib1(n : int) : int
    {
      | 0 => 0
      | 1 => 1
      | _ => Fib1(n - 1) + Fib1(n - 2)
    }
    
    [Memoize]
    static Fib2(n : int) : int
    {
      | 0 => 0
      | 1 => 1
      | _ => Fib2(n - 1) + Fib2(n - 2)
    }
    
    static TestFib(fib : int -> int) : void
    {
      def sw = Stopwatch();
      sw.Start();
      
      def result = fib(46);
      
      sw.Stop();
      
      Console.WriteLine($"Result: $result Time: $(sw.Elapsed.TotalSeconds)");
    }
    
    public static Main() : void
    {
      TestFib(Fib1);
      TestFib(Fib2);
    }
  }
}

Вывод:
Result: 1836311903 Time: 62,7802466
Result: 1836311903 Time: 0,0022332

[mini_root]

Надеюсь, не грех похвастаться. :-) Nemerle. Во второй функции используется макрос Memoize, реализующий соответствующую оптимизацию.

Код:

using Nemerle;
using System;
using System.Diagnostics;

namespace Fibonacci
{
  module Main
  {
    static Fib1(n : int) : int
    {
      | 0 => 0
      | 1 => 1
      | _ => Fib1(n - 1) + Fib1(n - 2)
    }
    
    [Memoize]
    static Fib2(n : int) : int
    {
      | 0 => 0
      | 1 => 1
      | _ => Fib2(n - 1) + Fib2(n - 2)
    }
    
    static TestFib(fib : int -> int) : void
    {
      def sw = Stopwatch();
      sw.Start();
      
      def result = fib(46);
      
      sw.Stop();
      
      Console.WriteLine($"Result: $result Time: $(sw.Elapsed.TotalSeconds)");
    }
    
    public static Main() : void
    {
      TestFib(Fib1);
      TestFib(Fib2);
    }
  }
}

Вывод:
Result: 1836311903 Time: 62,7802466
Result: 1836311903 Time: 0,0022332

Ну и? Смотрим условие, используется РЕКУРСИВНОЕ вычисление, а не оптимизированное итеративное (а это оно и есть, ведь так?). Итеративное везде быстро считается, там один цикл и нет ветвящейся рекурсии. Так что смотрим на первое число - 62 секунды.

P.S. Можно поподробнее, что именно делает Memoize? Явно превращает рекурсию в цикл?

[marvin]

P.S. Можно поподробнее, что именно делает Memoize? Явно превращает рекурсию в цикл?

Нет. Всего лишь кеширует результаты вызовов функции Fib2, тупо не вычисляя всё по несколько раз.

[mini_root]

P.S. Можно поподробнее, что именно делает Memoize? Явно превращает рекурсию в цикл?

Нет. Всего лишь кеширует результаты вызовов функции Fib2, тупо не вычисляя всё по несколько раз.

Я правильно понял - запоминается {имя функции, аргументы, результат} и при совпадении имени и аргументов сразу возвращается результат?

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

P.S. Но вообще прикольно, только что сам набросал примерчик, можно писать в функциональном стиле не теряя в производительности. О сколько нам открытий чудных готовит просвещения дух!

[konsoletyper]

Вот как то же на Хаскелле:

Код:

import IO
import CPUTime
import Numeric

fib = 1 : 1 : [a + b | (a, b) <- zip fib (tail fib)]

main = do
  putStrLn (show (fib!!46))
  time <- getCPUTime
  putStrLn (showFFloat (Just 6) (fromInteger time / 1e12) "")

Скомпилированный GHC код отработал 0.015625 секунд. Определение списка fib взял из Gentle Introduction. Заметьте, что это весьма лаконичное определение списка чисел Фибоначчи. А секрет быстрой работы в том, что во-первых, функция линеаризуется и раскручивается в цикл, а во-вторых, с помощью deforestation ликвидируется создание промежуточных структур. И никаких memoize не нужно.

Кстати, в отличие от всяких C, Nemerle и проч. данный вариант справится и с fib!!460 и даже с fib!!46000 (в этом случе код отрабатывает за 1.5 сек, вопреки ожиданиям :-) )

[mini_root]

Вот как то же на Хаскелле:

Код:

import IO
import CPUTime
import Numeric

fib = 1 : 1 : [a + b | (a, b) <- zip fib (tail fib)]

main = do
  putStrLn (show (fib!!46))
  time <- getCPUTime
  putStrLn (showFFloat (Just 6) (fromInteger time / 1e12) "")

Скомпилированный GHC код отработал 0.015625 секунд. Определение списка fib взял из Gentle Introduction. Заметьте, что это весьма лаконичное определение списка чисел Фибоначчи. А секрет быстрой работы в том, что во-первых, функция линеаризуется и раскручивается в цикл, а во-вторых, с помощью deforestation ликвидируется создание промежуточных структур. И никаких memoize не нужно.

Кстати, в отличие от всяких C, Nemerle и проч. данный вариант справится и с fib!!460 и даже с fib!!46000 (в этом случе код отрабатывает за 1.5 сек, вопреки ожиданиям :-) )

Мастер! Что еще сказать.... Я хаскелл так и не осилил пока перебиваюсь быдлоскалой...

P.S. Маленькое замечание, первым элементом списка должен быть 0.

Можно мелкий вопрос?:
fib = 0 : 1 : [a + b | (a, b) <- zip fib (tail fib)] - первые два элемента заданы явно, а третий и последующие как сумма a и b, где а и b берутся из конца списка. Я правильно понял? И еще, где указывается что нужно брать ДВА последних элемента из списка (я имею в виду конструкцию tail fib)?

[konsoletyper]

Мастер! Что еще сказать.... Я хаскелл так и не осилил пока перебиваюсь быдлоскалой...

P.S. Маленькое замечание, первым элементом списка должен быть 0.

Нет, 1 :-)

Можно мелкий вопрос?:
fib = 0 : 1 : [a + b | (a, b) <- zip fib (tail fib)] - первые два элемента заданы явно, а третий и последующие как сумма a и b, где а и b берутся из конца списка. Я правильно понял? И еще, где указывается что нужно брать ДВА последних элемента из списка (я имею в виду конструкцию tail fib)?

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

Вот по аналогии сочинил список факториалов (вообще, его можно где угодно найти):

Код:

fac = 1 : [a * b | (a, b) <- zip fac [1..]]

Следует читать как "список факториалов - это список начинающийся с единицы, а далее - из произведений элементов списков факториалов и натуральных чисел". Вначале вычисляется первый элемент - 1. Затем - второй по list comprehension, как произведение первого элемента fac (который 1) и первого натурального числа, т.е. 1. Третий элемент - это произведение второго элемента списка fac (тоже 1) и второго натурального числа. И так далее.

[mini_root]

Вот как то же на Хаскелле:

Код:

import IO
import CPUTime
import Numeric

fib = 1 : 1 : [a + b | (a, b) <- zip fib (tail fib)]

main = do
  putStrLn (show (fib!!46))
  time <- getCPUTime
  putStrLn (showFFloat (Just 6) (fromInteger time / 1e12) "")

Скомпилированный GHC код отработал 0.015625 секунд. Определение списка fib взял из Gentle Introduction. Заметьте, что это весьма лаконичное определение списка чисел Фибоначчи. А секрет быстрой работы в том, что во-первых, функция линеаризуется и раскручивается в цикл, а во-вторых, с помощью deforestation ликвидируется создание промежуточных структур. И никаких memoize не нужно.

Кстати, в отличие от всяких C, Nemerle и проч. данный вариант справится и с fib!!460 и даже с fib!!46000 (в этом случе код отрабатывает за 1.5 сек, вопреки ожиданиям :-) )

Сделал свой аналог на скале:
def fib(_n : BigInt): List[BigInt] =
 {
  if (_n ==0 ) {List[BigInt](0);}
  else if ( _n == 1 ) {List[BigInt](1,0);}
  else {val l = fib(_n-1); List[BigInt](l.head + l.tail.head) ::: l;}
 }

val startTm : long = System.currentTimeMillis();
Console.println(fib(460).head);
val endTm : long = System.currentTimeMillis();
Console.println("Total time: "+(endTm - startTm));

Результат:

60929766364353089279195197999021720669389417532925504644464121947359
6270869815908465388209600595
Total time: 29


Впрочем, это по сути тот же Memoize - то же сохранения результатов

[mini_root]

Мастер! Что еще сказать.... Я хаскелл так и не осилил пока перебиваюсь быдлоскалой...

P.S. Маленькое замечание, первым элементом списка должен быть 0.

Нет, 1 :-)

странно, в том же SICP:
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Понятно, что 0 ни на что не влияет, но все же

[konsoletyper]

Мой пример вычисляет fib!!460 за 0.031 сек, т.е всего на две миллисекунды дольше :-)

[mini_root]

Мой пример вычисляет fib!!460 за 0.031 сек, т.е всего на две миллисекунды дольше :-)

Усреднил:
def fib(_n : BigInt): List[BigInt] =
 {
  if (_n ==0 ) {List[BigInt](0);}
  else if ( _n == 1 ) {List[BigInt](1,0);}
  else {val l = fib(_n-1); List[BigInt](l.head + l.tail.head) ::: l;}
 }

var midTm : long = 0L;
for (val i<-1 to 10)
 {
  val startTm : long = System.currentTimeMillis();
  Console.println(fib(460).head);
  val endTm : long = System.currentTimeMillis();
  Console.println("Total time: "+(endTm - startTm));
  midTm = midTm + (endTm-startTm);
 }
Console.println("Mid time: "+(midTm/10.0));

Результат:
........
Total time: 6
609297663643530892791951979990217206693894175329255046444641219473596270869815908465388209600595
Total time: 8
Mid time: 18.2

P.S. JIT рулит

[mini_root]

Результат:
........
Total time: 6
609297663643530892791951979990217206693894175329255046444641219473596270869815908465388209600595
Total time: 8
Mid time: 18.2

P.S. JIT рулит

Ну и наконец:
усредняем по 1000 отсчетов

.......
60929766364353089279195197999021720669389417532925504644464121947
3596270869815908465388209600595
Total time: 1
60929766364353089279195197999021720669389417532925504644464121947
3596270869815908465388209600595
Total time: 4
60929766364353089279195197999021720669389417532925504644464121947
3596270869815908465388209600595
Total time: 0
Mid time: 2.563


P.S. JIT немерянно рулит
P.P.S. А с другой стороны, кому нахрен эти миллисекунды нужны .... Щас вот поставил себе в виртуалбоксе  студию 2005 и 1с8 - буду скрещать ужа с ежом

[Леголегс]

Ну и ничего! Во-первых ты конфигу машинки не написал, а во-вторых за несколько секунд проигрыша я получаю полную переносимость и все плюшки, которые дает виртуальная машина. Что лишь подтверждает мои слова о преимуществе Java/.NET на реальных прикладных приложениях - там где надо работать с сеткой, файлами или БД. В них ты вообще разницы по скорости не увидишь, а плюшки управляемых языков останутся.

C2D 4300 2ггц машинка.
Насчёт переносимости: я убеждён, что переносимость у явы не намного больше, чем у си с плюсами. Неверящие 1) берут мой код на c++, компилируют и успешно исполняют 2) находят мне запускающуюся асю на мобильник 3) берут бинарь http://ftp://exchange.lipetsk.ru/incoming/home/ex02953/fibcpp и с удивлением запускают на своём дистре 4) дают мне свой бинарь с явой и он не работает с вероятностью 70%

[mini_root]

Ну и ничего! Во-первых ты конфигу машинки не написал, а во-вторых за несколько секунд проигрыша я получаю полную переносимость и все плюшки, которые дает виртуальная машина. Что лишь подтверждает мои слова о преимуществе Java/.NET на реальных прикладных приложениях - там где надо работать с сеткой, файлами или БД. В них ты вообще разницы по скорости не увидишь, а плюшки управляемых языков останутся.

C2D 4300 2ггц машинка.
Насчёт переносимости: я убеждён, что переносимость у явы не намного больше, чем у си с плюсами. Неверящие 1) берут мой код на c++, компилируют и успешно исполняют 2) находят мне запускающуюся асю на мобильник 3) берут бинарь http://ftp://exchange.lipetsk.ru/incoming/home/ex02953/fibcpp и с удивлением запускают на своём дистре 4) дают мне свой бинарь с явой и он не работает с вероятностью 70%

Окей, дай мне код, который реализует взаимодействие через CORBA, работу с любой произвольной БД, и скажем вызов веб сервисов + гую а я его попробую, но только чтобы компилялся сразу и под виндой под linuxом.
А под жабой легко, ключевые слова EJB, JDBC (Type 4 - драйверы на чистой жабе), Axis2, Swing. Например сервер приложений geronimo - немаленькая такая прожка, один и тот же что под винду что под linux (jboss аналогично). Или, например, Netbeans - довольно монстроузная IDE, а в бинах "сборки под linux" лежит рядом с  *.sh еще и *.exe - а это занчит что код то один и тот же, только запускалка разная. Причем заметь ничего не надо перекомпилировать - все переноситься в бинарниках. Так что переносимость под жабу ~100%, по крайней мере до тех пока ты не столкнешься с JNI.
Самое главное не надо пытаться запускать прогу скомпиленную JDK1.6u4 под жутким гнушным поделием gij.
P.S. За все вышесказанное я готов ответить, примеры - без проблем, если хочешь могу тебе закинуть на ftp jboss - ставишь жабу и он запускается и под виндой и под linuxом. Или сервер приложений для тебе слишком мелко?
P.P.S. А мобильники трогать не надо - это отдельная песня, за нее можешь сказать спасибо производителям железок, которые положили на стандарты.

[Леголегс]

Окей, дай мне код,

Ну, амарок. И т.д. Надо только правильный тулкит выбирать. Ты правда думаешь, что на цпп нельзя писать кроссплатформенно? И главное не это. Главное - производительность. Эклипс тормозил на четвёртом пне, тормозит и на коре. Несмотря на все чЮдесные jit и прочее. Работать некомфортно. Привыкнуть можно, но зачем, если есть шустрые программы?
PS ну и мне просто люботытно: бинарь запустился?