Решил протестировать производительность различных языков программирования на факториале от 50000, и вот что у меня получилось.
Scheme (racket 5.1) – 8s
Clojure 1.2 – 23s
Java 1.7 – 17s
Sbcl 1.0.43 – 7s
Ruby 1.9.2 -- 10s.
Parallel Clojure -- 3s.
Ruby 1.9.2 -- 10s.
Parallel Clojure -- 3s.
Функция на Clojure выглядит следующим образом.
(defn fact!
([num]
(fact! num 1))
([num result]
(if (zero? num)
result
(recur (dec num) (* result num)))))
Ответ на функцию (fact! 50000) не привожу, потому что он занимает в OpenOffice 52 страницы шрифтом Liberation Serif 12.
Вывод из этого эксперимента следующий: самый быстрый язык для вычислений с большими числами в одном потоке – это Common Lisp (sbcl). С/C++ в расчет не берем, т. к. в его стандарте вообще нет средств для работы с числами такого размера. Java более чем в два раза медленнее; реализация алгоритма факториала не через рекурсию, а с помощью цикла. Это связано с тем, что в Java нет оптимизации хвостовой рекурсии, и рекурсивная реализация на Java просто вылетает с ошибкой StackOverflow. Хотя все реализации осуществляют именно итеративный процесс.
Clojure на 35% медленее Java, но тоже, в принципе, достаточно быстр.
Racket, запущенный без дебужных опций, оказался тоже достаточно шустрым и справился с заданием всего за 8 секунд, заняв почетное второе место. На третьем месте -- Ruby 1.9.2.
По предложению Vinzent'а, решил протестировать еще и параллельную реализацию на Clojure. Учитывая, что "параллельность" в Clojure из коробки, сделать это оказалось очень просто. Vinzent прислал очень идиоматичный исходник, за что большое ему спасибо. Привожу его (исходник) ниже.
Результат вычислений был выше всяких похвал. Clojure справился с факториалом 50000 всего за 3 секунды!
(defn chunks [x n]
(take n
(partition 2 1
(iterate
(partial + (/ x n)) 1))))
(defn pfact [chunks]
(reduce * (pmap
(fn [[from to]]
(reduce * (range from to)))
chunks)))
(time (pfact (chunks 50000 10)))
Racket, запущенный без дебужных опций, оказался тоже достаточно шустрым и справился с заданием всего за 8 секунд, заняв почетное второе место. На третьем месте -- Ruby 1.9.2.
По предложению Vinzent'а, решил протестировать еще и параллельную реализацию на Clojure. Учитывая, что "параллельность" в Clojure из коробки, сделать это оказалось очень просто. Vinzent прислал очень идиоматичный исходник, за что большое ему спасибо. Привожу его (исходник) ниже.
Результат вычислений был выше всяких похвал. Clojure справился с факториалом 50000 всего за 3 секунды!
(defn chunks [x n]
(take n
(partition 2 1
(iterate
(partial + (/ x n)) 1))))
(defn pfact [chunks]
(reduce * (pmap
(fn [[from to]]
(reduce * (range from to)))
chunks)))
(time (pfact (chunks 50000 10)))
Yea, right. sbcl is a definitly way to go...
ОтветитьУдалитьf' :: Integer -> Integer -> Integer
f' 1 a = a
f' x a = f' (x - 1) (a * x)
main = print $ f' 50000 1
home% ghc --make -O2 fact.hs
home% time ./fact > /dev/null
./fact > /dev/null 0.28s user 0.01s system 98% cpu 0.292 total
home% time runhaskell fact.hs > /dev/null
runhaskell fact.hs > /dev/null 0.44s user 0.02s system 99% cpu 0.468 tota
main = print $ product [1..50000]
ОтветитьУдалитьhome% ghc --make -O2 fact2.hs && time ./fact2 > /dev/null
./fact2 > /dev/null 0.26s user 0.00s system 98% cpu 0.261 total
sbcl 1.0.45:
ОтветитьУдалить(defun factorial (x)
(labels ((helper (current accum)
(if (= current 1)
accum
(helper (1- current)
(* current accum)))))
(helper x 1)))
0.611 seconds of real time
0.612038 seconds of total run time (0.596037 user, 0.016001 system)
Для рекурсивной версии java можно -Xms поставить побольше.
ОтветитьУдалитьЭто не тест языков, это тест их библиотек для работы с большими целыми числами.
ОтветитьУдалитьScala оказалась быстрее Clojure выдает 21s.
ОтветитьУдалитьdream-x: Ну это еще от компьютера зависит. Я тестирую на Intel Core i5 430M (2.26GHz, 3Mb L3 cache), 4Gb Memory.
ОтветитьУдалитьКстати, что интересно, Ruby 1.9.2 справился с тестом за 10с.
Как обычно, забыли в Racket отключить debug mode и трассировку стека? У меня ~18 секунд Racket и Clojure, причем на аргументах до 40000 Racket стабильно вдвое быстрее. И да, там jit, а не интерпретатор.
ОтветитьУдалитьСхема не интерпретатор.
ОтветитьУдалитьПопробуйте посчитать на Factor'е
ОтветитьУдалить: factorial ( n -- n! )
[1,b] product ;
[ 50000 factor drop ] time
На моей Core i7 760QM (1.6GHz) считает за 1.4 секунды..
Поправочка:
ОтветитьУдалить: factorial ( n -- n! )
[1,b] product ;
[ 50000 factorial drop ] time
Gambit-C
ОтветитьУдалить$ cat fg.scm
(define (f n acc)
(if (= n 0)
acc
(f (- n 1) (* acc n))))
(with-output-to-file "f.txt" (lambda () (display (f 50000 1))))
...интерпретируем-интерпретируем...
$ time ./a.out
./a.out 2,30s user 0,02s system 99% cpu 2,325 total
$ wc -c f.txt
213237 f.txt
а почему факториал считается в одном трэде? ведь параллелится же "на ура"...
ОтветитьУдалитьVinzent: знаю, просто хотелось сделать типа как в математике n!
ОтветитьУдалитьAlkhimov: распараллеливание здесь ничего не покажет, достаточно просто посмотреть, как язык считает на одном треде.
Вот вариант на Racket, раз пошла такая пляска:
ОтветитьУдалить(define (fac n fn)
(define len (add1 (truncate (/ n fn))))
(apply *
(map (λ (x) (apply * x))
(for/list ([i (in-range (add1 fn))])
(for/list ([j (stop-before (in-range 1 (add1 len))
(λ (j) (> (+ j (* i len)) n)))])
(+ j (* i len)))))))