Project Euler による速度比較: C vs Python vs Erlang vs Haskell 質問する

まとめ：

• 100% ...
• Python: 692% (PyPy 使用時は 118%)
• Erlang: 436% (135% は RichardC のおかげです)
• ハスケル: 1421%

C は、他の 3 つのように任意の長さの整数ではなく、計算に long を使用するため、大きな利点があると思います。また、最初にランタイムをロードする必要もありません (他の言語ではどうでしょうか?)。

質問 1: Erlang、Python、Haskell は、任意の長さの整数を使用することで速度が低下しますか、それとも値が 未満である限り速度は低下しませんかMAXINT?

質問 2: Haskell はなぜこんなに遅いのでしょうか? ブレーキをオフにするコンパイラ フラグがあるのでしょうか、それとも私の実装の問題なのでしょうか? (Haskell は私にとって 7 つの封印がされた本なので、後者である可能性が非常に高いです。)

質問 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