복붙노트

[PYTHON] Project Euler와의 속도 비교 : C vs Python vs. Erlang vs Haskell

PYTHON

Project Euler와의 속도 비교 : C vs Python vs. Erlang vs Haskell

필자는 Project Euler의 Problem # 12를 프로그래밍 연습으로 사용하고 C, Python, Erlang 및 Haskell에서의 (필연적으로 최적이 아닌) 구현을 비교합니다. 좀 더 높은 실행 시간을 얻기 위해 원래 문제에서 언급 한 것처럼 500 대신에 1000 개 이상의 제수를 가진 첫 번째 삼각형 수를 검색합니다.

결과는 다음과 같습니다.

기음:

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

파이썬과 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

얼랭 :

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가 계산을 위해 오랫동안 사용하고 다른 세 정수처럼 임의의 길이 정수를 사용하지 않기 때문에 큰 장점이 있다고 가정합니다. 또한 런타임을 먼저로드 할 필요가 없습니다 (나머지는 수행합니까?).

질문 1: 얼랑 (Erlang), 파이썬 (Python)과 하스켈 (Haskell)은 임의의 길이의 정수를 사용하기 때문에 속도가 떨어지거나 값이 MAXINT보다 작 으면 속도가 떨어지나요?

질문 2 : 하스켈은 왜 그렇게 느린가? 거기에 브레이크를 해제하거나 내 구현은 컴파일러 플래그가 있나요? (후자는 하스켈이 나에게 7 개의 물개가있는 책이므로 상당히 가능성이 있습니다.)

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

편집하다:

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

저는 하스켈과 얼랭의 지식이 매우 제한적이라는 것을 인정해야하지만 가능한 한 동일한 알고리즘을 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

해결법

  1. ==============================

    1.GHC 7.0.3, gcc 4.4.6, Linux 2.6.29를 x86_64 Core2 Duo (2.5GHz) 컴퓨터에서 사용하고 ghc -O2 -fllvm -fforce-recomp를 사용하여 Haskell을 컴파일하고 gcc -O3 -lm을 사용하여 C를 컴파일합니다.

    GHC 7.0.3, gcc 4.4.6, Linux 2.6.29를 x86_64 Core2 Duo (2.5GHz) 컴퓨터에서 사용하고 ghc -O2 -fllvm -fforce-recomp를 사용하여 Haskell을 컴파일하고 gcc -O3 -lm을 사용하여 C를 컴파일합니다.

     $ time ./so
 842161320  

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

    맞아. 7.95 초. 지속적으로 C 솔루션보다 0.5 초 빠릅니다. -fllvm 플래그가 없으면 여전히 8.182 초가 걸리므로 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

    편집 : 이제 우리는 그것을 탐구 해 보았습니다.

    Haskell에서 Integer를 사용하는 것은 Int보다 느리지 만, 수행 된 계산에 따라 느리게 계산됩니다. 다행히도 (64 비트 컴퓨터의 경우) Int이면 충분합니다. 이식성을 위해 Int64 또는 Word64를 사용하도록 코드를 다시 작성해야합니다 (C는 길이가 긴 유일한 언어는 아닙니다).

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

    네, 그게 문제가 아니 었습니다. 좋은 일을하고 기뻤습니다.

  2. ==============================

    2.Erlang 구현에는 몇 가지 문제가 있습니다. 다음을위한 기준으로, 수정되지 않은 Erlang 프로그램의 측정 된 실행 시간은 C 코드의 12.7 초에 비해 47.6 초입니다.

    Erlang 구현에는 몇 가지 문제가 있습니다. 다음을위한 기준으로, 수정되지 않은 Erlang 프로그램의 측정 된 실행 시간은 C 코드의 12.7 초에 비해 47.6 초입니다.

    계산 집약적 인 Erlang 코드를 실행하려면 먼저 원시 코드를 사용하십시오. erlc + native euler12로 컴파일하면 41.3 초가 걸립니다. 그러나이 종류의 코드에서 원시 컴파일로 예상 한 것보다 훨씬 더 빠른 속도 (단지 15 %)이며 문제는 -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 프로그램보다 C보다 50 % 더 느리다는 것은 꽤 좋은 것입니다.

    마지막으로, 귀하의 질문에 관해서 :

    질문 1 : 임의의 길이 정수를 사용하기 때문에 erlang, python 및 haskell 속도가 느려지거나 값이 MAXINT보다 작 으면 않는가?

    네, 다소. Erlang에서는 "32/64 비트 산술을 사용하여 랩 어라운드"라고 말할 방법이 없기 때문에 컴파일러가 정수에 대한 경계를 증명할 수 없다면 (보통은 그렇게 할 수 없다), 모든 계산을 점검해야한다. 단일 태그가있는 단어에 적합하거나 힙 할당 bignum으로 변환해야하는 경우 런타임시 실제로 bignum이 사용되지 않더라도이 검사를 수행해야합니다. 반면에 갑자기 이전보다 더 큰 입력을 주면 예기치 않은 정수 랩 어라운드 때문에 알고리즘이 실패하지 않는다는 것을 의미합니다.

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

    네, 얼랭 코드는 최종 통화 최적화와 관련하여 정확합니다.

  3. ==============================

    3.Python 최적화와 관련하여 PyPy를 사용하는 것 외에도 PyPy의 번역 툴 체인을 사용하여 RPython 호환 버전을 컴파일하거나 Cython을 사용하여 확장 모듈을 빌드 할 수 있습니다. Cython 모듈이 거의 두 배 빠름 내 테스트에서 C 버전보다 빠릅니다. 참고로 저는 C와 PyPy 벤치 마크 결과도 포함합니다 :

    Python 최적화와 관련하여 PyPy를 사용하는 것 외에도 PyPy의 번역 툴 체인을 사용하여 RPython 호환 버전을 컴파일하거나 Cython을 사용하여 확장 모듈을 빌드 할 수 있습니다. Cython 모듈이 거의 두 배 빠름 내 테스트에서 C 버전보다 빠릅니다. 참고로 저는 C와 PyPy 벤치 마크 결과도 포함합니다 :

    C (gcc -O3 -lm으로 컴파일 됨)

    % time ./euler12-c 
