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

Question

Я взял Задачу № 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 скорость из-за использования целых чисел произвольной длины или неt, если значения меньше 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

Answer 1

Использование GHC 7.0.3, gcc 4.4.6, Linux 2.6.29 на компьютере x2_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: теряют ли скорость эрланг, питон и хаскель из-за использования произвольные длины целых чисел или нет, если значения меньше чем MAXINT?

В Haskell использование Integer медленнее, чем Int, но насколько медленнее, зависит от выполненных вычислений. К счастью (для 64-битных машин) Int достаточно. Ради переносимости вам, вероятно, следует переписать мой код для использования Int64 или Word64 (C не единственный язык с long).

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

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

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

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

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

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

Answer 2

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

Answer 3

Что касается оптимизации Python, в дополнение к использованию PyPy (для довольно впечатляющего ускорения с нулевым изменением кода), вы можете использовать PyPy * toolchain для перевода для компиляции 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 кажется действительно простым способом оптимизации вашей программы.

Answer 4

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

Реализация C является неоптимальной (как намекает Томас М. Дюбюссон), в версии используются 64-битные целые числа (т. Е. long datatype). Я расскажу о листинге сборки позже, но, опираясь на осознанное предположение, в скомпилированном коде происходит несколько обращений к памяти, которые значительно замедляют использование 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 обычно генерирует более быстрый код.

Answer 5

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

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

Answer 6

Ваша реализация на 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

Answer 7

Просто для удовольствия. Ниже приведена более «нативная» реализация 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 на целые, используя 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 заинтересованному читателю.

Answer 8

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

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

EDIT : о, хорошо, я отмечаю, что вы используете Python 3, поэтому range() возвращает не список, а генератор. В этом случае моя точка зрения о распределении списков наполовину неверна: функция просто выделяет range объекты, которые, тем не менее, неэффективны, но не настолько неэффективны, как распределение списка с большим количеством элементов.

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

Используете ли вы Объятия ? Объятия - довольно медленный переводчик. Если вы используете его, возможно, вы сможете лучше провести время с 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 и т. Д.), Теперь вы знаете, почему люди делают это :)

Answer 9

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

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

Answer 10

Еще несколько цифр и пояснения к версии 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

• integertype на данный момент совпадает с исходной программой (подробнее об этом позже)
• архитектура - 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>

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

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

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

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

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

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

int не менее 32 бит
long как минимум int

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

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