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

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代码在最后调用优化方面是正确的。

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.

下面的代码不需要这个假设来保证正确性，但是为了快速。这似乎很有效;只有大约十万分之一的数字给出了足够高的估计，需要进行全面检查。

代码如下:

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

其中，14753024个三角形数有13824个因子用时约0.7秒，879207615个三角形数有61440个因子用时34秒，12524486975个三角形数有138240个因子用时10分5秒，26467,792064个三角形数有172032个因子用时21分25秒(2.4GHz Core2 Duo)，因此该代码平均每个数只需要116个处理器周期。最后一个三角数本身大于2^68，所以

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

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

问题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等名称)，现在你知道为什么人们这样做了:)

通过使用Haskell包中的一些函数，可以大大加快Haskell实现的速度。 在这种情况下，我使用了质数，它只是安装了'cabal安装质数';)

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

正如你所看到的，在同一台机器上，这台机器运行38毫秒，而你的机器运行16秒:)

编译命令:

ghc -O2 012.hs -o bin\012.exe
ghc -O2 012_slow.hs -o bin\012_slow.exe