842161320

./euler12-c  11.95s 
 user 0.00s 
 system 99% 
 cpu 11.959 total

    피피 1.5

    % time pypy euler12.py
842161320
pypy euler12.py  
16.44s user 
0.01s system 
99% cpu 16.449 total

    RPython (최신 PyPy 개정판, c2f583445aee 사용)

    % time ./euler12-rpython-c
842161320
./euler12-rpy-c  
10.54s user 0.00s 
system 99% 
cpu 10.540 total

    Cython 0.15

    % time python euler12-cython.py
842161320
python euler12-cython.py  
6.27s user 0.00s 
system 99% 
cpu 6.274 total

    RPython 버전에는 몇 가지 주요 변경 사항이 있습니다. 독립 실행 형 프로그램으로 변환하려면 대상을 정의해야합니다.이 경우 대상은 주 기능입니다. sys.argv를 인수로 받아 들일 것으로 예상되며 int를 반환해야합니다. translate.py, % translate.py euler12-rpython.py를 사용하여 번역 할 수 있습니다.이 번역은 C로 변환되어 컴파일됩니다.

    # 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 버전은 일반 python 파일에서 가져오고 호출하는 확장 모듈 _euler12.pyx로 다시 작성되었습니다. _euler12.pyx는 본질적으로 버전과 동일하며 몇 가지 추가 정적 유형 선언이 포함되어 있습니다. 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을 사용하는 경우 Cython 확장 모듈에 CPU를 많이 사용하는 코드를 작성하는 것이 프로그램을 최적화하는 가장 쉬운 방법입니다.

  4. ==============================

    4.C 구현은 (Thomas M. DuBuisson이 암시 한 것처럼) 차선책이며 버전은 64 비트 정수 (즉, 긴 데이터 유형)를 사용합니다. 나중에 어셈블리리스트를 조사 하겠지만, 추측 컨데, 64 비트 정수를 상당히 느리게 사용하는 컴파일 된 코드에서 일부 메모리 액세스가 발생합니다. 이 코드가 생성되었거나 생성 된 코드입니다 (SSE 레지스터에 64 비트 int를 적게 넣거나 64 비트 정수로 double을 반올림하는 것이 더 느립니다).

    C 구현은 (Thomas M. DuBuisson이 암시 한 것처럼) 차선책이며 버전은 64 비트 정수 (즉, 긴 데이터 유형)를 사용합니다. 나중에 어셈블리리스트를 조사 하겠지만, 추측 컨데, 64 비트 정수를 상당히 느리게 사용하는 컴파일 된 코드에서 일부 메모리 액세스가 발생합니다. 이 코드가 생성되었거나 생성 된 코드입니다 (SSE 레지스터에 64 비트 int를 적게 넣거나 64 비트 정수로 double을 반올림하는 것이 더 느립니다).

    다음은 수정 된 코드입니다 (int를 long으로 대체하고 gcc -O3과 함께 필요하다고 생각하지는 않지만 명시 적으로 인라인 된 factorCount를 사용합니다).

    #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는 일반적으로 더 빠른 코드를 생성합니다.

  5. ==============================

    5.이 블로그를 한번보세요. 지난 1 년 동안 하스켈과 파이썬에서 Project Euler 문제 중 일부를 수행했으며, 그는 하스켈이 훨씬 더 빠르다고 일반적으로 발견했습니다. 그 언어들 사이에는 유창함과 코딩 스타일에 더 많은 것이 있다고 생각합니다.

    이 블로그를 한번보세요. 지난 1 년 동안 하스켈과 파이썬에서 Project Euler 문제 중 일부를 수행했으며, 그는 하스켈이 훨씬 더 빠르다고 일반적으로 발견했습니다. 그 언어들 사이에는 유창함과 코딩 스타일에 더 많은 것이 있다고 생각합니다.

    파이썬 속도에 관해서는 잘못된 구현을 사용하고 있습니다! PyPy를 사용해 보시고, 이와 같은 것들을 위해 훨씬 빠르고 훨씬 빠르다는 것을 알게 될 것입니다.

  6. ==============================

    6.Haskell 패키지의 일부 기능을 사용하면 Haskell 구현을 크게 향상시킬 수 있습니다. 이 경우 나는 'cabal install primes'로 설치 한 소수를 사용했다;)

    Haskell 패키지의 일부 기능을 사용하면 Haskell 구현을 크게 향상시킬 수 있습니다. 이 경우 나는 '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
  7. ==============================

    7.재미로. 다음은 '기본'하스켈 구현입니다.

    재미로. 다음은 '기본'하스켈 구현입니다.

    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 -O3을 사용하면 내 컴퓨터 (1.73GHz Core i7)에서 0.55 ~ 0.58 초 동안 일관되게 실행됩니다.

    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;
}

    gcc -O3 -lm을 사용하여 main에서 long을 int로 변경하면 일관되게 0.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 속도 향상을 남겨둔다.

  8. ==============================

    8.이것은있을 법하지 않습니다. 나는 Erlang과 Haskell에 대해 많이 말할 수는 없지만 (파이썬에서 다른 병목 현상을 지적 할 수있다. 프로그램이 파이썬에서 어떤 값을 가진 연산을 실행하려고 할 때마다, 값이 적절한 타입인지를 확인해야하고, 약간의 시간이 걸린다. 귀하의 factorCount 함수는 여러 번 범위 (1, isquare + 1)가있는 목록을 할당하고 런타임에서는 malloc 스타일의 메모리 할당이 카운터에서 범위를 반복하는 것보다 느립니다. 특히, factorCount () 여러 번 호출되므로 많은 목록을 할당합니다. 또한 파이썬이 해석되고 CPython 인터프리터가 최적화에 집중하지 않는다는 사실을 잊지 말자.

    이것은있을 법하지 않습니다. 나는 Erlang과 Haskell에 대해 많이 말할 수는 없지만 (파이썬에서 다른 병목 현상을 지적 할 수있다. 프로그램이 파이썬에서 어떤 값을 가진 연산을 실행하려고 할 때마다, 값이 적절한 타입인지를 확인해야하고, 약간의 시간이 걸린다. 귀하의 factorCount 함수는 여러 번 범위 (1, isquare + 1)가있는 목록을 할당하고 런타임에서는 malloc 스타일의 메모리 할당이 카운터에서 범위를 반복하는 것보다 느립니다. 특히, factorCount () 여러 번 호출되므로 많은 목록을 할당합니다. 또한 파이썬이 해석되고 CPython 인터프리터가 최적화에 집중하지 않는다는 사실을 잊지 말자.

    편집 : 오, 음, 글쎄, 당신은 목록 (range)을 반환하지 않고 파이썬 3을 사용하고있다. 그러나 생성기 (generator). 이 경우 목록을 할당하는 것에 대한 저의 요점은 반쯤 잘못되었습니다. 함수는 범위 객체를 할당하기 만하지만 비효율적이지만 항목이 많은 목록을 할당하는 것만 큼 비효율적이지는 않습니다.

    너 허그를 사용하고 있니? 포옹은 상당히 느린 통역사입니다. 만약 당신이 그것을 사용하고 있다면, 어쩌면 당신은 GHC로 더 좋은 시간을 가질 수 있습니다 -하지만 hypotheis, 좋은 하스켈 컴파일러가 후드 아래에서하는 일종의 일종은 꽤 흥미 롭고 내 이해를 초월한 방법입니다. :)

    나는 너를 놀리는 게임이라고 말한다. 다양한 언어를 아는 가장 좋은 방법은 가능하면 가장 다른 방법을 사용하는 것입니다.하지만 나는이 지점에 대한 권장 사항이 없습니다. 죄송합니다. 누군가이 사건에서 당신을 도울 수 있기를 바랍니다 :)

    늘어나는만큼, 값을 반환하기 전에 재귀 호출이 마지막 명령인지 확인해야합니다. 즉, 아래 함수와 같은 최적화 함수를 사용할 수 있습니다.

    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

    꼬리 재귀를 만들지 결정하는 것은 컴파일러 / 인터프리터의 몫이다. 예를 들어, 잘 기억한다면 파이썬 인터프리터는 그것을하지 않습니다 (저는 유창한 구문 때문에 나의 예제에서 파이썬을 사용했습니다). 어쨌든, 두 개의 매개 변수가있는 계승 함수와 같은 이상한 물건을 발견하면 (그리고 매개 변수 중 하나에 acc, 누산기 등의 이름이 있음) 이제 사람들이 왜 그것을하는지 알 수 있습니다 :)

  9. ==============================

    9.Haskell을 사용하면 재귀에서 명시 적으로 생각할 필요가 없습니다.

    Haskell을 사용하면 재귀에서 명시 적으로 생각할 필요가 없습니다.

    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의 일반적인 목록 작업에 대한 응답에서 명시 적 재귀를 대체했습니다. 꼬리 재귀에 대해 걱정할 필요없이 코드는 여전히 똑같은 일을합니다. @Raedwulf의 C 버전은 ~ 3.15s까지 실행되는 반면, GHC 7.6.2를 사용하는 @Thomas의 응답 (~ 7.04s)의 버전보다 GHC 7.6.2의 버전보다 약 6 % 느립니다 (~ 7.49s). GHC가 일 년 내내 개선 된 것 같습니다.

    추신. 나는 그것이 오래된 질문이라는 것을 알고 있으며 나는 구글 검색 (나는 지금 무엇을 찾고 있는지 잊어 버렸다 ...)에서 우연히 발견한다. LCO에 관한 질문에 대해 논평하고 하스켈에 대한 내 감정을 전반적으로 표현하고 싶었습니다. 가장 좋은 답변에 대해 의견을 말하고 싶지만 주석은 코드 블록을 허용하지 않습니다.

  10. ==============================

    10.얼랭 구현을 살펴보십시오. 타이밍은 전체 가상 컴퓨터의 시작, 프로그램 실행 및 가상 컴퓨터 중지를 포함합니다. erlang VM을 설정하고 중지하는 데 시간이 좀 걸릴 것이라고 확신합니다.

    얼랭 구현을 살펴보십시오. 타이밍은 전체 가상 컴퓨터의 시작, 프로그램 실행 및 가상 컴퓨터 중지를 포함합니다. erlang VM을 설정하고 중지하는 데 시간이 좀 걸릴 것이라고 확신합니다.

    타이밍이 erlang 가상 머신 자체 내에서 수행 되었다면, 결과는 다른 경우가 될 것입니다. 우리는 문제의 프로그램에 대해서만 실제 시간을 갖습니다. 그렇지 않으면 Erlang Vm을 시작하고로드하는 프로세스에 걸린 총 시간 (프로그램에 넣었을 때)을 멈추는 총 시간은 모두 시간을 계산하는 데 사용하는 총 시간에 포함됩니다. 프로그램이 출력 중입니다. 가상 머신 자체에서 프로그램 시간을 정할 때 사용하는 erlang 타이밍 자체의 사용을 고려하십시오. 타이머 : tc / 1 또는 타이머 : tc / 2 또는 타이머 : tc / 3. 이 방법으로, erlang의 결과는 가상 시스템을 시작 및 중지 / 중지하는 데 걸리는 시간을 제외합니다. 그것은 저의 추론입니다. 그것에 대해 생각하고 벤치 마크를 다시 시도하십시오.

    정확한 값을 얻기 위해 해당 언어의 런타임 내에서 프로그램을 런타임에 실행하려고 시도하는 것이 좋습니다. 예를 들어 Erlang, Python, Haskell처럼 런타임 시스템을 시작하고 종료하는 데 오버 헤드가 없습니다 (98 %는 정정을 의미합니다). 그래서 (이 추론을 바탕으로) 나는이 벤치 마크가 런타임 시스템의 최상위에서 실행되는 언어에 대해 정확하지 않다고 말하는 것으로 결론을 짓는다. 이 변경 사항을 다시 적용 할 수 있습니다.

    편집 : 게다가 모든 언어가 런타임 시스템을했다하더라도, 각각을 시작하고 그것을 중단의 오버 헤드가 다를 것입니다. 그래서 우리는 런타임 시스템 (이 언어가 적용되는 언어) 내에서 시간을 제안합니다. Erlang VM은 시동시 상당한 오버 헤드가있는 것으로 알려져 있습니다!

  11. ==============================

    11.C 버전에 대한 더 많은 숫자와 설명. 분명히 아무도 그 모든 년 동안 그것을하지 않았다. 모든 사람들이보고 배우고 얻을 수 있도록이 대답을 upvote 기억하십시오.

    C 버전에 대한 더 많은 숫자와 설명. 분명히 아무도 그 모든 년 동안 그것을하지 않았다. 모든 사람들이보고 배우고 얻을 수 있도록이 대답을 upvote 기억하십시오.

    노트북 사양 :

    명령 :

    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

    파일 이름은 다음과 같습니다 : integertype_architecture_compiler.exe

    VS는 gcc보다 250 % 빠릅니다. 두 컴파일러는 비슷한 속도를 제공해야합니다. 분명히, 코드 나 컴파일러 옵션에 문제가 있습니다. 조사하자!

    첫 번째 관심 영역은 정수 유형입니다. 변환은 비용이 많이 들고 일관성은 더 나은 코드 생성 및 최적화에 중요합니다. 모든 정수는 같은 유형이어야합니다.

    지금은 int와 long이 혼재 된 혼란입니다. 우리는 그것을 향상시킬 것입니다. 어떤 유형을 사용할 수 있습니까? 가장 빠른. 꼭 벤치 마크 해!

    ----------
