與Project Euler進行速度比較:C vs Python vs Erlang vs Haskell




performance (12)

我將Project Euler的 問題#12作為編程練習,並比較了C,Python,Erlang和Haskell中的我的(當然不是最優的)實現。 為了獲得更高的執行時間,我搜索了第一個包含1000個以上除數的三角形數字,而不是原始問題中所述的500。

結果如下:

C:

[email protected]:~/erlang$ gcc -lm -o euler12.bin euler12.c
[email protected]:~/erlang$ time ./euler12.bin
842161320

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

蟒蛇:

[email protected]:~/erlang$ time ./euler12.py 
842161320

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

Python與PyPy:

[email protected]:~/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

二郎:

[email protected]:~/erlang$ erlc euler12.erl 
[email protected]:~/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

哈斯克爾:

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

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

概要:

  • C:100%
  • Python:692%(PyPy為118%)
  • Erlang:436%(135%感謝RichardC)
  • 哈斯克爾:1421%

我認為C具有很大的優勢,因為它使用很長的時間進行計算,而不是任意長度的整數作為其他三個。 也不需要首先加載運行時(其他人?)。

問題1:由於使用任意長度的整數,Erlang,Python和Haskell是否會失去速度,或者只要值小於MAXINT它們是否會失去速度?

問題2:為什麼Haskell這麼慢? 是否有編譯器標誌關閉剎車或者是我的實現? (後者很可能,因為Haskell是一本有七枚印章的書。)

問題3:您能否提供一些提示,告訴我如何優化這些實現而不改變我確定因素的方式? 以任何方式優化:更好,更快,更“原生”的語言。

編輯:

問題4:我的功能實現是否允許LCO(上次呼叫優化,也稱為尾遞歸消除),從而避免在調用堆棧中添加不必要的幀?

儘管我不得不承認我的Haskell和Erlang的知識非常有限,但我真的試圖在四種語言中盡可能地實現相同的算法。

使用的源代碼:

#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:由於使用了任意長度的整數,Erlang,python和haskell的速度是否會減慢,或者只要值小於MAXINT,它們是否會變慢?

這不太可能。 我不能多說Erlang和Haskell(好吧,下面可能有點關於Haskell),但我可以指出Python中的其他瓶頸。 每次程序試圖用Python中的某些值執行某個操作時,都應驗證這些值是否來自正確的類型,並且需要一定的時間。 您的factorCount函數只是分配一個range (1, isquare + 1)不同時間的列表,並且運行時, malloc -styled內存分配比在C中使用計數器迭代範圍要慢。值得注意的是, factorCount()被稱為多次,因此分配了很多列表。 另外,我們不要忘記,Python是被解釋的,並且CPython解釋器沒有專注於優化。

編輯 :哦,好吧,我注意到你正在使用Python 3,所以range()不會返回一個列表,而是一個生成器。 在這種情況下,我關於分配列表的觀點是錯誤的:函數只是分配range對象,雖然這樣做效率低下,但並不像分配包含很多項目的列表那樣低效。

問題2:為什麼Haskell這麼慢? 是否有編譯器標誌關閉剎車或者是我的實現? (後者很可能,因為哈斯克爾是一本有七枚印章的書。)

你在用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解釋器就不會這樣做(我的示例中只使用了Python,因為它的流暢語法)。 無論如何,如果你發現一些奇怪的東西,例如具有兩個參數的階乘函數(並且其中一個參數具有accaccumulator等名稱),現在你就知道人們為什麼這樣做了:)


問題3:您能否提供一些提示,告訴我如何優化這些實現而不改變我確定因素的方式? 以任何方式優化:更好,更快,更“原生”的語言。

C實現並不理想(正如Thomas M. DuBuisson暗示的那樣),該版本使用64位整數(即數據類型)。 稍後我會研究程序集列表,但是經過深思熟慮,編譯代碼中存在一些內存訪問,這使得使用64位整數的速度明顯變慢。 就是那個或者生成的代碼(事實上,你可以在SSE寄存器中容納更少的64位整數,或者將雙整數變為64位整數)。

