Вопросы Теги

Сравнение скорости вычисления простых чисел в Haskell и C

Первоначально я написал этот (грубый и неэффективный )метод вычисления простых чисел, чтобы убедиться, что нет никакой разницы в скорости между использованием «если -, то -иначе» по сравнению с охранниками в Haskell (. ] и нет никакой разницы! ). Но потом я решил написать программу на C для сравнения, и у меня получилось следующее (Haskell медленнее чуть более чем на 25%):

(Примечание. Я получил идею использования rem вместо mod, а также опции O3 в вызове компилятора из следующего поста:Об улучшении производительности Haskell по сравнению с C в тесте fibonacci micro -)

Haskell :Forum.hs

divisibleRec :: Int -> Int -> Bool
divisibleRec i j 
  | j == 1         = False 
  | i `rem` j == 0 = True 
  | otherwise      = divisibleRec i (j-1)

divisible::Int -> Bool
divisible i = divisibleRec i (i-1)

r = [ x | x <- [2..200000], divisible x == False]

main :: IO()
main = print(length(r))

C :main.cpp

#include 

bool divisibleRec(int i, int j){
  if(j==1){ return false; }
  else if(i%j==0){ return true; }
  else{ return divisibleRec(i,j-1); }
}

bool divisible(int i){ return divisibleRec(i, i-1); }

int main(void){
  int i, count =0;
  for(i=2; i<200000; ++i){
    if(divisible(i)==false){
      count = count+1;
    }
  }
  printf("number of primes = %d\n",count);
  return 0;
}

Результаты, которые я получил, были следующими:

Время компиляции

time (ghc -O3 -o runProg Forum.hs)
real    0m0.355s
user    0m0.252s
sys 0m0.040s

time (gcc -O3 -o runProg main.cpp)
real    0m0.070s
user    0m0.036s
sys 0m0.008s

и следующие времена работы:

Время работы в Ubuntu 32 бит

Haskell
17984
real    0m54.498s
user    0m51.363s
sys 0m0.140s


C++
number of primes = 17984
real    0m41.739s
user    0m39.642s
sys 0m0.080s

Меня очень впечатлило время работы Haskell. Однако мой вопрос заключается в следующем: :могу ли я что-нибудь сделать, чтобы ускорить программу haskell без:

  1. Изменение базового алгоритма (ясно, что значительное ускорение может быть достигнуто путем изменения алгоритма; но я просто хочу понять, что я могу сделать на стороне языка/компилятора для повышения производительности)
  2. Вызов компилятора llvm (, потому что он не установлен )

[РЕД. :Использование памяти]

После комментария Алана я заметил, что программа C использует постоянный объем памяти, в то время как программа Haskell медленно увеличивает объем памяти. Сначала я подумал, что это как-то связано с рекурсией, но ниже gspr объясняет, почему это происходит, и предлагает решение.Уилл Несс предлагает альтернативное решение, которое (, как и решение gspr ), также гарантирует, что память остается статической.

[РЕДАКТИРОВАТЬ :Сводка больших тиражей]

максимальное число протестированных :200 000:

(54,498 с/41,739 с )=Haskell на 30,5% медленнее

максимальное число протестированных :400 000:

3 м 31,372 с / 2 м 45,076 с = 211,37 с / 165 с =Haskell на 28,1% медленнее

максимальное число протестированных :800 000:

14 м 3,266 с / 11 м 6,024 с = 843,27 с / 666,02 с =Haskell на 26,6% медленнее

[РЕДАКТИРОВАТЬ :Код для Алана]

Это был написанный мной ранее код без рекурсии, который я протестировал на 200 000 :

#include 

bool divisibleRec(int i, int j){
  while(j>0){
    if(j==1){ return false; }
    else if(i%j==0){ return true; }
    else{ j -= 1;}
  }
}


bool divisible(int i){ return divisibleRec(i, i-1); }

int main(void){
  int i, count =0;
  for(i=2; i<8000000; ++i){
    if(divisible(i)==false){
      count = count+1;
    }
  }
  printf("number of primes = %d\n",count);
  return 0;
}

. Результаты для кода C с рекурсией и без нее следующие (для 800 000):

С рекурсией :11м6.024с

Без рекурсии :11м5.328с

Обратите внимание, что исполняемый файл занимает 60 КБ (, как показано в системном мониторе ), независимо от максимального числа, и поэтому я подозреваю, что компилятор обнаруживает эту рекурсию.

7
задан Community 23 May 2017 в 12:04
поделиться