$ 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

    정수 유형은 int입니다. int32_t uint32_t int64_t 및 uint64_t from #include

    C에는 정수 유형이 많이 있고, 서명 / 서명되지 않은 코드와 함께 x86 또는 x64 (실제 정수 크기와 혼동해서는 안 됨)로 컴파일 할 선택 항목이 있습니다. 컴파일 및 실행 버전이 많이 있습니다 ^^

    결론 :

    트릭 질문 : "C에서 int와 long의 크기는 무엇입니까?" 올바른 대답은 : int의 크기와 C의 길이가 잘 정의되어 있지 않습니다!

    C 스펙에서 :

    gcc 맨 페이지 (-m32와 -m64 플래그)에서 :

    MSDN 설명서 (데이터 유형 범위) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :

  12. ==============================

    12.질문 1은 Erlang에 대한 음성으로 대답 할 수 있습니다. 마지막 질문은 Erlang을 다음과 같이 적절하게 사용하여 응답합니다.

    질문 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.

    아래 테스트는 Intel Atom ™ 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
  13. ==============================

    13.C ++ 11, <20ms for me - 여기서 실행하십시오.

    C ++ 11, <20ms for me - 여기서 실행하십시오.

    언어 별 지식을 향상시키는 데 도움이되는 팁을 원한다는 것을 이해합니다. 그러나 여기에서 다루었 기 때문에 질문 등에 대한 mathematica 주석을 보았을 수도있는 사람들을위한 컨텍스트를 추가하고 이것이 왜 궁금합니다. 코드가 너무 느렸다.

    이 답변은 주로 사람들이 질문 / 기타 답변의 코드를보다 쉽게 ​​평가할 수 있도록하기위한 컨텍스트를 제공하는 데 주로 사용됩니다.

    이 코드는 다음을 기반으로 사용되는 언어와 관련이없는 몇 가지 (uglyish) 최적화만을 사용합니다.

    #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 밀리 초가 걸렸습니다. 여기에서 보았던 대부분의 다른 코드와는 거리가 있습니다. 그리고 의심 할 여지없이 여전히 많은 최적화가 가능합니다.

  14. ==============================

    14.시도 :

    시도 :

    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 % thaumkid의 C 버전 : 0.1060 8650 % 최초 버전 : 8.2520 111 % 두 번째 시도 버전 : 0.0230 39865 %

    나는 또한 Python3.6과 pypy3.3-5.5-alpha를 시도했다.

    원본 C 버전 : 8.629 100 % 유행 버전 : 0.109 7916 % 파이썬 3.6 : 54.795 16 % pypy3.3-5.5-alpha : 13.291 65 %

    그리고 다음 코드를 얻었습니다.

    원본 C 버전 : 8.629 100 % 유행 버전 : 0.109 8650 % 파이썬 3.6 : 1.489 580 % pypy3.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)
  15. ==============================

    15.변경 : 사례 (제수 (T, round (math : sqrt (T)))> 500) of

    변경 : 사례 (제수 (T, round (math : sqrt (T)))> 500) of

    To : case (제수 (T, round (math : sqrt (T)))> 1000) of

    이렇게하면 Erlang 다중 프로세스 예제에 대한 정답을 얻을 수 있습니다.

  16. ==============================

    16.관련된 숫자에 많은 작은 요소가있는 경우 요소의 수가 많은 것으로 가정했습니다. 그래서 thaumkid의 탁월한 알고리즘을 사용했지만 처음에는 너무 작지 않은 요소 수에 대한 근사값을 사용했습니다. 그것은 매우 간단합니다 : 29까지 소수 요소를 확인한 다음 남은 수를 확인하고 요소 수에 대한 상한을 계산하십시오. 이것을 사용하여 요인 수에 대한 상한을 계산하고, 그 수가 충분히 높으면 정확한 요인 수를 계산하십시오.

    관련된 숫자에 많은 작은 요소가있는 경우 요소의 수가 많은 것으로 가정했습니다. 그래서 thaumkid의 탁월한 알고리즘을 사용했지만 처음에는 너무 작지 않은 요소 수에 대한 근사값을 사용했습니다. 그것은 매우 간단합니다 : 29까지 소수 요소를 확인한 다음 남은 수를 확인하고 요소 수에 대한 상한을 계산하십시오. 이것을 사용하여 요인 수에 대한 상한을 계산하고, 그 수가 충분히 높으면 정확한 요인 수를 계산하십시오.

    아래의 코드는 정확성을 위해이 가정이 필요하지 않지만 빠르다. 그것은 작동하는 것 같다; 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 번째 삼각형 수 및 172,032 개의 요소가있는 26,467,792,064 번째 삼각형 수를 찾습니다. 21 분 25 초 (2.4GHz Core2 Duo)이므로이 코드는 평균적으로 숫자 당 116 프로세서 사이클 밖에 걸리지 않습니다. 마지막 삼각형 수 자체는 2 ^ 68보다 큽니다.

  17. ==============================

    17.나는 "Jannich Brendle"버전을 500 대신에 1000으로 수정했다. 그리고 euler12.bin, euler12.erl, p12dist.erl의 결과를 나열한다. 두 erl 코드 모두 '+ native'를 사용하여 컴파일합니다.

    나는 "Jannich Brendle"버전을 500 대신에 1000으로 수정했다. 그리고 euler12.bin, euler12.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$
  18. ==============================

    18.

    #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 euler.c

    시간 ./a.out

    2.79s 사용자 0.00s 시스템 99 % cpu 2.794 total

    19. from https://stackoverflow.com/questions/6964392/speed-comparison-with-project-euler-c-vs-python-vs-erlang-vs-haskell by cc-by-sa and MIT license

'PYTHON' 카테고리의 다른 글

[PYTHON] Django 사이트에서 HTML을 PDF로 렌더링  (0) 2018.10.09
[PYTHON] 파이썬 대 Cpython  (0) 2018.10.09
[PYTHON] 날짜를 기반으로 한 R 또는 Python의 요소 값 붙여 넣기 - 학교 간 나누기 만들기  (0) 2018.10.09
[PYTHON] 새 줄을 삽입하지 않고도 사용자 입력을받을 수 있습니까?  (0) 2018.10.09
[PYTHON] 이름을 가진 모듈을 가져 오는 방법?  (0) 2018.10.09
,

티스토리툴바