Сравнение скорости с 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
18 ответов
С помощью GHC 7.0.3, gcc 4.4.6, Linux 2.6.29 на компьютере x86_64 Core2 Duo (2.5 ГГц), компиляция с использованием ghc -O2 -fllvm -fforce-recomp для Хаскелла и 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% медленнее, чем С в такой программе, как эта, и это очень хорошо.
Наконец, по поводу ваших вопросов:
Вопрос 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:
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;
}
Изменение длинны на целые, используя 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 для заинтересованного читателя.
Ваша реализация на 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 вам действительно не нужно явно думать о рекурсиях.
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 в целом. Я хотел прокомментировать верхний ответ, но комментарии не позволяют блоки кода.
Вопрос 1: теряют ли скорость erlang, python и haskell из-за использования целых чисел произвольной длины или нет, если значения меньше MAXINT?
Это маловероятно. Я не могу много сказать об Эрланге и Хаскелле (ну, может быть, немного о Хаскелле ниже), но я могу указать много других узких мест в Python. Каждый раз, когда программа пытается выполнить операцию с некоторыми значениями в Python, она должна проверить, соответствуют ли значения правильному типу, и это стоит немного времени. Ваш factorCount Функция просто выделяет список с range (1, isquare + 1) разное время и время выполнения, mallocвыделение памяти в стиле намного медленнее, чем итерация по диапазону со счетчиком, как в C. Примечательно, что factorCount() вызывается несколько раз и поэтому выделяет много списков. Кроме того, давайте не будем забывать, что 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 и т.д.) теперь вы знаете, почему люди это делают:)
Еще несколько цифр и объяснений для версии 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
Целочисленные типы intlongint32_tuint32_tint64_t а также uint64_t от #include <stdint.h>
Есть много целочисленных типов в C, плюс некоторые со знаком / без знака для игры, плюс возможность компилировать как x86 или x64 (не путать с фактическим целочисленным размером). Это много версий для компиляции и запуска ^^
Шаг третий: понимание чисел
Окончательные выводы:
- 32-битные целые числа ~ на 200% быстрее, чем 64-битные эквиваленты
- 64-разрядные целые числа без знака на 25% быстрее 64-разрядных со знаком (к сожалению, у меня нет объяснения этому)
Вопрос с подвохом: "Каковы размеры int и long в C?"
Правильный ответ: размер int и long в C не определены четко!
Из спецификации C:
int не менее 32 бит
долго, по крайней мере, Int
Со страницы руководства 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 int
В заключение: извлеченные уроки
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% уверены в этом - я исправляюсь). Итак (основываясь на этом рассуждении) я в заключение говорю, что этот эталонный тест не был достаточно точным / справедливым для языков, работающих поверх системы времени выполнения. Давайте сделаем это снова с этими изменениями.
РЕДАКТИРОВАТЬ: кроме того, даже если бы все языки имели системы времени выполнения, накладные расходы на запуск каждого из них и его остановку отличались бы. поэтому я предлагаю время изнутри систем времени исполнения (для языков, для которых это применимо). Эрланг 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,60 ГГц
~$ 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
Попытка 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 100%
версия Таумкида c: 0.1060 8650%
Первая версия: 8.2520 111%
второй ход версия: 0,0230 39865%
Я также попробовал Python3.6 и pypy3.3-5.5-alpha:
оригинальная версия c: 8.629 100%
версия Таумкида c: 0.109 7916%
Python3.6: 54,795 16%
pypy3,3-5,5-альфа: 13,291 65%
а затем со следующим кодом я получил:
оригинальная версия c: 8.629 100%
версия Таумкида c: 0.109 8650%
Python3.6: 1.489 580%
pypy3,3-5,5-альфа: 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)
C++11, < 20 мс для меня - запустите здесь
Я понимаю, что вам нужны советы, которые помогут улучшить ваши знания по конкретному языку, но, поскольку это хорошо освещено здесь, я подумал, что хотел бы добавить некоторый контекст для людей, которые, возможно, смотрели комментарий mathematica по вашему вопросу и т. Д., И задавался вопросом, почему это код был намного медленнее.
Этот ответ в основном предназначен для обеспечения контекста, который, как мы надеемся, поможет людям легче оценить код вашего вопроса / других ответов.
Этот код использует только пару (некрасивых) оптимизаций, не связанных с используемым языком, на основе:
- каждый номер traingle имеет вид 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 мс для моего ноутбука, что значительно отличается от большинства других кодов, которые я видел здесь. И есть, без сомнения, много оптимизаций еще доступны.
Я сделал предположение, что количество факторов велико только в том случае, если в числе участвующих факторов много мелких факторов. Поэтому я использовал отличный алгоритм 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 секунды, 879207 615-й треугольный номер с 61 440 факторами за 34 секунды, 12524 486 975-й треугольный номер с 138 240 факторами за 10 минут 5 секунд и 26 467 792 064-й треугольный номер с 172 032 факторами в 21 минута 25 секунд (2,4 ГГц Core2 Duo), поэтому этот код в среднем занимает всего 116 циклов процессора на число. Само последнее треугольное число больше 2^68, поэтому
Изменить: case (divisor(T,round(math:sqrt(T))) > 500) of
Для того, чтобы: case (divisor(T,round(math:sqrt(T))) > 1000) of
Это даст правильный ответ для примера с несколькими процессами Erlang.
Я изменил версию "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 всего