Сравнение скорости с Project Euler: C против Python против Erlang против Haskell

Я взял задачу № 12 от Project Euler как упражнение по программированию и сравнил свои (безусловно, не оптимальные) реализации на C, Python, Erlang и Haskell. Чтобы получить большее время выполнения, я ищу первый номер треугольника с более чем 1000 делителями вместо 500, как указано в исходной задаче.

Результат следующий:

C:

lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c
lorenzo@enzo:~/erlang$ time ./euler12.bin
842161320

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

Python:

lorenzo@enzo:~/erlang$ time ./euler12.py 
842161320

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

Python с PyPy:

lorenzo@enzo:~/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

Erlang:

lorenzo@enzo:~/erlang$ erlc euler12.erl 
lorenzo@enzo:~/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

Haskell:

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

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

Резюме:

• C: 100%
• Python: 692% (118% с PyPy)
• Erlang: 436% (135% благодаря RichardC)
• Haskell: 1421%

Я предполагаю, что C имеет большое преимущество, так как он использует long для вычислений, а не произвольные целые числа длины, как остальные три. Также не нужно сначала загружать среду выполнения (другие?).

Вопрос 1: теряют ли Erlang, Python и Haskell скорость из-за использования целых чисел произвольной длины или нет, если значения меньше MAXINT?

Вопрос 2: Почему Haskell такой медленный? Есть флаг компилятора, который отключает тормоза, или это моя реализация? (Последнее вполне вероятно, поскольку Хаскелл для меня - книга с семью печатями.)

Вопрос 3: Можете ли вы дать мне несколько советов, как оптимизировать эти реализации, не меняя способ определения факторов? Оптимизация любым способом: приятнее, быстрее, более «родной» для языка.

РЕДАКТИРОВАТЬ:

Вопрос 4: разрешают ли мои функциональные реализации LCO (оптимизация последнего вызова, устранение хвостовой рекурсии) и, следовательно, избегают добавления ненужных кадров в стек вызовов?

Я действительно пытался реализовать один и тот же алгоритм, насколько это возможно, на четырех языках, хотя я должен признать, что мои знания Хаскелла и Эрланга очень ограничены.

Используемые исходные коды:

#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

Используя GHC 7.0.3, gcc 4.4.6, Linux 2.6.29на x86_64 Core2 Duo (2,5 ГГц) машины, компиляции , используя ghc -O2 -fllvm -fforce-recompдля Haskell и gcc -O3 -lmдля C.

• Ваша подпрограмма C выполняется за 8,4 секунды (быстрее, чем ваша, вероятно, из-за -O3)
• Решение Haskell запускается за 36 секунд (из-за -O2флага)
• Ваш factorCount'код не напечатан явно и по умолчанию Integer(спасибо Дэниелу за исправление моего неправильного диагноза здесь!). Предоставление явной подписи типа (что в любом случае является стандартной практикой) с использованием Intвремени, изменяющегося на 11,1 секунды.
• в factorCount'тебя без надобности позвонили fromIntegral. Исправление не приводит к изменениям (компилятор умен, вам повезло).
• Вы использовали modгде remбыстрее и достаточно. Это изменяет время до 8,5 секунд .
• factorCount'постоянно применяет два дополнительных аргумента, которые никогда не меняются ( number, sqrt). Преобразование рабочий / оболочка дает нам:

 $ 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 использование Integerмедленнее, чем, Intно насколько медленнее, зависит от выполненных вычислений. К счастью (для 64-битных машин) Intдостаточно. Ради переносимости вам, вероятно, следует переписать мой код для использования Int64или Word64(C не единственный язык с long).

Вопрос 2: Почему Haskell такой медленный? Есть флаг компилятора, который отключает тормоза, или это моя реализация? (Последнее вполне вероятно, поскольку haskell для меня - книга с семью печатями.)

Вопрос 3: Можете ли вы дать мне несколько советов, как оптимизировать эти реализации, не меняя способ определения факторов? Оптимизация любым способом: приятнее, быстрее, более «родной» для языка.

Это было то, что я ответил выше. Ответ был

• 0) Используйте оптимизацию через -O2
• 1) Используйте быстрые (особенно: unbox-способны) типы, когда это возможно
• 2) remнет mod(часто забытая оптимизация) и
• 3) преобразование рабочий / упаковщик (возможно, самая распространенная оптимизация).

