Программа на Haskell работает очень медленно - PullRequest
Новая
       9

Программа на Haskell работает очень медленно

2 голосов
/ 06 марта 2019

Я написал свою первую программу для вычисления простых чисел. Однако он работает очень медленно, и я не могу понять, почему. Я написал подобный код в java, и для n = 10000 java-программа не занимает много времени, в то время как программа на Haskell занимает около 2 минут. 

import Data.List
main = do
    print "HowManyPrimes? - OnlyInteger"
    inputNumber <- getLine
    let x = (read inputNumber :: Int)
    print (firstNPrimes x)

-- prime - algorithm
primeNumber:: Int -> Bool
primeNumber 2 = True
primeNumber x = primNumberRec x (div x 2)

primNumberRec:: Int -> Int -> Bool
primNumberRec x y
      |y == 0 = False
      |y == 1 = True 
      |mod x y == 0 = False
      |otherwise = primNumberRec x (y-1)

-- prime numbers till n
primesTillN:: Int -> [Int]
primesTillN n = 2:[ x | x <- [3,5..n], primeNumber x ]


--firstNPrimes
firstNPrimes:: Int -> [Int]
firstNPrimes 0 = []
firstNPrimes n = 2: take (n-1) [x|x <- [3,5..], primeNumber x]

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

Аналогичный код Java: 

import java.util.Scanner;
public class PrimeNumbers{

static Scanner scan = new Scanner(System.in);

public boolean primeAlgorithm(int x){
    if (x < 2)
        return false;
    return primeAlgorithm(x, (int)Math.sqrt(x));
}

public boolean primeAlgorithm(int x, int divider){
    if (divider == 1)
        return true;
    if (x%divider == 0)
        return false;
    return primeAlgorithm(x, divider-1);
}

public static void main(String[] args){

    PrimeNumbers p = new PrimeNumbers();
    int howManyPrimes = scan.nextInt();
    int number = 3;
    while(howManyPrimes!=0){
        if(p.primeAlgorithm(number)){
            System.out.print(number+" ");
            howManyPrimes--;
        }
        number+=2;
    }

}

}

Ответы [ 2 ]

9 голосов
/ 06 марта 2019

При выполнении измерений времени всегда компилируйте;ghci предназначен для быстрого цикла изменения-восстановления-запуска, а не для быстрого выполнения созданного кода.Однако даже после следования этому совету между вашими фрагментами есть огромная разница во времени.

Ключевое различие между вашим Java и Haskell заключается в использовании sqrt вместо деления на 2. Ваши оригиналы на моей машине: 

% javac Test.java && echo 10000 | /usr/bin/time java Test >/dev/null                             
0.21user 0.02system 0:00.13elapsed 186%CPU (0avgtext+0avgdata 38584maxresident)k
0inputs+0outputs (0major+5823minor)pagefaults 0swaps
% ghc -O2 test && echo 10000 | /usr/bin/time ./test >/dev/null
8.85user 0.00system 0:08.87elapsed 99%CPU (0avgtext+0avgdata 4668maxresident)k
0inputs+0outputs (0major+430minor)pagefaults 0swaps

Так 0,2 с для Java, 8,9 с для Haskell.После перехода к использованию квадратного корня со следующим изменением: 

- primeNumber x = primNumberRec x (div x 2)
+ primeNumber x = primNumberRec x (ceiling (sqrt (fromIntegral x)))

я получаю следующий тайминг для Haskell: 

% ghc -O2 test && echo 10000 | /usr/bin/time ./test >/dev/null
0.07user 0.00system 0:00.07elapsed 98%CPU (0avgtext+0avgdata 4560maxresident)k
0inputs+0outputs (0major+427minor)pagefaults 0swaps

Теперь в 3 раза быстрее, чем код Java.(И, конечно, есть значительно лучшие алгоритмы, которые сделают его еще быстрее.)

6 голосов
/ 06 марта 2019

Скомпилируйте!

Код на Haskell в GHCi далек от оптимизации;попробуйте скомпилировать его в двоичный файл с ghc -o prime prime.hs или даже лучше использовать -O2 оптимизацию.Однажды у меня был скрипт, который занимал 5 минут в GHCi, но несколько секунд после компиляции.

...