在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，因此 避免添加不必要的帧到调用堆栈?

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

c++ 11， < 20ms for me -在这里运行它

我理解您想要一些技巧来帮助提高您的语言特定知识，但由于这里已经很好地介绍了这一点，我想我应该为那些可能看过您的问题的mathematica注释等并想知道为什么这段代码如此之慢的人添加一些上下文。

这个答案主要是为了提供上下文，希望能够帮助人们更容易地评估您的问题/其他答案中的代码。

这段代码只使用了一些(丑陋的)优化，与所使用的语言无关，基于:

每个三角数的形式都是n(n+1)/2 N和N +1是互质 除数的数量是一个乘法函数

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

我的台式机平均花费19毫秒，笔记本电脑平均花费80毫秒，这与我在这里看到的大多数其他代码相差甚远。毫无疑问，还有许多优化方法可用。

在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密集型代码似乎是优化程序的一种非常简单的方法。

在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，因此 避免添加不必要的帧到调用堆栈?

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

只是为了好玩。下面是一个更“原生”的Haskell实现:

import Control.Applicative
import Control.Monad
import Data.Either
import Math.NumberTheory.Powers.Squares

isInt :: RealFrac c => c -> Bool
isInt = (==) <$> id <*> fromInteger . round

intSqrt :: (Integral a) => a -> Int
--intSqrt = fromIntegral . floor . sqrt . fromIntegral
intSqrt = fromIntegral . integerSquareRoot'

factorize :: Int -> [Int]
factorize 1 = []
factorize n = first : factorize (quot n first)
  where first = (!! 0) $ [a | a <- [2..intSqrt n], rem n a == 0] ++ [n]

factorize2 :: Int -> [(Int,Int)]
factorize2 = foldl (\ls@((val,freq):xs) y -> if val == y then (val,freq+1):xs else (y,1):ls) [(0,0)] . factorize

numDivisors :: Int -> Int
numDivisors = foldl (\acc (_,y) -> acc * (y+1)) 1 <$> factorize2

nextTriangleNumber :: (Int,Int) -> (Int,Int)
nextTriangleNumber (n,acc) = (n+1,acc+n+1)

forward :: Int -> (Int, Int) -> Either (Int, Int) (Int, Int)
forward k val@(n,acc) = if numDivisors acc > k then Left val else Right (nextTriangleNumber val)

problem12 :: Int -> (Int, Int)
problem12 n = (!!0) . lefts . scanl (>>=) (forward n (1,1)) . repeat . forward $ n

main = do
  let (n,val) = problem12 1000
  print val

使用ghc -O3，它在我的机器上持续运行0.55-0.58秒(1.73GHz Core i7)。

C版本中一个更有效的factorCount函数:

int factorCount (int n)
{
  int count = 1;
  int candidate,tmpCount;
  while (n % 2 == 0) {
    count++;
    n /= 2;
  }
    for (candidate = 3; candidate < n && candidate * candidate < n; candidate += 2)
    if (n % candidate == 0) {
      tmpCount = 1;
      do {
        tmpCount++;
        n /= candidate;
      } while (n % candidate == 0);
       count*=tmpCount;
      }
  if (n > 1)
    count *= 2;
  return count;
}

在main中使用gcc -O3 -lm将long类型更改为int类型，该程序始终在0.31-0.35秒内运行。

如果您利用第n个三角形数= n*(n+1)/2，并且n和(n+1)具有完全不同的质因数分解，则可以使两者运行得更快，因此可以将每个一半的因数数相乘，以得到整体的因数数。以下几点:

int main ()
{
  int triangle = 0,count1,count2 = 1;
  do {
    count1 = count2;
    count2 = ++triangle % 2 == 0 ? factorCount(triangle+1) : factorCount((triangle+1)/2);
  } while (count1*count2 < 1001);
  printf ("%lld\n", ((long long)triangle)*(triangle+1)/2);
}

将c代码的运行时间减少到0.17-0.19秒，它可以处理更大的搜索——大于10000个因数在我的机器上大约需要43秒。我给感兴趣的读者留下了类似的haskell加速。

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