Вопрос 4: разрешают ли мои функциональные реализации LCO и, следовательно, избегают добавления ненужных кадров в стек вызовов?

Да, это не проблема. Хорошая работа и рада, что вы обдумали это.

Есть некоторые проблемы с реализацией Erlang. В качестве базового показателя для следующего, мое измеренное время выполнения вашей немодифицированной программы Erlang составило 47,6 секунды, по сравнению с 12,7 секундами для кода C.

Первое, что вы должны сделать, если хотите запустить вычислительный код Erlang, это использовать нативный код. Компиляция с erlc +native euler12полученным временем до 41,3 секунд. Это, однако, намного более низкое ускорение (всего 15%), чем ожидалось от нативной компиляции для такого рода кода, и проблема заключается в том, как вы его используете -compile(export_all). Это полезно для экспериментов, но тот факт, что все функции потенциально доступны извне, приводит к тому, что нативный компилятор очень консервативен. (Обычный эмулятор BEAM не так сильно затронут.) Замена этого объявления -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

учитывая, что Эрланг вовсе не ориентирован на написание числового кода, он на 50% медленнее, чем C в такой программе, как это, довольно хорошо.

Наконец, по поводу ваших вопросов:

Вопрос 1: Erlang, python и haskell теряют скорость из-за использования целых чисел произвольной длины или нет, если значения меньше MAXINT?

Да, немного. В Erlang нет никакого способа сказать «использовать 32/64-битную арифметику с циклическим изменением», поэтому, если компилятор не может доказать некоторые ограничения для ваших целых чисел (а это обычно не может), он должен проверить все вычисления, чтобы увидеть могут ли они вписаться в одно помеченное слово или если оно должно превратить их в бигнумы, выделенные для кучи. Даже если на практике во время выполнения не используются никакие бигнумы, эти проверки должны быть выполнены. С другой стороны, это означает, что вы знаете, что алгоритм никогда не выйдет из строя из-за неожиданного целочисленного переноса, если вы вдруг дадите ему больше входных данных, чем раньше.

Вопрос 4: разрешают ли мои функциональные реализации LCO и, следовательно, избегают добавления ненужных кадров в стек вызовов?

Да, ваш код Erlang верен в отношении оптимизации последнего вызова.

Что касается оптимизации 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 кажется действительно простым способом оптимизации вашей программы.

Вопрос 3: Можете ли вы дать мне несколько советов, как оптимизировать эти реализации, не меняя способ определения факторов? Оптимизация любым способом: приятнее, быстрее, более «родной» для языка.

Реализация C является неоптимальной (как намекает Томас М. Дюбюссон), в версии используются 64-битные целые числа (то есть тип данных long ). Я расскажу о листинге сборки позже, но, опираясь на осознанное предположение, в скомпилированном коде происходит несколько обращений к памяти, которые значительно замедляют использование 64-битных целых чисел. Это тот или иной сгенерированный код (будь то факт, что вы можете поместить меньше 64-битных целых в регистр SSE или округлить от двойного до 64-битного целого числа медленнее).

Вот модифицированный код (просто замените long на int, и я явно указал 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 обычно генерирует более быстрый код.

Посмотрите на этот блог . За последний год или около того он сделал несколько проблем с Project Euler в Haskell и Python, и он, как правило, обнаружил, что Haskell работает намного быстрее. Я думаю, что между этими языками это больше связано с вашей беглостью и стилем кодирования.

Что касается скорости Python, вы используете неправильную реализацию! Попробуйте PyPy , и для таких вещей вы обнаружите, что это будет намного быстрее.

Ваша реализация на Haskell может быть значительно ускорена за счет использования некоторых функций из пакетов Haskell. В этом случае я использовал простые числа, которые просто устанавливаются с помощью '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

Как вы можете видеть, этот работает за 38 миллисекунд на той же машине, где ваш работал за 16 секунд :)

Команды компиляции:

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

Просто для удовольствия. Ниже приведена более «родная» реализация 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,73 ГГц Core i7).

Более эффективная функция factorCount для версии C:

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

Изменяя long в ints в main, используя gcc -O3 -lm, это последовательно выполняется за 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 для заинтересованного читателя.