這裡是修改後的代碼(只需用int替換long ,然後我明確插入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

作為參考,托馬斯在早先的答案中的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通常會生成更快的代碼。


Erlang的實現有一些問題。 作為以下的基準,我未測量的Erlang程序執行時間為47.6秒,而C代碼為12.7秒。

如果你想運行計算密集的Erlang代碼,你應該做的第一件事就是使用本地代碼。 用erlc +native euler12編譯時間縮短到41.3秒。 然而,這種代碼的本機編譯速度比預期的要低得多(只有15%),問題在於你使用了-compile(export_all) 。 這對實驗很有用,但所有函數都可以從外部訪問的事實導致本機編譯器非常保守。 (正常的BEAM模擬器沒有太大的影響。)用-export([solve/0]).替換這個聲明-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位算術進行換行”,所以除非編譯器能夠證明整數(通常不能),否則它必須檢查所有計算才能看到如果它們可以放在單個標記的單詞中,或者它們必須將它們變成堆分配的bignums。 即使在運行時實際上沒有使用過bignums,這些檢查也必須執行。 另一方面,這意味著你知道如果突然給它比以前更大的輸入,算法將永遠不會失敗,因為意外的整數迴繞。

問題4:我的功能實現是否允許LCO,從而避免在調用堆棧中添加不必要的幀?

是的,您的Erlang代碼在上次呼叫優化方面是正確的。


C++11, < 20ms for me - Run it here

I understand that you want tips to help improve your language specific knowledge, but since that has been well covered here, I thought I would add some context for people who may have looked at the mathematica comment on your question, etc, and wondered why this code was so much slower.

This answer is mainly to provide context to hopefully help people evaluate the code in your question / other answers more easily.

This code uses only a couple of (uglyish) optimisations, unrelated to the language used, based on:

  1. every traingle number is of the form n(n+1)/2
  2. n and n+1 are coprime
  3. the number of divisors is a multiplicative function

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

That takes around 19ms on average for my desktop and 80ms for my laptop, a far cry from most of the other code I've seen here. And there are, no doubt, many optimisations still available.


I made the assumption that the number of factors is only large if the numbers involved have many small factors. So I used thaumkid's excellent algorithm, but first used an approximation to the factor count that is never too small. It's quite simple: Check for prime factors up to 29, then check the remaining number and calculate an upper bound for the nmber of factors. Use this to calculate an upper bound for the number of factors, and if that number is high enough, calculate the exact number of factors.

The code below doesn't need this assumption for correctness, but to be fast. It seems to work; only about one in 100,000 numbers gives an estimate that is high enough to require a full check.

代碼如下:

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

This finds the 14,753,024th triangular with 13824 factors in about 0.7 seconds, the 879,207,615th triangular number with 61,440 factors in 34 seconds, the 12,524,486,975th triangular number with 138,240 factors in 10 minutes 5 seconds, and the 26,467,792,064th triangular number with 172,032 factors in 21 minutes 25 seconds (2.4GHz Core2 Duo), so this code takes only 116 processor cycles per number on average. The last triangular number itself is larger than 2^68, so


I modified "Jannich Brendle" version to 1000 instead 500. And list the result of euler12.bin, euler12.erl, p12dist.erl. Both erl codes use '+native' to compile.

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$

Trying GO:

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

I get:

original c version: 9.1690 100%
go: 8.2520 111%

But using:

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
}

I get:

original c version: 9.1690 100%
thaumkid's c version: 0.1060 8650%
first go version: 8.2520 111%
second go version: 0.0230 39865%

I also tried Python3.6 and pypy3.3-5.5-alpha:

original c version: 8.629 100%
thaumkid's c version: 0.109 7916%
Python3.6: 54.795 16%
pypy3.3-5.5-alpha: 13.291 65%

and then with following code I got:

original c version: 8.629 100%
thaumkid's c version: 0.109 8650%
Python3.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)

使用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'回答中的顯式遞歸。 代碼仍然執行完全相同的事情,而不用擔心尾遞歸。 它運行( 〜7.49s )比我在使用GHC 7.6.2的機器上@Thomas的答案( 〜7.04s )中的版本慢6%左右 ,而@Raedwulf的C版則運行了〜3.15s 。 GHC似乎在一年中有所改善。

PS。 我知道這是一個古老的問題,我偶然從谷歌搜索中找到它(我忘記了我正在搜索的內容,現在...)。 只想對LCO的問題發表評論,並表達我對Haskell的一般看法。 我想評論最重要的答案,但評論不允許代碼塊。


在x86_64 Core2 Duo(2.5GHz)機器上使用GHC 7.0.3gcc 4.4.6Linux 2.6.29 ,使用ghc -O2 -fllvm -fforce-recomp編譯Haskell,使用gcc -O3 -lm C。

  • 您的C例程運行時間為8.4秒(比-O3運行速度快)
  • Haskell解決方案在36秒內運行(由於-O2標誌)
  • 你的factorCount'代碼沒有明確的輸入,並且默認為Integer (感謝Daniel在這裡糾正我的誤診!)。 使用Int給出明確的類型簽名(這是標準練習),時間變為11.1秒
  • factorCount'你不必要地從整體調用。 雖然修正結果不變(編譯器很聰明,對你來說很幸運)。
  • 你使用modrem更快更充分。 這將時間更改為8.5秒
  • factorCount'不斷應用兩個額外的參數( numbersqrt )。 工人/包裝轉換為我們提供了:
 $ time ./so
 842161320  

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

沒錯, 7.95秒 。 始終比C解決方案快半秒 。 沒有-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中,使用IntegerInt慢,但慢多少取決於執行的計算。 幸運的是(對於64位機器) Int就足夠了。 為了便於使用,您應該重寫我的代碼以使用Int64Word64 (C不是唯一的語言)。

問題2:為什麼Haskell這麼慢? 是否有編譯器標誌關閉剎車或者是我的實現? (後者很可能,因為哈斯克爾是一本有七枚印章的書。)

問題3:您能否提供一些提示,告訴我如何優化這些實現而不改變我確定因素的方式? 以任何方式優化:更好,更快,更“原生”的語言。

這是我上面回答的。 答案是

  • 0)通過-O2使用優化
  • 1)盡可能使用快速(特別是:無箱式)類型
  • 2) rem不是mod (經常被遺忘的優化)和
  • 3)工人/包裝轉換(也許是最常見的優化)。

問題4:我的功能實現是否允許LCO,從而避免在調用堆棧中添加不必要的幀?

是的,那不是問題。 良好的工作,很高興你考慮到這一點


看看這個博客 。 在過去的一年左右,他在Haskell和Python中完成了Euler項目中的一些問題,並且他通常發現Haskell要快得多。 我認為在這些語言之間它更多的與你的流暢性和編碼風格有關。

說到Python速度,你使用的是錯誤的實現! 嘗試PyPy ,對於這樣的事情,你會發現它要快得多。


通過使用Haskell包中的一些函數可以大大加快你的Haskell實現。 在這種情況下,我使用了primes,它只與'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

關於Python優化,除了使用PyPy(對於代碼沒有太大變化的相當令人印象深刻的加速),您可以使用PyPy的翻譯工具鏈編譯符合RPython的版本,或者使用Cython編譯擴展模塊,這比我測試中的C版快,Cython模塊速度快了一倍 。 作為參考,我還包括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(使用最新的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版本有幾個關鍵的變化。 要翻譯成獨立的程序,您需要定義您的target ,在這種情況下是main功能。 預計接受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版本被改寫為擴展模塊_euler12.pyx ,我從一個普通的python文件中導入和調用。 _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密集的代碼位似乎是一種非常簡單的優化程序的方法。





erlang