프로젝트 오일러와의 속도 비교 : C vs Python vs Erlang vs Haskell

질문 : 프로젝트 오일러와의 속도 비교 : C vs Python vs Erlang vs Haskell

---

저는 Project Euler 에서 문제 # 12 를 프로그래밍 연습으로 가져와 C, Python, Erlang 및 Haskell의 내 (최적은 아님) 구현을 비교했습니다. 더 높은 실행 시간을 얻기 위해 원래 문제에서 설명한 것처럼 500 대신 1000 이상의 제수가있는 첫 번째 삼각형 숫자를 검색합니다.

결과는 다음과 같습니다.

C:

lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c
lorenzo@enzo:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

파이썬 :

lorenzo@enzo:~/erlang$ time ./euler12.py 
842161320

real    1m16.632s
user    1m16.370s
sys 0m0.250s

PyPy를 사용한 Python :

lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 
842161320

real    0m13.082s
user    0m13.050s
sys 0m0.020s

Erlang:

 

lorenzo@enzo:~/erlang$ erlc euler12.erl 
lorenzo@enzo:~/erlang$ time erl -s euler12 solve
Erlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.4  (abort with ^G)
1> 842161320

real    0m48.259s
user    0m48.070s
sys 0m0.020s

Haskell :

lorenzo@enzo:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
lorenzo@enzo:~/erlang$ time ./euler12.hsx 
842161320

real    2m37.326s
user    2m37.240s
sys 0m0.080s

요약:

• C : 100 %
• Python : 692 % (PyPy 사용시 118 %)
• Erlang : 436 % (RichardC 덕분에 135 %)
• 하스켈 : 1421 %

나는 C가 다른 세 가지와 같이 임의의 길이 정수가 아닌 계산에 long을 사용하므로 큰 이점이 있다고 가정합니다. 또한 런타임을 먼저로드 할 필요가 없습니다 (다른 작업은 수행합니까?).

질문 1 : Erlang, Python 및 Haskell은 임의의 길이 정수를 사용하여 속도를 잃거나 값이 MAXINT 보다 작 으면 속도를 잃지 않습니까?

질문 2 : Haskell이 왜 그렇게 느린가요? 브레이크를 끄는 컴파일러 플래그가 있습니까 아니면 내 구현입니까? (하스켈이 나에게 일곱 개의 봉인이있는 책이기 때문에 후자는 꽤 가능성이있다.)

질문 3 : 요인을 결정하는 방식을 변경하지 않고 이러한 구현을 최적화하는 방법에 대한 힌트를 제공 할 수 있습니까? 어떤 방식 으로든 최적화 : 더 좋고, 더 빠르고, 더 "기본"언어.

편집하다:

질문 4 : 내 기능 구현이 LCO (마지막 호출 최적화, 꼬리 재귀 제거라고도 함)를 허용하므로 불필요한 프레임을 호출 스택에 추가하지 않습니까?

나는 Haskell과 Erlang에 대한 지식이 매우 제한적이라는 것을 인정해야하지만 4 개 언어로 가능한 한 비슷한 동일한 알고리즘을 구현하려고 노력했습니다.

---

사용 된 소스 코드 :

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square;
    int count = isquare == square ? -1 : 0;
    long candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

---

#! /usr/bin/env python3.2

import math

def factorCount (n):
    square = math.sqrt (n)
    isquare = int (square)
    count = -1 if isquare == square else 0
    for candidate in range (1, isquare + 1):
        if not n % candidate: count += 2
    return count

triangle = 1
index = 1
while factorCount (triangle) < 1001:
    index += 1
    triangle += index

print (triangle)

---

-module (euler12).
-compile (export_all).

factorCount (Number) -> factorCount (Number, math:sqrt (Number), 1, 0).

factorCount (_, Sqrt, Candidate, Count) when Candidate > Sqrt -> Count;

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

factorCount (Number, Sqrt, Candidate, Count) ->
    case Number rem Candidate of
        0 -> factorCount (Number, Sqrt, Candidate + 1, Count + 2);
        _ -> factorCount (Number, Sqrt, Candidate + 1, Count)
    end.

nextTriangle (Index, Triangle) ->
    Count = factorCount (Triangle),
    if
        Count > 1000 -> Triangle;
        true -> nextTriangle (Index + 1, Triangle + Index + 1)  
    end.