Вопрос 1: Erlang, python и haskell теряют скорость из-за использования целых чисел произвольной длины или нет, если значения меньше MAXINT?

Это маловероятно. Я не могу много сказать об Эрланге и Хаскелле (ну, может, немного о Хаскелле ниже), но я могу указать много других узких мест в Python. Каждый раз, когда программа пытается выполнить операцию с некоторыми значениями в Python, она должна проверить, соответствуют ли значения правильному типу, и это стоит немного времени. Ваша factorCountфункция просто выделяет список с range (1, isquare + 1)разным временем, а mallocвыделение памяти в стиле времени выполнения намного медленнее, чем итерация по диапазону со счетчиком, как это factorCount()делается в C. В частности, он вызывается несколько раз и поэтому выделяет много списков. Кроме того, давайте не будем забывать, что Python интерпретируется, а интерпретатор CPython не уделяет большого внимания оптимизации.

РЕДАКТИРОВАТЬ : о хорошо, я отмечаю, что вы используете Python 3, поэтому range()не возвращает список, но генератор. В этом случае моя точка зрения о распределении списков наполовину неверна: функция просто выделяет rangeобъекты, которые, тем не менее, неэффективны, но не настолько неэффективны, как распределение списка с большим количеством элементов.

Вопрос 2: Почему Haskell такой медленный? Есть флаг компилятора, который отключает тормоза, или это моя реализация? (Последнее вполне вероятно, поскольку 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 в своем примере только из-за его свободного синтаксиса). В любом случае, если вы найдете странные вещи, такие как факторные функции с двумя параметрами (и у одного из параметров есть имена, такие как accи accumulatorт. Д.), Теперь вы знаете, почему люди делают это :)

С 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,49 с ) примерно на 6% медленнее, чем версия из ответа @Thomas (~ 7,04 с ), на моей машине с GHC 7.6.2, в то время как версия C из @Raedwulf работает ~ 3,15 с . Кажется, что GHC улучшилось за год.

PS. Я знаю, что это старый вопрос, и я наткнулся на него из поисков Google (я забыл, что я искал, сейчас ...). Просто хотел прокомментировать вопрос о LCO и выразить свои чувства по поводу Haskell в целом. Я хотел прокомментировать верхний ответ, но комментарии не позволяют блоки кода.

Еще несколько цифр и объяснений для версии C. Очевидно, никто не делал этого в течение всех этих лет. Не забудьте высказать этот ответ, чтобы он мог быть на вершине, чтобы все могли видеть и учиться.

Шаг первый: эталон программ автора

Характеристики ноутбука:

• CPU i3 M380 (931 МГц - режим максимального энергосбережения)
• 4 ГБ памяти
• Win7 64 бит
• Microsoft Visual Studio 2012 Ultimate
• 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

• целочисленный тип такой же, как и в оригинальной программе (подробнее об этом позже)
• архитектура x86 или x64 в зависимости от настроек компилятора
• компилятор gcc или vs2012

Шаг второй: исследовать, улучшать и снова тестировать

VS на 250% быстрее, чем gcc. Два компилятора должны дать одинаковую скорость. Очевидно, что-то не так с кодом или параметрами компилятора. Давайте исследуем!

Первый интерес представляет целочисленные типы. Преобразования могут быть дорогими, а согласованность важна для лучшей генерации и оптимизации кода. Все целые числа должны быть одного типа.

Это смешанный беспорядок 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от#include <stdint.h>

Есть много целочисленных типов в C, плюс некоторые со знаком / без знака для игры, плюс возможность компилировать как x86 или x64 (не путать с фактическим целочисленным размером). Это много версий для компиляции и запуска ^^

Шаг третий: понимание чисел

Окончательные выводы:

• 32-битные целые числа ~ на 200% быстрее, чем 64-битные эквиваленты
• 64-разрядные целые числа без знака на 25% быстрее 64-разрядных со знаком (к сожалению, у меня нет объяснения этому)

Вопрос с подвохом: «Каковы размеры int и long в C?»
Правильный ответ: размер int и long в C не определены четко!

Из спецификации C:

int - это
длина не менее 32 бит.

Со страницы руководства gcc (флаги -m32 и -m64):

32-разрядная среда устанавливает 32-разрядные значения int, long и pointer и генерирует код, который выполняется в любой системе i386.
В 64-битной среде для int устанавливается значение 32 бита и long, а для указателя - 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 со знаком

