我把“Jannich Brendle”版本改成了1000，而不是500。并列出euler12.bin, euler12.bin的结果。话务量,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$

我把“Jannich Brendle”版本改成了1000，而不是500。并列出euler12.bin, euler12.bin的结果。话务量,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$

尝试:

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

我得到:

原始版本:9.1690 100% Go: 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
}

我得到:

原始版本:9.1690 100% Thaumkid的c版本:0.1060 8650% 首发版本:8.2520 111% 第二围棋版本:0.0230 39865%

我还尝试了Python3.6和pypy3.3-5.5-alpha:

原版本:8.629 100% Thaumkid的c版本:0.109 7916% python: 54.795 16% Pypy3.3-5.5-alpha: 13.291 65%

然后用下面的代码我得到:

原版本:8.629 100% Thaumkid的c版本: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)

问题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

作为参考，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通常会生成更快的代码。

在x86_64 Core2 Duo (2.5GHz)机器上使用GHC 7.0.3, gcc 4.4.6, Linux 2.6.29，对Haskell使用GHC -O2 - flvm - force-recomp编译，对C使用gcc -O3 -lm编译。

Your C routine runs in 8.4 seconds (faster than your run probably because of -O3) The Haskell solution runs in 36 seconds (due to the -O2 flag) Your factorCount' code isn't explicitly typed and defaulting to Integer (thanks to Daniel for correcting my misdiagnosis here!). Giving an explicit type signature (which is standard practice anyway) using Int and the time changes to 11.1 seconds in factorCount' you have needlessly called fromIntegral. A fix results in no change though (the compiler is smart, lucky for you). You used mod where rem is faster and sufficient. This changes the time to 8.5 seconds. factorCount' is constantly applying two extra arguments that never change (number, sqrt). A worker/wrapper transformation gives us:

 $ time ./so
 842161320  

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

没错，7.95秒。始终比C方案快半秒。没有- flvm标志，我仍然得到8.182秒，所以NCG后端在这种情况下也做得很好。

结论:Haskell非常棒。

生成的代码

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

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

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

main = print $ nextTriangle 1 1

编辑:现在我们已经探讨了这个问题，让我们来解决问题

问题1:erlang、python和haskell是否会因为使用 任意长度的整数，只要值更小 比MAXINT ?

在Haskell中，使用Integer比Int慢，但慢多少取决于执行的计算。幸运的是(对于64位机器)Int就足够了。出于可移植性的考虑，你可能应该重写我的代码，使用Int64或Word64 (C不是唯一的语言长)。

问题2:为什么haskell这么慢?有编译器标志吗 关闭刹车还是我的实现?(后者相当 就像haskell对我来说是一本有七个印章的书一样。) 问题3:你能给我一些建议吗 实现而不改变我确定因子的方式? 以任何方式优化:更好、更快、更“原生”的语言。

这就是我上面所回答的。答案是

0)通过-O2进行优化 1)尽可能使用快速(特别是不可装箱的)类型 2) rem not mod(一个经常被遗忘的优化)和 3)工人/包装器转换(可能是最常见的优化)。

问题4:我的功能实现是否允许LCO，因此 避免添加不必要的帧到调用堆栈?

是的，这不是问题所在。干得好，很高兴你考虑到这一点。

问题1:erlang, python和haskell会因为使用任意长度的整数而降低速度吗?还是只要值小于MAXINT就不会?

This is unlikely. I cannot say much about Erlang and Haskell (well, maybe a bit about Haskell below) but I can point a lot of other bottlenecks in Python. Every time the program tries to execute an operation with some values in Python, it should verify whether the values are from the proper type, and it costs a bit of time. Your factorCount function just allocates a list with range (1, isquare + 1) various times, and runtime, malloc-styled memory allocation is way slower than iterating on a range with a counter as you do in C. Notably, the factorCount() is called multiple times and so allocates a lot of lists. Also, let us not forget that Python is interpreted and the CPython interpreter has no great focus on being optimized.

编辑:哦，好吧，我注意到你使用的是Python 3，所以range()不返回一个列表，而是一个生成器。在这种情况下，我关于分配列表的观点有一半是错误的:该函数只是分配范围对象，尽管效率很低，但没有分配包含很多项的列表那么低。

问题2:为什么haskell这么慢?是否有一个编译器标志关闭刹车或它是我的实现?(后者很有可能，因为haskell对我来说是一本有七个印章的书。)

你在使用Hugs吗?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只是因为它的语法流畅)。不管怎样，如果你发现了一些奇怪的东西，比如带两个参数的阶乘函数(其中一个参数有acc, accumulator等名称)，现在你知道为什么人们这样做了:)