프로젝트 오일러와의 속도 비교: C vs Python vs Erlang vs Haskell
Project Oiler의 문제 #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
Python:
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
해스켈:
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 % (Richard C 덕분에 135 %)
- 해스켈: 1421%
C는 다른 세 가지와 마찬가지로 임의의 길이의 정수가 아닌 긴 정수를 사용하기 때문에 큰 장점이 있다고 생각합니다.또한 먼저 실행 시간을 로드할 필요가 없습니다(다른 작업은?).
질문 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
「」를 사용합니다.GHC 7.0.3,gcc 4.4.6,Linux 2.6.29Duo(25x86_64 Core2 Duo(2.5)를 사용한 )의 경우, " ", "ghc -O2 -fllvm -fforce-recomp과 Haskell을 »gcc -O3 -lmC. 우 c 。
- 은 8안에 C 8.4초 때문에 ).
-O3) - 에 실행됩니다(Haskell "36" "" "에).
-O2flag를 합니다. - 의 ★★★★★★★★★★★★★★★★★.
factorCount'이 "Default"로 설정됩니다.Integer(어쨌든 입니다!)를 사용하여 시그니처를 합니다(어쨌든표준적인 프랙티스입니다.Int시간은 11.1초로 바뀝니다. factorCount'havefromIntegral수정해도 변경되지 않습니다(컴파일러는 스마트하고 운이 좋습니다).- 사용하셨습니다.
mod서 ''는rem더 빠르고 충분합니다.그러면 시간이 8.5초로 변경됩니다. factorCount'변경되지 하고 있습니다(변경하지 않습니다).number,sqrtworker/wrapper를
$ time ./so
842161320
real 0m7.954s
user 0m7.944s
sys 0m0.004s
맞아요, 7.95초입니다.C 솔루션보다 0.5초 빠릅니다.미포함-fllvmI get 내가 flag flag flag flag flag flag flag flag flag flag flag8.182 seconds이 경우에도 NCG 백엔드는 정상적으로 동작합니다.
결론:해스켈은 멋져요.
결과 코드
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을 합니다.IntegerInt하지만 얼마나 느린지는 계산 결과에 따라 달라집니다.도 (머신의 ) 6464비비64 （ 64 ）Int를 다시 쓰는 것이 것 .Int64 ★★★★★★★★★★★★★★★★★」Word64가 있는 언어는 .long를 참조해 주세요.
질문 2: Haskell은 왜 이렇게 느립니까?브레이크를 끄는 컴파일러 플래그가 있습니까?아니면 실장되어 있습니까?(후자는 해스켈이 7개의 도장이 찍힌 책이기 때문에 가능성이 높습니다.)
질문 3: 요인 결정 방법을 변경하지 않고 이러한 구현을 최적화하는 방법에 대해 힌트를 주시겠습니까?어떤 방식으로든 최적화: 언어에 맞게 더 좋고, 더 빠르고, 더 '원어민'합니다.
그것은 내가 위에서 대답한 것이다.정답은
- 0을 통한 사용 (0)
-O2 - 1) 가능한 한 고속 타입(특정: 박스 불가능)을 사용한다.
- 2)
remmod잊어버리는 및 ('최적화') - 3) 작업자/직원의 변환(가장 일반적인 최적화).
질문 4: 기능 실장에서는 LCO가 허용되어 불필요한 프레임이 콜스택에 추가되는 것을 피할 수 있습니까?
네, 그게 문제가 아니었어요.수고하셨습니다. 검토해주셔서 감사합니다.
Erlang 구현에는 몇 가지 문제가 있습니다.아래의 기준으로서, 당신의 수정되지 않은 Erlang 프로그램에 대한 나의 측정 실행 시간은 47.6초였고, C 코드는 12.7초였습니다.
계산 부하가 높은 Erlang 코드를 실행하려면 먼저 네이티브 코드를 사용해야 합니다.「」를 한 컴파일erlc +native euler12.3은 에 대한 했던 것보다 %)입니다.는 이 속도를 사용하는 입니다.★★★★★★★★★★★★★★★★★★,-compile(export_all)이 기능은 실험에 유용하지만 모든 함수가 외부에서 도달할 수 있기 때문에 네이티브 컴파일러는 매우 보수적입니다(일반 BEAM 에뮬레이터는 그다지 영향을 받지 않습니다).을 「」로 치환합니다.-export([solve/0]).는, 31.5초(기준으로부터 약 35%)의 고속화를 실현합니다.
단, 코드 자체에 문제가 있습니다.factorCount 루프 내의 각 반복에 대해 다음 테스트를 수행합니다.
factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;
C코드로는 안 돼일반적으로 같은 코드의 다른 실장 간에 공정한 비교를 하는 것은 어려울 수 있습니다.특히 알고리즘이 수치적인 경우에는 실제로 같은 동작을 하고 있는지 확인해야 합니다.어느 실장에서는, 어느 쪽의 타입 캐스트에 의해서 약간 반올림 에러가 발생해도, 어느 쪽의 실장에서는 다른 쪽의 실장보다 훨씬 더 많은 반올림 에러가 발생할 가능성이 있습니다.
이 에러 발생원을 배제하기 위해서(및 각 반복에서의 추가 테스트를 배제하기 위해서), 다음과 같이 factorCount 함수를 C 코드에 근거해 상세하게 모델화했습니다.
factorCount (N) ->
Sqrt = math:sqrt (N),
ISqrt = trunc(Sqrt),
if ISqrt == Sqrt -> factorCount (N, ISqrt, 1, -1);
true -> factorCount (N, ISqrt, 1, 0)
end.
factorCount (_N, ISqrt, Candidate, Count) when Candidate > ISqrt -> Count;
factorCount ( N, ISqrt, Candidate, Count) ->
case N rem Candidate of
0 -> factorCount (N, ISqrt, Candidate + 1, Count + 2);
_ -> factorCount (N, ISqrt, Candidate + 1, Count)
end.
에서는, 「」, 「」는 없습니다.export_all컴파일은 시간을
$ erlc +native euler12.erl
$ time erl -noshell -s euler12 solve
842161320
real 0m19.468s
user 0m19.450s
sys 0m0.010s
이는 C코드에 비해 나쁘지 않습니다.
$ time ./a.out
842161320
real 0m12.755s
user 0m12.730s
sys 0m0.020s
Erlang이 숫자 코드 작성에 전혀 준비가 되어 있지 않다는 것을 고려하면, 이런 프로그램에서는 C보다 50%만 느리다는 것은 꽤 좋은 일입니다.
마지막으로 질문 사항:
질문 1: 임의의 길이의 정수를 사용하여 erlang, python 및 haskell 속도가 느립니까, 아니면 값이 MAXINT보다 작으면 느립니까?
네, 약간요.Erlang에서는 "랩 어라운드와 함께 32/64비트 산술을 사용한다"는 말은 할 수 없습니다.따라서 컴파일러가 정수에 대한 경계를 증명할 수 없는 경우(일반적으로 증명할 수 없는 경우), 모든 계산을 체크하여 단일 태그가 달린 워드에 들어갈 수 있는지 또는 힙 할당 바이넘으로 변환해야 하는지 확인해야 합니다.실행 시 실제로 bignum이 사용되지 않더라도 이러한 검사를 수행해야 합니다.한편, 이것은 알고리즘에 갑자기 더 큰 입력값을 입력해도 예기치 않은 정수 랩어라운드로 인해 알고리즘이 실패하는 일이 없다는 것을 의미합니다.
질문 4: 기능 실장에서는 LCO가 허용되어 불필요한 프레임이 콜스택에 추가되는 것을 피할 수 있습니까?
네, 지난번 콜 최적화와 관련하여 Erlang 코드가 정확합니다.
Python 최적화에 관해서는 PyPy를 사용하는 것 외에 PyPy의 번역 툴체인을 사용하여 RPython 준거 버전을 컴파일하거나 Cython을 사용하여 확장 모듈을 빌드할 수 있습니다.이 두 가지 모두 Cython 모듈을 사용하여 거의 2회 fa로 테스트하고 있습니다.St. 참고로 C 및 PyPy 벤치마크 결과도 포함합니다.
C와 )gcc -O3 -lm)
% time ./euler12-c
842161320
./euler12-c 11.95s
user 0.00s
system 99%
cpu 11.959 total
PyPy 1.5
% time pypy euler12.py
842161320
pypy euler12.py
16.44s user
0.01s system
99% cpu 16.449 total
리비전 , RPython(RPyPy) 사용),c2f583445aee)
% time ./euler12-rpython-c
842161320
./euler12-rpy-c
10.54s user 0.00s
system 99%
cpu 10.540 total
시톤 0.15
% time python euler12-cython.py
842161320
python euler12-cython.py
6.27s user 0.00s
system 99%
cpu 6.274 total
RPython은 RPython을 사용합니다.하려면 '을해야 합니다.target 이것은 「」, 「」입니다.main기능.그것은 그것을 받아들일 것으로 예상된다.sys.argv이는 인수일 뿐이고 int를 반환해야 하기 때문입니다..py 에서 할 수 .파이를 사용하다% translate.py euler12-rpython.py다아다
# euler12-rpython.py
import math, sys
def factorCount(n):
square = math.sqrt(n)
isquare = int(square)
count = -1 if isquare == square else 0
for candidate in xrange(1, isquare + 1):
if not n % candidate: count += 2
return count
def main(argv):
triangle = 1
index = 1
while factorCount(triangle) < 1001:
index += 1
triangle += index
print triangle
return 0
if __name__ == '__main__':
main(sys.argv)
def target(*args):
return main, None
은 확장 모듈 Cython으로 되었습니다._euler12.pyx비단뱀_euler12.pyx는 기본적으로 사용하시는 버전과 동일하며 추가 정적 유형 선언이 있습니다.py에는 setup을 .py에는 확장 기능을 구축하기 위한 일반 보일러 플레이트가 있습니다.python setup.py build_ext --inplace.
# _euler12.pyx
from libc.math cimport sqrt
cdef int factorCount(int n):
cdef int candidate, isquare, count
cdef double square
square = 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
cpdef main():
cdef int triangle = 1, index = 1
while factorCount(triangle) < 1001:
index += 1
triangle += index
print triangle
# euler12-cython.py
import _euler12
_euler12.main()
# setup.py
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
ext_modules = [Extension("_euler12", ["_euler12.pyx"])]
setup(
name = 'Euler12-Cython',
cmdclass = {'build_ext': build_ext},
ext_modules = ext_modules
)
저는 솔직히 RPython이나 Cython에 대한 경험이 거의 없어서 결과에 매우 놀랐습니다.CPython을 사용하는 경우 CPU 집약적인 코드 비트를 Cython 확장 모듈에 쓰는 것은 프로그램을 최적화하는 매우 쉬운 방법처럼 보입니다.
질문 3: 요인 결정 방법을 변경하지 않고 이러한 구현을 최적화하는 방법에 대해 힌트를 주시겠습니까?어떤 방식으로든 최적화: 언어에 맞게 더 좋고, 더 빠르고, 더 '원어민'합니다.
C의 실장은 (Thomas M이 시사한 바와 같이) 차선책입니다.DuBuisson), 버전에서는 64비트 정수(즉, 긴 데이터형)를 사용합니다.어셈블리 목록은 나중에 조사하겠습니다만, 컴파일된 코드로 메모리 액세스가 이루어지고 있기 때문에 64비트 정수를 사용하는 속도가 상당히 느려집니다.또는 생성된 코드입니다(SSE 레지스터에 더 적은 64비트 int를 넣거나 64비트 정수로 반올림할 수 있다는 사실이 더 느립니다).
변경된 코드는 다음과 같습니다(단, long을 int로 치환하고 명시적으로 inline factorCount를 지정합니다만, gcc - O3에서는 이것이 필요하지 않다고 생각합니다).
#include <stdio.h>
#include <math.h>
static inline int factorCount(int n)
{
double square = sqrt (n);
int isquare = (int)square;
int count = isquare == square ? -1 : 0;
int candidate;
for (candidate = 1; candidate <= isquare; candidate ++)
if (0 == n % candidate) count += 2;
return count;
}
int main ()
{
int triangle = 1;
int index = 1;
while (factorCount (triangle) < 1001)
{
index++;
triangle += index;
}
printf ("%d\n", triangle);
}
실행 중 + 타이밍:
$ gcc -O3 -lm -o euler12 euler12.c; time ./euler12
842161320
./euler12 2.95s user 0.00s system 99% cpu 2.956 total
참고로 앞의 답변에서 Thomas가 수행한 Haskell 구현은 다음과 같습니다.
$ ghc -O2 -fllvm -fforce-recomp euler12.hs; time ./euler12 [9:40]
[1 of 1] Compiling Main ( euler12.hs, euler12.o )
Linking euler12 ...
842161320
./euler12 9.43s user 0.13s system 99% cpu 9.602 total
결론:ghc에서 아무것도 얻을 수 없기 때문에 뛰어난 컴파일러이지만 보통 gcc는 더 빠른 코드를 생성합니다.
그냥 재미로.다음은 보다 '네이티브'한 Haskell 구현입니다.
import Control.Applicative
import Control.Monad
import Data.Either
import Math.NumberTheory.Powers.Squares
isInt :: RealFrac c => c -> Bool
isInt = (==) <$> id <*> fromInteger . round
intSqrt :: (Integral a) => a -> Int
--intSqrt = fromIntegral . floor . sqrt . fromIntegral
intSqrt = fromIntegral . integerSquareRoot'
factorize :: Int -> [Int]
factorize 1 = []
factorize n = first : factorize (quot n first)
where first = (!! 0) $ [a | a <- [2..intSqrt n], rem n a == 0] ++ [n]
factorize2 :: Int -> [(Int,Int)]
factorize2 = foldl (\ls@((val,freq):xs) y -> if val == y then (val,freq+1):xs else (y,1):ls) [(0,0)] . factorize
numDivisors :: Int -> Int
numDivisors = foldl (\acc (_,y) -> acc * (y+1)) 1 <$> factorize2
nextTriangleNumber :: (Int,Int) -> (Int,Int)
nextTriangleNumber (n,acc) = (n+1,acc+n+1)
forward :: Int -> (Int, Int) -> Either (Int, Int) (Int, Int)
forward k val@(n,acc) = if numDivisors acc > k then Left val else Right (nextTriangleNumber val)
problem12 :: Int -> (Int, Int)
problem12 n = (!!0) . lefts . scanl (>>=) (forward n (1,1)) . repeat . forward $ n
main = do
let (n,val) = problem12 1000
print val
「」를 사용합니다.ghc -O30.55~0.58 GHz의 Core i7 (1.73 GHz Core i7).
C 버전에 대한 보다 효율적인 factorCount 함수:
int factorCount (int n)
{
int count = 1;
int candidate,tmpCount;
while (n % 2 == 0) {
count++;
n /= 2;
}
for (candidate = 3; candidate < n && candidate * candidate < n; candidate += 2)
if (n % candidate == 0) {
tmpCount = 1;
do {
tmpCount++;
n /= candidate;
} while (n % candidate == 0);
count*=tmpCount;
}
if (n > 1)
count *= 2;
return count;
}
longs의 ints를 로 변경하는 , ints를 사용하는 방법gcc -O3 -lm0.31~0.35입니다.
n번째 삼각수 = n*(n+1)/2, n과 (n+1)의 소인수 분해가 완전히 이질적이므로 각 반의 인자 수를 곱하여 전체 인자 수를 구할 수 있습니다.다음 항목:
int main ()
{
int triangle = 0,count1,count2 = 1;
do {
count1 = count2;
count2 = ++triangle % 2 == 0 ? factorCount(triangle+1) : factorCount((triangle+1)/2);
} while (count1*count2 < 1001);
printf ("%lld\n", ((long long)triangle)*(triangle+1)/2);
}
c 코드 실행 시간이 0.17~0.19초로 단축되어 훨씬 더 큰 검색을 처리할 수 있습니다. 10000보다 큰 계수는 제 기계에서 약 43초가 걸립니다.나는 관심있는 독자에게 비슷한 해스켈의 속력을 남긴다.
Haskell 패키지의 일부 기능을 사용하면 Haskell 구현 속도를 크게 높일 수 있습니다.이 경우 prime을 사용했습니다.prime은 'cabal install primes'와 함께 설치됩니다.
import Data.Numbers.Primes
import Data.List
triangleNumbers = scanl1 (+) [1..]
nDivisors n = product $ map ((+1) . length) (group (primeFactors n))
answer = head $ filter ((> 500) . nDivisors) triangleNumbers
main :: IO ()
main = putStrLn $ "First triangle number to have over 500 divisors: " ++ (show answer)
타이밍:
원래 프로그램:
PS> measure-command { bin\012_slow.exe }
TotalSeconds : 16.3807409
TotalMilliseconds : 16380.7409
구현 개선
PS> measure-command { bin\012.exe }
TotalSeconds : 0.0383436
TotalMilliseconds : 38.3436
보시는 바와 같이 이 시스템은 16초 만에 실행되었던 머신과 동일한 머신에서 38밀리초 만에 실행됩니다.
컴파일 명령어:
ghc -O2 012.hs -o bin\012.exe
ghc -O2 012_slow.hs -o bin\012_slow.exe
해스켈과 함께라면 반복을 명시적으로 생각할 필요가 없습니다.
factorCount number = foldr factorCount' 0 [1..isquare] -
(fromEnum $ square == fromIntegral isquare)
where
square = sqrt $ fromIntegral number
isquare = floor square
factorCount' candidate
| number `rem` candidate == 0 = (2 +)
| otherwise = id
triangles :: [Int]
triangles = scanl1 (+) [1,2..]
main = print . head $ dropWhile ((< 1001) . factorCount) triangles
위의 코드에서는 @Thomas의 답변에서 명시적인 재귀가 공통 목록 연산으로 대체되었습니다.꼬리 재귀에 대한 걱정 없이 코드는 여전히 정확히 같은 기능을 합니다.GHC 7.6.2를 탑재한 제 머신에서는 @Thomas의 응답 버전(~ 7.04s)보다 약 6% 느리지만 @Raedwulf의 C 버전은 3.15s까지 실행됩니다.GHC는 1년 동안 좋아진 것 같다.
추신. 오래된 질문이라는 것을 알고 있습니다.그리고 구글 검색에서 우연히 발견하게 되었습니다.(검색하고 있던 것을 잊어버렸습니다...)LCO에 대한 질문에 대해 코멘트를 하고 Haskell에 대한 전반적인 감정을 표현하고 싶습니다.상위 답변에 대해 코멘트를 하고 싶었지만 코멘트는 코드 블록을 허용하지 않습니다.
이 블로그를 보세요.지난 1년 정도 동안 그는 해스켈과 파이썬에서 프로젝트 오일러 문제를 몇 개 풀었고, 그는 일반적으로 해스켈이 훨씬 더 빠르다고 생각했습니다.나는 그 언어들 사이에서 당신의 유창함과 코딩 스타일에 더 관련이 있다고 생각한다.
Python의 속도에 관해서는 잘못된 구현을 사용하고 있습니다.PyPy를 사용해 보세요.이렇게 하면 훨씬 더 빠릅니다.
질문 1: 임의의 길이의 정수를 사용하여 erlang, python 및 haskell 속도가 느립니까, 아니면 값이 MAXINT보다 작으면 느립니까?
그럴 것 같지 않다.Erlang과 Haskell(아래의 Haskell에 대해 조금 언급할 수는 없지만 Python에서는 다른 병목도 많이 지적할 수 있습니다.프로그램이 Python에서 몇 가지 값을 사용하여 작업을 실행하려고 할 때마다 값이 적절한 유형인지 확인해야 하며 시간이 걸립니다.의 ★★★★★★★★★★★★★★★★★.factorCount과 목록만 합니다.range (1, isquare + 1) 번, 런타임, """ "" "" " " " " " " " " " " ",malloc스타일 메모리 할당은 C에서와 같이 카운터가 있는 범위에서 반복하는 것보다 훨씬 느립니다.히,는factorCount()여러 번 호출되기 때문에 많은 목록을 할당합니다.또한 Python은 인터프리터이며 CPython 인터프리터는 최적화에 큰 초점을 두지 않는다는 점도 잊지 말자.
편집: 아, Python 3을 사용하고 계시네요.range()는 목록을 반환하지 않고 제너레이터를 반환합니다. 목록 에 대한 내. 는 단지 할당만 . 함수는 할당만 합니다.range오브젝트: 그럼에도 불구하고 많은 아이템으로 목록을 할당하는 것만큼 비효율적이지는 않습니다.
질문 2: Haskell은 왜 이렇게 느립니까?브레이크를 끄는 컴파일러 플래그가 있습니까?아니면 실장되어 있습니까?(후자는 해스켈이 7개의 도장이 찍힌 책이기 때문에 가능성이 높습니다.)
Hugs를 사용하시나요?포옹은 통역 속도가 상당히 느리다.만약 당신이 그것을 사용하고 있다면, 당신은 GHC로 더 나은 시간을 얻을 수 있을 것입니다.그러나 나는 단지 추측을 생각하고 있을 뿐입니다.좋은 Haskell 컴파일러가 하는 일은 매우 흥미롭고, 나의 이해를 훨씬 초월합니다.
질문 3: 요인 결정 방법을 변경하지 않고 이러한 구현을 최적화하는 방법에 대해 힌트를 주시겠습니까?어떤 방식으로든 최적화: 언어에 맞게 더 좋고, 더 빠르고, 더 '원어민'합니다.
난 네가 재미없는 게임을 하고 있다고 말하고 싶어.다양한 언어를 아는 것의 가장 좋은 점은 가능한 한 다른 방법으로 사용하는 것입니다:) 하지만 저는 이 점에 대해 추천할 만한 것이 없습니다.죄송합니다. 이 경우 누군가가 도움을 주셨으면 합니다.
질문 4: 기능 실장에서는 LCO가 허용되어 불필요한 프레임이 콜스택에 추가되는 것을 피할 수 있습니까?
제가 기억하는 한, 재귀 호출이 값을 반환하기 전에 마지막 명령어인지 확인만 하면 됩니다.즉, 다음과 같은 함수는 이러한 최적화를 사용할 수 있습니다.
def factorial(n, acc=1):
if n > 1:
acc = acc * n
n = n - 1
return factorial(n, acc)
else:
return acc
다만, 재귀 콜 후에 연산(곱셈)이 있기 때문에, 다음과 같은 함수의 경우는, 이러한 최적화를 실시할 수 없습니다.
def factorial2(n):
if n > 1:
f = factorial2(n-1)
return f*n
else:
return 1
어떤 작업이 실행되는지 명확히 하기 위해 일부 로컬 변수에서 작업을 분리했습니다.단, 가장 일반적인 것은 다음과 같은 기능을 보는 것이지만, 제가 말하는 요점은 다음과 같습니다.
def factorial(n, acc=1):
if n > 1:
return factorial(n-1, acc*n)
else:
return acc
def factorial2(n):
if n > 1:
return n*factorial(n-1)
else:
return 1
테일 재귀 여부를 결정하는 것은 컴파일러/인터프리터에 달려 있습니다.예를 들어 Python interpreter는 내 기억이 잘 나면 그렇게 하지 않는다(Python은 구문이 유창하기 때문에 예제에서 Python을 사용했다).파라미터가 등 이중의 파라미터에는 '요인함수'라는 있습니다).acc,accumulator그랬던 거지)왜 사람들이 지금 당신이 알고 있는:)등)이제 사람들이 왜 그러는지 알게 되었습니다.:).
시작 시도 중:
package main
import "fmt"
import "math"
func main() {
var n, m, c int
for i := 1; ; i++ {
n, m, c = i * (i + 1) / 2, int(math.Sqrt(float64(n))), 0
for f := 1; f < m; f++ {
if n % f == 0 { c++ }
}
c *= 2
if m * m == n { c ++ }
if c > 1001 {
fmt.Println(n)
break
}
}
}
이해:
오리지널 C 버전: 9.1690 100%
실행: 8.2520 111%
단, 사용방법:
package main
import (
"math"
"fmt"
)
// Sieve of Eratosthenes
func PrimesBelow(limit int) []int {
switch {
case limit < 2:
return []int{}
case limit == 2:
return []int{2}
}
sievebound := (limit - 1) / 2
sieve := make([]bool, sievebound+1)
crosslimit := int(math.Sqrt(float64(limit))-1) / 2
for i := 1; i <= crosslimit; i++ {
if !sieve[i] {
for j := 2 * i * (i + 1); j <= sievebound; j += 2*i + 1 {
sieve[j] = true
}
}
}
plimit := int(1.3*float64(limit)) / int(math.Log(float64(limit)))
primes := make([]int, plimit)
p := 1
primes[0] = 2
for i := 1; i <= sievebound; i++ {
if !sieve[i] {
primes[p] = 2*i + 1
p++
if p >= plimit {
break
}
}
}
last := len(primes) - 1
for i := last; i > 0; i-- {
if primes[i] != 0 {
break
}
last = i
}
return primes[0:last]
}
func main() {
fmt.Println(p12())
}
// Requires PrimesBelow from utils.go
func p12() int {
n, dn, cnt := 3, 2, 0
primearray := PrimesBelow(1000000)
for cnt <= 1001 {
n++
n1 := n
if n1%2 == 0 {
n1 /= 2
}
dn1 := 1
for i := 0; i < len(primearray); i++ {
if primearray[i]*primearray[i] > n1 {
dn1 *= 2
break
}
exponent := 1
for n1%primearray[i] == 0 {
exponent++
n1 /= primearray[i]
}
if exponent > 1 {
dn1 *= exponent
}
if n1 == 1 {
break
}
}
cnt = dn * dn1
dn = dn1
}
return n * (n - 1) / 2
}
이해:
오리지널 C 버전: 9.1690 100%
Tahumkid의 c 버전: 0.1060 8650%
첫 번째 버전: 8.2520 111%
세컨드 Go 버전: 0.0230 39865 %
Python 3.6과 pypy 3.3-5.5-alpha도 사용해 보았습니다.
오리지널 C 버전: 8.629 100%
Tahumkid의 c 버전: 0.140 7916%
Python3.6: 54.795 16 %
pypy 3.3-5.5-alpha: 13.291 65 %
그리고 다음 코드와 함께 받았습니다.
오리지널 C 버전: 8.629 100%
Tahumkid의 c 버전: 0.140 8650%
Python 3.6: 1.489 580 %
pypy 3.3-5.5-alpha: 0.582 1483%
def D(N):
if N == 1: return 1
sqrtN = int(N ** 0.5)
nf = 1
for d in range(2, sqrtN + 1):
if N % d == 0:
nf = nf + 1
return 2 * nf - (1 if sqrtN**2 == N else 0)
L = 1000
Dt, n = 0, 0
while Dt <= L:
t = n * (n + 1) // 2
Dt = D(n/2)*D(n+1) if n%2 == 0 else D(n)*D((n+1)/2)
n = n + 1
print (t)
질문 1: Erlang, Python 및 Haskell은 임의의 길이의 정수를 사용하여 속도가 느려지거나 값이 MAXINT보다 작으면 속도가 느려지지 않습니까?
질문 1은 Erlang에 대해 부정적으로 대답할 수 있습니다.마지막 질문은 다음과 같이 Erlang을 적절히 사용하여 답변합니다.
http://bredsaal.dk/learning-erlang-using-projecteuler-net
당신의 첫 번째 C 예보다 빠르기 때문에, 다른 예에서는 이미 자세하게 다루었기 때문에, 많은 문제가 있다고 생각합니다.
이 Erlang 모듈은 저렴한 넷북 상에서 약 5초 만에 실행됩니다.erlang의 네트워크 스레드모델을 사용하여 이벤트모델을 활용하는 방법을 나타냅니다.여러 노드에 분산될 수 있습니다.그리고 빠르다.내 암호는 아니야
-module(p12dist).
-author("Jannich Brendle, jannich@bredsaal.dk, http://blog.bredsaal.dk").
-compile(export_all).
server() ->
server(1).
server(Number) ->
receive {getwork, Worker_PID} -> Worker_PID ! {work,Number,Number+100},
server(Number+101);
{result,T} -> io:format("The result is: \~w.\~n", [T]);
_ -> server(Number)
end.
worker(Server_PID) ->
Server_PID ! {getwork, self()},
receive {work,Start,End} -> solve(Start,End,Server_PID)
end,
worker(Server_PID).
start() ->
Server_PID = spawn(p12dist, server, []),
spawn(p12dist, worker, [Server_PID]),
spawn(p12dist, worker, [Server_PID]),
spawn(p12dist, worker, [Server_PID]),
spawn(p12dist, worker, [Server_PID]).
solve(N,End,_) when N =:= End -> no_solution;
solve(N,End,Server_PID) ->
T=round(N*(N+1)/2),
case (divisor(T,round(math:sqrt(T))) > 500) of
true ->
Server_PID ! {result,T};
false ->
solve(N+1,End,Server_PID)
end.
divisors(N) ->
divisor(N,round(math:sqrt(N))).
divisor(_,0) -> 1;
divisor(N,I) ->
case (N rem I) =:= 0 of
true ->
2+divisor(N,I-1);
false ->
divisor(N,I-1)
end.
아래 테스트는 인텔(R) ATOM(TM) CPU N270 @ 1.60GHz에서 실시되었습니다.
~$ time erl -noshell -s p12dist start
The result is: 76576500.
^C
BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
(v)ersion (k)ill (D)b-tables (d)istribution
a
real 0m5.510s
user 0m5.836s
sys 0m0.152s
Erlang의 구현을 확인합니다.이 타이밍에는 전체 가상 시스템의 시작, 프로그램 실행 및 가상 시스템 중단이 포함되었습니다.erlang VM을 설정하고 중지하는 데 시간이 걸립니다.
타이밍이 erlang 가상 머신 자체 내에서 이루어지면 결과가 달라집니다.이 경우 문제의 프로그램에만 실제 시간이 할당됩니다.그렇지 않으면, Erlang VM의 기동과 로딩에 걸리는 시간과 정지하는 시간(프로그램에 넣는 시간)이 모두, 프로그램의 타이밍에 사용하는 방법에 의해서 출력되는 시간의 합계에 포함되어 있다고 생각합니다.가상 시스템 자체 내에서 프로그램 시간을 설정할 때 사용하는 erlang 타이밍 자체를 사용하는 것이 좋습니다. 이렇게 하면 erlang의 결과에서 가상 시스템을 시작 및 중지/정지/halt하는 데 걸리는 시간이 제외됩니다.그게 내 추론이야, 생각해보고 벤치 마크 다시 해봐.
실제로 정확한 값을 얻기 위해 (런타임이 있는 언어의 경우) 프로그램 실행 시간 내에 시간을 재는 것이 좋습니다.예를 들어 C는 Erlang, Python 및 Haskell과 마찬가지로 런타임 시스템을 시작 및 종료하는 오버헤드가 없습니다(98% 확신 - i 스탠드 수정).따라서 (이 추론에 근거해) 이 벤치마크는 런타임 시스템 상에서 실행되는 언어에는 충분히 정확하지 않거나 적절하지 않다고 결론짓습니다.이 변경 사항으로 다시 해보겠습니다.
편집: 또한 모든 언어에 런타임 시스템이 있더라도 각각의 부팅과 중단에 따른 오버헤드는 다르기 때문에 런타임 시스템 내에서 시간을 재는 것이 좋습니다(이것이 적용되는 언어).Erlang VM은 시작 시 상당한 오버헤드가 있는 것으로 알려져 있습니다.
C++11, 20밀리초 미만 - 여기서 실행
언어 고유의 지식을 향상시키기 위한 힌트가 필요한 것은 이해하지만, 여기서도 충분히 다루어졌으므로, 질문의 매스매틱 코멘트등을 보고, 이 코드가 왜 이렇게 느린지 궁금해 하는 분들을 위해서, 몇개의 콘텍스트를 추가하려고 생각하고 있습니다.
이 답변은 주로 질문/기타 답변의 코드를 보다 쉽게 평가할 수 있도록 컨텍스트를 제공하는 것입니다.
이 코드는 사용되는 언어와 무관한 몇 가지(추악한) 최적화만 사용합니다.
- 모든 트라우글 번호는 n(n+1)/2 형식입니다.
- n과 n+1은 공존한다.
- 제수의 수는 곱셈 함수이다
#include <iostream>
#include <cmath>
#include <tuple>
#include <chrono>
using namespace std;
// Calculates the divisors of an integer by determining its prime factorisation.
int get_divisors(long long n)
{
int divisors_count = 1;
for(long long i = 2;
i <= sqrt(n);
/* empty */)
{
int divisions = 0;
while(n % i == 0)
{
n /= i;
divisions++;
}
divisors_count *= (divisions + 1);
//here, we try to iterate more efficiently by skipping
//obvious non-primes like 4, 6, etc
if(i == 2)
i++;
else
i += 2;
}
if(n != 1) //n is a prime
return divisors_count * 2;
else
return divisors_count;
}
long long euler12()
{
//n and n + 1
long long n, n_p_1;
n = 1; n_p_1 = 2;
// divisors_x will store either the divisors of x or x/2
// (the later iff x is divisible by two)
long long divisors_n = 1;
long long divisors_n_p_1 = 2;
for(;;)
{
/* This loop has been unwound, so two iterations are completed at a time
* n and n + 1 have no prime factors in common and therefore we can
* calculate their divisors separately
*/
long long total_divisors; //the divisors of the triangle number
// n(n+1)/2
//the first (unwound) iteration
divisors_n_p_1 = get_divisors(n_p_1 / 2); //here n+1 is even and we
total_divisors =
divisors_n
* divisors_n_p_1;
if(total_divisors > 1000)
break;
//move n and n+1 forward
n = n_p_1;
n_p_1 = n + 1;
//fix the divisors
divisors_n = divisors_n_p_1;
divisors_n_p_1 = get_divisors(n_p_1); //n_p_1 is now odd!
//now the second (unwound) iteration
total_divisors =
divisors_n
* divisors_n_p_1;
if(total_divisors > 1000)
break;
//move n and n+1 forward
n = n_p_1;
n_p_1 = n + 1;
//fix the divisors
divisors_n = divisors_n_p_1;
divisors_n_p_1 = get_divisors(n_p_1 / 2); //n_p_1 is now even!
}
return (n * n_p_1) / 2;
}
int main()
{
for(int i = 0; i < 1000; i++)
{
using namespace std::chrono;
auto start = high_resolution_clock::now();
auto result = euler12();
auto end = high_resolution_clock::now();
double time_elapsed = duration_cast<milliseconds>(end - start).count();
cout << result << " " << time_elapsed << '\n';
}
return 0;
}
데스크탑의 경우 평균 19밀리초, 노트북의 경우 80밀리초 정도 소요됩니다.이것은 지금까지의 다른 코드와는 크게 다릅니다.그리고 많은 최적화를 이용할 수 있습니다.
C 버전에 대한 추가 숫자와 설명입니다.지난 몇 년 동안 아무도 그런 짓을 하지 않은 것 같아요모든 사람이 보고 배울 수 있도록 이 답변을 상향 투표하는 것을 잊지 마십시오.
1단계: 저자의 프로그램 벤치마크
노트북 사양:
- CPU i3 M380 (931 MHz - 최대 배터리 절약 모드)
- 4 GB 메모리
- Win7 64비트
- Microsoft Visual Studio 2012 Ultimate
- GCC 4.9.3을 사용하는 Cygwin
- 파이썬 2.7.10
명령어:
compiling on VS x64 command prompt > `for /f %f in ('dir /b *.c') do cl /O2 /Ot /Ox %f -o %f_x64_vs2012.exe`
compiling on cygwin with gcc x64 > `for f in ./*.c; do gcc -m64 -O3 $f -o ${f}_x64_gcc.exe ; done`
time (unix tools) using cygwin > `for f in ./*.exe; do echo "----------"; echo $f ; time $f ; done`
.
----------
$ time python ./original.py
real 2m17.748s
user 2m15.783s
sys 0m0.093s
----------
$ time ./original_x86_vs2012.exe
real 0m8.377s
user 0m0.015s
sys 0m0.000s
----------
$ time ./original_x64_vs2012.exe
real 0m8.408s
user 0m0.000s
sys 0m0.015s
----------
$ time ./original_x64_gcc.exe
real 0m20.951s
user 0m20.732s
sys 0m0.030s
Filenames 있습니다.파일명은 다음과 같습니다.integertype_architecture_compiler.exe
- 현재 intergentype은 원래 프로그램과 동일합니다(나중에 자세히 설명).
- 아키텍처는 컴파일러 설정에 따라 x86 또는 x64입니다.
- 컴파일러는 gcc 또는 vs2012입니다.
2단계: 조사, 개선 및 벤치마크 다시 실시
VS는 gcc보다 250% 빠릅니다.두 컴파일러의 속도는 비슷합니다.코드 또는 컴파일러 옵션에 문제가 있는 것은 분명합니다.조사해 봅시다!
첫 번째 관심 포인트는 정수 유형입니다.변환은 비용이 많이 들 수 있습니다.또한 코드 생성과 최적화를 향상시키기 위해서는 일관성이 중요합니다.모든 정수는 동일한 유형이어야 합니다.
이 뒤죽박죽이다의 엇갈린 혼란입니다.int그리고 그리고.long지금 당장.지금 당장. 우리는 그걸 개선할 겁니다.우리는그것을 개선할 것이다.무엇 종류를 사용할 것?어떤 타입을 사용할까요?가장 빠른.제일 빨라요.야 하는 벤치 마크 them'all!모두벤치마킹해야 해!
----------
$ time ./int_x86_vs2012.exe
real 0m8.440s
user 0m0.016s
sys 0m0.015s
----------
$ time ./int_x64_vs2012.exe
real 0m8.408s
user 0m0.016s
sys 0m0.015s
----------
$ time ./int32_x86_vs2012.exe
real 0m8.408s
user 0m0.000s
sys 0m0.015s
----------
$ time ./int32_x64_vs2012.exe
real 0m8.362s
user 0m0.000s
sys 0m0.015s
----------
$ time ./int64_x86_vs2012.exe
real 0m18.112s
user 0m0.000s
sys 0m0.015s
----------
$ time ./int64_x64_vs2012.exe
real 0m18.611s
user 0m0.000s
sys 0m0.015s
----------
$ time ./long_x86_vs2012.exe
real 0m8.393s
user 0m0.015s
sys 0m0.000s
----------
$ time ./long_x64_vs2012.exe
real 0m8.440s
user 0m0.000s
sys 0m0.015s
----------
$ time ./uint32_x86_vs2012.exe
real 0m8.362s
user 0m0.000s
sys 0m0.015s
----------
$ time ./uint32_x64_vs2012.exe
real 0m8.393s
user 0m0.015s
sys 0m0.015s
----------
$ time ./uint64_x86_vs2012.exe
real 0m15.428s
user 0m0.000s
sys 0m0.015s
----------
$ time ./uint64_x64_vs2012.exe
real 0m15.725s
user 0m0.015s
sys 0m0.015s
----------
$ time ./int_x64_gcc.exe
real 0m8.531s
user 0m8.329s
sys 0m0.015s
----------
$ time ./int32_x64_gcc.exe
real 0m8.471s
user 0m8.345s
sys 0m0.000s
----------
$ time ./int64_x64_gcc.exe
real 0m20.264s
user 0m20.186s
sys 0m0.015s
----------
$ time ./long_x64_gcc.exe
real 0m20.935s
user 0m20.809s
sys 0m0.015s
----------
$ time ./uint32_x64_gcc.exe
real 0m8.393s
user 0m8.346s
sys 0m0.015s
----------
$ time ./uint64_x64_gcc.exe
real 0m16.973s
user 0m16.879s
sys 0m0.030s
Integer 종류가 있정수형은다음과 같습니다.int long int32_t uint32_t int64_t그리고 그리고.uint64_t부터에서#include <stdint.h>
C에는 많은 정수 타입이 있으며, 몇 가지 서명된/서명되지 않은 것 외에 x86 또는 x64로 컴파일할 수 있는 옵션도 있습니다(실제 정수 사이즈와 혼동하지 마십시오.^^를 컴파일하고 실행할 수 있는 버전이 많습니다.
순서 3: 숫자에 대해서
최종 결론:
- 32비트 정수는 64비트 등가물보다 최대 200% 빠릅니다.
- 부호 없는 64비트 정수는 부호 있는 64비트보다 25% 빠릅니다(불행하게도 이에 대한 설명은 없습니다).
트릭 질문:"무엇을 native와 C는 길게의 크기이니?".'C' int long' 'C' int' " 、 'C' int long' 。
정답은 다음과 같습니다.C의 int와 long의 크기가 명확하지 않습니다!
C사양부터:
의 int입니다.
intlong이다.
gcc man 페이지(-m32 및 -m64 플래그)에서 다음을 수행합니다.
32비트 환경은 int, long 및 pointer를 32비트로 설정하고 i386 시스템에서 실행되는 코드를 생성합니다.
64비트 환경은 int를 32비트 길이, 포인터를 64비트로 설정하고 AMD의 x86-64 아키텍처용 코드를 생성합니다.
MSDN 매뉴얼(데이터 타입 범위)https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx 에서 다음 문서를 참조해 주세요.
있는 int, 4바이트, 4바이트, 4바이트로 있습니다.
및 long int long, 4 이 long int long int signed long int int int 。
결론: 배운 교훈
32비트 정수가 64비트 정수보다 빠릅니다.
표준 정수 유형은 C 또는 C++에서 잘 정의되지 않으며 컴파일러 및 아키텍처에 따라 다릅니다. 가능성이 , "예측가능성합니다.
uint32_t「」의#include <stdint.h>.속도 문제 해결.다른 모든 언어는 수백 % 뒤처져 있어 C&C++가 다시 승리했습니다!그들은 항상 그래.다음 개선사항은 OpenMP : D를 사용한 멀티스레딩입니다.
요인의 수는 관련된 요인의 수가 작은 요인의 수가 많은 경우에만 많다고 가정했습니다.그래서 저는 Taumkid의 뛰어난 알고리즘을 사용했지만, 먼저 너무 작지 않은 인자 수에 대한 근사치를 사용했습니다.매우 간단합니다.29까지 소인수를 확인한 다음 나머지 숫자를 확인하고 nmber 요인의 상한을 계산합니다.이 항목을 사용하여 요인 수의 상한을 계산하고 이 수가 충분히 높으면 정확한 요인 수를 계산합니다.
아래 코드는 정확성을 위해 이 가정을 필요로 하는 것이 아니라 신속해야 합니다.그것은 효과가 있는 것처럼 보인다; 100,000개 중 한 개만이 전체 확인이 필요할 정도로 충분히 높은 견적을 제공한다.
코드는 다음과 같습니다.
// Return at least the number of factors of n.
static uint64_t approxfactorcount (uint64_t n)
{
uint64_t count = 1, add;
#define CHECK(d) \
do { \
if (n % d == 0) { \
add = count; \
do { n /= d; count += add; } \
while (n % d == 0); \
} \
} while (0)
CHECK ( 2); CHECK ( 3); CHECK ( 5); CHECK ( 7); CHECK (11); CHECK (13);
CHECK (17); CHECK (19); CHECK (23); CHECK (29);
if (n == 1) return count;
if (n < 1ull * 31 * 31) return count * 2;
if (n < 1ull * 31 * 31 * 37) return count * 4;
if (n < 1ull * 31 * 31 * 37 * 37) return count * 8;
if (n < 1ull * 31 * 31 * 37 * 37 * 41) return count * 16;
if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43) return count * 32;
if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47) return count * 64;
if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53) return count * 128;
if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59) return count * 256;
if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61) return count * 512;
if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67) return count * 1024;
if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71) return count * 2048;
if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73) return count * 4096;
return count * 1000000;
}
// Return the number of factors of n.
static uint64_t factorcount (uint64_t n)
{
uint64_t count = 1, add;
CHECK (2); CHECK (3);
uint64_t d = 5, inc = 2;
for (; d*d <= n; d += inc, inc = (6 - inc))
CHECK (d);
if (n > 1) count *= 2; // n must be a prime number
return count;
}
// Prints triangular numbers with record numbers of factors.
static void printrecordnumbers (uint64_t limit)
{
uint64_t record = 30000;
uint64_t count1, factor1;
uint64_t count2 = 1, factor2 = 1;
for (uint64_t n = 1; n <= limit; ++n)
{
factor1 = factor2;
count1 = count2;
factor2 = n + 1; if (factor2 % 2 == 0) factor2 /= 2;
count2 = approxfactorcount (factor2);
if (count1 * count2 > record)
{
uint64_t factors = factorcount (factor1) * factorcount (factor2);
if (factors > record)
{
printf ("%lluth triangular number = %llu has %llu factors\n", n, factor1 * factor2, factors);
record = factors;
}
}
}
}
이를 통해 약 0.7초 만에 13824개의 계수를 가진 14,753,024번째 삼각수, 34초 만에 61,440개의 계수를 가진 879,207,615번째 삼각수, 10분 5초 만에 138,240개의 계수를 가진 12,524,486,975번째 삼각수 및 2532분의 계수를 가진 26,467,92,064,0번째 삼각수를 찾습니다.GHz Core2 Duo)를 통해 이 코드에는 평균 번호당 116개의 프로세서 사이클이 소요됩니다.마지막 삼각수 자체가 2^68보다 크니까
"Jannich Brendle" 버전을 500이 아닌 1000으로 수정했습니다.그리고 oiler12.bin, oiler12.erl, p12dist.erl의 결과를 나열하라.두 Erl 코드 모두 '+native'를 사용하여 컴파일합니다.
zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s p12dist start
The result is: 842161320.
real 0m3.879s
user 0m14.553s
sys 0m0.314s
zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s euler12 solve
842161320
real 0m10.125s
user 0m10.078s
sys 0m0.046s
zhengs-MacBook-Pro:workspace zhengzhibin$ time ./euler12.bin
842161320
real 0m5.370s
user 0m5.328s
sys 0m0.004s
zhengs-MacBook-Pro:workspace zhengzhibin$
#include <stdio.h>
#include <math.h>
int factorCount (long n)
{
double square = sqrt (n);
int isquare = (int) square+1;
long candidate = 2;
int count = 1;
while(candidate <= isquare && candidate <= n){
int c = 1;
while (n % candidate == 0) {
c++;
n /= candidate;
}
count *= c;
candidate++;
}
return count;
}
int main ()
{
long triangle = 1;
int index = 1;
while (factorCount (triangle) < 1001)
{
index ++;
triangle += index;
}
printf ("%ld\n", triangle);
}
gcc -lm -Ofast oiler.c
타임아웃
2.79s 사용자 0.00s 시스템 99% CPU 2.794 합계
언급URL : https://stackoverflow.com/questions/6964392/speed-comparison-with-project-euler-c-vs-python-vs-erlang-vs-haskell
'source' 카테고리의 다른 글
| Vue.js에서 폼 기본 동작 방지 (0) | 2022.08.19 |
|---|---|
| 최적의 C/C++ 네트워크 라이브러리 (0) | 2022.08.19 |
| 컴파일 가드가 다중 정의 포함을 방지하지 못하는 이유는 무엇입니까? (0) | 2022.08.19 |
| VueJ + Vuex + map Actions (0) | 2022.08.19 |
| Nuxt.js에서 Rails로 전송된 데이터를 저장하고 싶다. (0) | 2022.08.19 |