В заключение: извлеченные уроки

• 32-разрядные целые числа быстрее, чем 64-разрядные целые числа.

• Стандартные целочисленные типы плохо определены в C и C ++, они различаются в зависимости от компиляторов и архитектур. Когда вам нужна последовательность и предсказуемость, используйте uint32_tцелочисленное семейство из #include <stdint.h>.

• Проблемы со скоростью решены. Все остальные языки отстают на сотни процентов, C & C ++ снова побеждает! Они всегда делают. Следующим улучшением будет многопоточность с использованием OpenMP: D

Глядя на вашу реализацию Erlang. Время включает в себя запуск всей виртуальной машины, запуск вашей программы и остановку виртуальной машины. Я уверен, что установка и остановка erlang vm займет некоторое время.

Если бы время было выполнено в самой виртуальной машине erlang, результаты были бы другими, так как в этом случае у нас было бы реальное время только для рассматриваемой программы. В противном случае, я считаю, что общее время, затрачиваемое на процесс запуска и загрузки Erlang Vm плюс время его остановки (как вы положили это в своей программе), все включено в общее время, которое метод, который вы используете, чтобы рассчитать время Программа выводит. Рассмотрите возможность использования времени erlang, которое мы используем, когда хотим синхронизировать наши программы с самой виртуальной машиной timer:tc/1 or timer:tc/2 or timer:tc/3. Таким образом, результаты erlang исключают время, необходимое для запуска и остановки / остановки / остановки виртуальной машины. Это мое рассуждение, подумайте об этом, а затем снова попробуйте свой тест.

На самом деле я предлагаю, чтобы мы попытались синхронизировать программу (для языков, которые имеют время выполнения), в пределах времени выполнения этих языков, чтобы получить точное значение. C, например, не имеет никаких издержек запуска и выключения системы времени выполнения, как это делают Erlang, Python и Haskell (98% уверены в этом - я исправляюсь). Поэтому (основываясь на этом рассуждении) я в заключение говорю, что этот тест был недостаточно точным / справедливым для языков, работающих поверх системы времени выполнения. Давайте сделаем это снова с этими изменениями.

РЕДАКТИРОВАТЬ: кроме того, даже если бы все языки имели системы времени выполнения, накладные расходы на запуск каждого из них и его остановку отличались бы. поэтому я предлагаю время изнутри систем времени исполнения (для языков, для которых это применимо). Erlang VM, как известно, имеет значительные накладные расходы при запуске!

Вопрос 1: теряют ли Erlang, Python и Haskell скорость из-за использования целых чисел произвольной длины или нет, если значения меньше MAXINT?

На первый вопрос можно ответить отрицательно для Эрланга. На последний вопрос отвечаем, используя Erlang соответствующим образом, как в:

http://bredsaal.dk/learning-erlang-using-projecteuler-net

Так как это быстрее, чем ваш первоначальный пример C, я бы предположил, что есть множество проблем, которые другие уже подробно рассмотрели.

Этот модуль Erlang выполняется на дешевом нетбуке примерно за 5 секунд ... Он использует модель сетевых потоков в erlang и, как таковой, демонстрирует, как воспользоваться моделью событий. Это может быть распределено по многим узлам. И это быстро. Не мой код

-module(p12dist).  
-author("Jannich Brendle, jannich@bredsaal.dk, http://blog.bredsaal.dk").  
-compile(export_all).

server() ->  
  server(1).

server(Number) ->  
  receive {getwork, Worker_PID} -> Worker_PID ! {work,Number,Number+100},  
  server(Number+101);  
  {result,T} -> io:format("The result is: \~w.\~n", [T]);  
  _ -> server(Number)  
  end.

worker(Server_PID) ->  
  Server_PID ! {getwork, self()},  
  receive {work,Start,End} -> solve(Start,End,Server_PID)  
  end,  
  worker(Server_PID).

start() ->  
  Server_PID = spawn(p12dist, server, []),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]).

solve(N,End,_) when N =:= End -> no_solution;

solve(N,End,Server_PID) ->  
  T=round(N*(N+1)/2),
  case (divisor(T,round(math:sqrt(T))) > 500) of  
    true ->  
      Server_PID ! {result,T};  
    false ->  
      solve(N+1,End,Server_PID)  
  end.