solve () ->
    io:format ("~p~n", [nextTriangle (1, 1) ] ),
    halt (0).

---

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' number sqrt candidate count
    | fromIntegral candidate > sqrt = count
    | number `mod` candidate == 0 = factorCount' number sqrt (candidate + 1) (count + 2)
    | otherwise = factorCount' number sqrt (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

답변

---

x86_64 Core2 Duo (2.5GHz) 시스템에서 GHC 7.0.3 , gcc 4.4.6 , Linux 2.6.29 사용, Haskell의 경우 ghc -O2 -fllvm -fforce-recomp , C의 경우 gcc -O3 -lm

• C 루틴은 8.4 초 안에 실행됩니다 ( -O3 때문에 실행하는 것보다 빠름)
• Haskell 솔루션은 36 초만에 실행됩니다 ( -O2 플래그로 인해).
• 귀하의 factorCount' 코드는 명시 적으로 입력되지 않았고 Integer 기본 설정되어 있습니다 (여기에서 오진을 수정 한 Daniel에게 감사드립니다!). Int 사용하여 명시 적 형식 서명 (어쨌든 표준 방식)을 제공하고 시간이 11.1 초로 변경됩니다.
• factorCount' 에서 불필요하게 fromIntegral 호출했습니다. 그러나 수정 사항은 변경되지 않습니다 (컴파일러는 똑똑하고 운이 좋습니다).
• rem 이 더 빠르고 충분한 mod 사용했습니다. 이렇게하면 시간이 8.5 초로 변경됩니다.
• factorCount' 는 변경되지 않는 두 개의 추가 인수 ( number , sqrt )를 지속적으로 적용합니다. 작업자 / 래퍼 변환은 다음을 제공합니다.

$ time ./so
 842161320  

 real    0m7.954s  
 user    0m7.944s  
 sys     0m0.004s

맞습니다. 7.95 초 . C 솔루션보다 지속적으로 0.5 초 더 빠릅니다 . -fllvm 플래그가 8.182 seconds 경우에도 NCG 백엔드가 잘 작동합니다.

결론 : Haskell은 굉장합니다.

결과 코드

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
  where
  go candidate count
    | candidate > sqrt = count
    | number `rem` candidate == 0 = go (candidate + 1) (count + 2)
    | otherwise = go (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

편집 : 이제 우리가 그것을 탐구 했으므로 질문에 답해 보겠습니다.

질문 1 : erlang, python 및 haskell은 임의의 길이 정수를 사용하여 속도를 잃거나 값이 MAXINT보다 작 으면 속도를 잃지 않습니까?

Haskell에서 Integer Int 보다 느리지 만 수행되는 계산에 따라 얼마나 느려지는지에 따라 다릅니다. 다행히 (64 비트 머신의 경우) Int 이면 충분합니다. Int64 또는 Word64 를 사용하도록 내 코드를 다시 작성해야합니다 long 가진 유일한 언어가 아닙니다).

질문 2 : 하스켈이 왜 그렇게 느린가요? 브레이크를 끄는 컴파일러 플래그가 있습니까 아니면 내 구현입니까? (하스켈은 나에게 일곱 개의 봉인이있는 책이기 때문에 후자는 꽤 가능성이 있습니다.)

질문 3 : 요인을 결정하는 방식을 변경하지 않고 이러한 구현을 최적화하는 방법에 대한 힌트를 제공 할 수 있습니까? 어떤 방식 으로든 최적화 : 더 좋고, 더 빠르고, 더 "기본"언어.

그것이 내가 위에서 대답 한 것입니다. 대답은

• -O2 를 통한 최적화 사용
• 1) 가능하면 빠른 (특히 : unbox-able) 유형 사용
• 2) rem not mod (자주 잊혀진 최적화)
• 3) 작업자 / 래퍼 변환 (아마 가장 일반적인 최적화).

질문 4 : 기능 구현이 LCO를 허용하므로 불필요한 프레임을 호출 스택에 추가하지 않습니까?

네, 그게 문제가 아닙니다. 수고하셨습니다.

출처 : https://stackoverflow.com/questions/6964392/speed-comparison-with-project-euler-c-vs-python-vs-erlang-vs-haskell