问题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通常会生成更快的代码。

尝试:

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)

看看这个博客。在过去一年左右的时间里，他用Haskell和Python完成了一些Project Euler问题，他通常发现Haskell要快得多。我认为在这些语言之间，它更多地与你的流畅性和编码风格有关。

说到Python速度，你使用了错误的实现!尝试一下PyPy，对于这样的事情，你会发现它要快得多。

Erlang实现存在一些问题。作为下面的基准，我测量的未修改的Erlang程序的执行时间为47.6秒，而C代码的执行时间为12.7秒。

(编辑:在Erlang/OTP版本24,2021年，Erlang有一个自动JIT编译器，旧的+本机编译器选项不再支持或需要。我保留下面这段文字作为历史文件。关于export_all的注释对于jit生成良好代码的能力仍然是有效的。)

The first thing you should do if you want to run computationally intensive Erlang code is to use native code. Compiling with erlc +native euler12 got the time down to 41.3 seconds. This is however a much lower speedup (just 15%) than expected from native compilation on this kind of code, and the problem is your use of -compile(export_all). This is useful for experimentation, but the fact that all functions are potentially reachable from the outside causes the native compiler to be very conservative. (The normal BEAM emulator is not that much affected.) Replacing this declaration with -export([solve/0]). gives a much better speedup: 31.5 seconds (almost 35% from the baseline).

但是代码本身有一个问题:对于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，它们不就行了吗?

Yes, somewhat. In Erlang, there is no way of saying "use 32/64-bit arithmetic with wrap-around", so unless the compiler can prove some bounds on your integers (and it usually can't), it must check all computations to see if they can fit in a single tagged word or if it has to turn them into heap-allocated bignums. Even if no bignums are ever used in practice at runtime, these checks will have to be performed. On the other hand, that means you know that the algorithm will never fail because of an unexpected integer wraparound if you suddenly give it larger inputs than before.

问题4:我的函数实现是否允许LCO，从而避免在调用堆栈中添加不必要的帧?

是的，您的Erlang代码在最后调用优化方面是正确的。

在Python优化方面，除了使用PyPy(对代码进行零更改即可获得令人印象深刻的加速)之外，还可以使用PyPy的翻译工具链编译与rpython兼容的版本，或者使用Cython构建扩展模块，在我的测试中，这两种工具都比C版本快，而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

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

崇拜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版本被重写为扩展模块_euler12。我从一个普通的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密集型代码似乎是优化程序的一种非常简单的方法。

更多关于C版本的数字和解释。显然这么多年来没人这么做过。记得给这个答案点赞，这样它就可以放在最上面，让每个人都能看到和学习。

第一步:作者程序的基准

笔记本电脑的规格:

CPU i3 M380 (931 MHz -最大省电模式) 4 gb内存 Win7 64位 微软Visual Studio 2012终极版 Cygwin与gcc 4.9.3 Python 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

文件名为:integertype_architecture_compiler.exe

Integertype目前与原始程序相同(稍后详细介绍) 架构是x86或x64，取决于编译器设置 编译器是GCC或vs2012

第二步:调查、改进和再次基准

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 long int32_t uint32_t int64_t和uint64_t from #include <stdint.h>

C语言中有很多整数类型，还有一些带符号/无符号的可以使用，还有编译为x86或x64的选择(不要与实际的整数大小混淆)。要编译和运行^^的版本太多了

第三步:理解数字

最终结论:

32位整数比64位整数快200% 无符号64位整数比有符号64位快25%(不幸的是，我对此没有解释)

陷阱问题:“C语言中int和long的大小是多少?” 正确答案是:C中int和long的大小没有很好的定义!

来自C规范:

Int至少是32位 Long至少是int型

从gcc手册页(-m32和-m64标志):

32位环境将int、long和指针设置为32位，并生成可在任何i386系统上运行的代码。 64位环境将int设置为32位，long设置为64位，指针设置为64位，并为AMD的x86-64架构生成代码。

来自MSDN文档(数据类型范围)https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx:

Int, 4字节，也是有符号的 Long, 4字节，也称为Long int和带符号的Long int

总结一下:吸取的教训

32位整数比64位整数快。 标准整数类型在C和c++中都没有很好地定义，它们取决于编译器和体系结构。当你需要一致性和可预测性时，使用uint32_t整数族从#include <stdint.h>。 速度问题解决。所有其他语言都落后百分之百，C和c++又赢了!他们总是这样。接下来的改进将是使用OpenMP:D进行多线程处理