Михаил Ильин (yorool_gui) wrote,
Михаил Ильин
yorool_gui

скорость вычисления факториала - наш ответ Чемберлену

Сергей Кищенко сравнил скорость работы разных языков, включая Haskell на примере вычисления факториала. Разумеется, он совершил классическую ошибку, записав факториал в рекурсивной форме, из-за чего результат для Haskell получился много хуже, чем мог бы быть. По катом правильный вариант:
module Main where

import System.CPUTime
import System.Environment
import Text.Printf
import Data.List

time a = do
    start <- getCPUTime
    res <- a
    end   <- getCPUTime
    let diff = (fromIntegral (end - start)) / (10^12)
    return (res,diff::Double)

fac' 0 _ = error "called with 0? (actually, forcing (res*n))" -- спасибо thesz 
fac' res 0 = res
fac' res n = fac' (res*n) (n-1)

fac_tail n = fac' 1 n

fac_simple n = if n == 0 then 1 else n * fac_simple (n-1)

fac_foldl n = foldl1' (*) [1..n]

main = do
    count <- getArgs >>= (return.read.head)
    putStrLn "Starting..."
    (_,t1) <- time $ return $! (fac_tail count)
    printf "fac_tail: %0.3f sec\n" t1
    (_,t2) <- time $ return $! (fac_foldl count)
    printf "fac_foldl: %0.3f sec\n" t2
    (_,t3) <- time $ return $! (fac_simple count)
    printf "fac_simple: %0.3f sec\n" t3
    putStrLn "Done."


И вот собственно результат:

D:\haskell\fac>fac.exe 200000
Starting...
fac_tail: 54.547 sec (вариант с хвостовой рекурсией)
fac_foldl: 45.875 sec (вариант через foldl1' - foldl c форсированным вычислением)
fac_simple: 251.547 sec (наивный, рекурсивный вариант)
Done.
Subscribe

  • 2048 on Rust/WinRT

    Микрософт выкатила библиотеку для работы с Windows Runtime для Rust — Rust/WinRT. И, похоже, будет ее поддерживать. Сделана она так же, как и…

  • GUI на Rust - есть прогресс

    Приобрело работающий вид. Сейчас есть кнопки — две штуки внизу, чекбоксы и радиокнопки — наверху. Чекбоксы и радиокнопки — одно и…

  • GUI на Rust - мой подход к снаряду

    Выложил прототип GUI на Rust'e. Назвал, разумееется, yorool_gui :-) Пока умеет рисовать кнопки, нажимать кнопки и передавать сообщения между…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 19 comments

  • 2048 on Rust/WinRT

    Микрософт выкатила библиотеку для работы с Windows Runtime для Rust — Rust/WinRT. И, похоже, будет ее поддерживать. Сделана она так же, как и…

  • GUI на Rust - есть прогресс

    Приобрело работающий вид. Сейчас есть кнопки — две штуки внизу, чекбоксы и радиокнопки — наверху. Чекбоксы и радиокнопки — одно и…

  • GUI на Rust - мой подход к снаряду

    Выложил прототип GUI на Rust'e. Назвал, разумееется, yorool_gui :-) Пока умеет рисовать кнопки, нажимать кнопки и передавать сообщения между…