divisors(N) ->  
  divisor(N,round(math:sqrt(N))).

divisor(_,0) -> 1;  
divisor(N,I) ->  
  case (N rem I) =:= 0 of  
  true ->  
    2+divisor(N,I-1);  
  false ->  
    divisor(N,I-1)  
  end.

Приведенный ниже тест проводился на: Intel (R) Atom (TM) CPU N270 @ 1.60GHz

~$ time erl -noshell -s p12dist start

The result is: 76576500.

^C

BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
       (v)ersion (k)ill (D)b-tables (d)istribution
a

real    0m5.510s
user    0m5.836s
sys 0m0.152s

C ++ 11, <20 мс для меня - запустите здесь

Я понимаю, что вам нужны советы, которые помогут улучшить ваши знания по конкретному языку, но, поскольку это хорошо освещено здесь, я подумал, что хотел бы добавить некоторый контекст для людей, которые, возможно, посмотрели комментарий mathematica по вашему вопросу и т. Д., И задавался вопросом, почему это код был намного медленнее.

Этот ответ в основном предназначен для обеспечения контекста, который, как мы надеемся, поможет людям легче оценить код вашего вопроса / других ответов.

Этот код использует только несколько (некрасивых) оптимизаций, не связанных с используемым языком, на основе:

1. каждый номер traingle имеет вид n (n + 1) / 2
2. n и n + 1 взаимно просты
3. число делителей является мультипликативной функцией

#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 мс для моего ноутбука, что сильно отличается от большинства других кодов, которые я видел здесь. И есть, без сомнения, много оптимизаций еще доступны.

Попытка 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
        }
    }
}

Я получил:

оригинальная версия c: 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
}

Я получил:

оригинальная версия c: 9.1690 версия c 100%
thaumkid: 0.1060 8650%
версия первого хода: 8.2520 111%
вторая версия go: 0.0230 39865%

Я также попробовал Python3.6 и pypy3.3-5.5-alpha:

оригинальная c версия: 8.629 100%
thaumkid's c версия: 0.109 7916%
Python3.6: 54.795 16%
pypy3.3-5.5-alpha: 13.291 65%

а затем со следующим кодом я получил:

оригинальная c версия: 8.629 100%
thaumkid's 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)

Изменить: case (divisor(T,round(math:sqrt(T))) > 500) of

Для того, чтобы: case (divisor(T,round(math:sqrt(T))) > 1000) of

Это даст правильный ответ для примера с несколькими процессами Erlang.

Я сделал предположение, что число факторов велико только в том случае, если в числе участвующих факторов много мелких факторов. Поэтому я использовал отличный алгоритм thaumkid, но сначала использовал приближение к числу факторов, которое никогда не бывает слишком маленьким. Все довольно просто: проверьте простые факторы до 29, затем проверьте оставшееся число и вычислите верхнюю границу для числа факторов. Используйте это, чтобы вычислить верхнюю границу для числа факторов, и, если это число достаточно велико, рассчитайте точное количество факторов.

Приведенный ниже код не нуждается в этом допущении для правильности, но чтобы быть быстрым. Это похоже на работу; только один из 100 000 номеров дает оценку, которая достаточно высока, чтобы потребовать полной проверки.

Вот код:

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

Это находит 14 753 024-й треугольник с 13824 факторами за 0,7 секунды, 879 207 615-й треугольный номер с 61 440 факторами за 34 секунды, 12 524 486 975-й треугольный номер с 138 240 факторами за 10 минут 5 секунд и 26 467 792 064-й треугольный номер с 172 032 факторами в 21 минута 25 секунд (2,4 ГГц Core2 Duo), поэтому этот код в среднем занимает всего 116 циклов процессора на число. Последнее само треугольное число больше 2 ^ 68, поэтому

Я изменил версию «Jannich Brendle» на 1000 вместо 500. И перечислим результат euler12.bin, euler12.erl, 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$

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square+1;
    long candidate = 2;
    int count = 1;
    while(candidate <= isquare && candidate<=n){
        int c = 1;
        while (n % candidate == 0) {
           c++;
           n /= candidate;
        }
        count *= c;
        candidate++;
    }
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

gcc -lm -Ofast euler.c

время ./a.out

2.79s пользователь 0.00s система 99% процессор 2.794 всего