Сравнение скорости с 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

Глядя на вашу реализацию 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 имеет значительные накладные расходы при запуске!

Answer 2

Вопрос 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® Rom Atom ™ TM 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

Answer 3

Попытка 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%
версия thaumkid's: 0.1060 8650%
версия первого хода: 8,2520 111%
версия второго хода: 0,0230 39865%

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

оригинальная версия c: 8.629 100%
версия thaumkid: 0.109 7916%
Python3.6: 54,795 16%
pypy3,3-5,5-alpha: 13,291 65%

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

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

Answer 4

C ++ 11, <20 мс для меня </strong> - Запустите его здесь

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

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

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

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

Answer 5

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

Кому: case (divisor(T,round(math:sqrt(T))) > 1000) of

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

Answer 6

Я сделал предположение, что число факторов велико только в том случае, если участвующие числа имеют много мелких факторов. Поэтому я использовал отличный алгоритм 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, поэтому

Answer 7

Я изменил версию "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$

Answer 8

#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

time ./a.out

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