Porównanie prędkości z projektem Euler: C vs Python vs Erlang vs Haskell

Są pewne problemy z implementacją Erlanga. Jako punkt odniesienia dla poniższego, mój zmierzony czas wykonania dla niezmodyfikowanego programu Erlang wynosił 47,6 sekundy, w porównaniu do 12,7 sekundy dla kodu C.

Pierwszą rzeczą, którą powinieneś zrobić, jeśli chcesz uruchomić intensywny obliczeniowo Kod Erlang, jest użycie kodu natywnego. Kompilacja z erlc +native euler12 zmniejszyła czas do 41,3 sekundy. Jest to jednak znacznie niższe przyspieszenie (tylko 15%) niż oczekiwano od natywnej kompilacji tego rodzaju kod, a problemem jest użycie -compile(export_all). Jest to przydatne do eksperymentowania, ale fakt, że wszystkie funkcje są potencjalnie dostępne z zewnątrz powoduje, że natywny kompilator jest bardzo konserwatywny. (Normalny emulator wiązki nie jest tak bardzo dotknięty.) Zastąpienie tej deklaracji -export([solve/0]). daje znacznie lepsze przyspieszenie: 31,5 sekundy (prawie 35% od wartości bazowej).

Ale sam kod ma problem: dla każdej iteracji W pętli factorCount wykonujesz to test:

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

Kod C tego nie robi. Ogólnie rzecz biorąc, porównanie różnych implementacji tego samego kodu może być trudne, w szczególności jeśli algorytm jest numeryczny, ponieważ musisz mieć pewność, że faktycznie robią to samo. Niewielki błąd zaokrąglania w jednej implementacji z powodu jakiegoś typecast może spowodować, że zrobi ona o wiele więcej iteracji niż druga, mimo że obie ostatecznie osiągną ten sam wynik.

Aby wyeliminować to możliwe źródło błędu (i pozbyć się dodatkowego testu w każdej iteracji), przepisałem funkcję factorCount w następujący sposób, ściśle wzorowany na kodzie 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.

To przepisanie, nie export_all, i natywna kompilacja, dały mi następujący czas wykonania:

$ erlc +native euler12.erl
$ time erl -noshell -s euler12 solve
842161320

real    0m19.468s
user    0m19.450s
sys 0m0.010s

Co nie jest takie złe w porównaniu z kodem C:

$ time ./a.out 
842161320

real    0m12.755s
user    0m12.730s
sys 0m0.020s

Biorąc pod uwagę, że Erlang wcale nie jest nastawiony na pisanie kodu numerycznego, bycie tylko 50% wolniejszym niż C w takim programie jest całkiem dobre.

Wreszcie, jeśli chodzi o Twoje pytania:

Pytanie 1: Czy erlang, python i haskell luźne prędkości ze względu na użycie dowolnych liczb całkowitych długości lub czy nie są one tak długo, jak wartości są mniejsze niż MAXINT?

Pytanie 4: Czy moje implementacje funkcjonalne pozwalają na LCO i tym samym unikają dodawania niepotrzebnych ramek na stosie wywołań?

Tak, Twój kod Erlanga jest poprawny z respect to last call optimization.

W odniesieniu do optymalizacji Pythona, oprócz korzystania z PyPy (dla imponujących przyspieszeń z zerową zmianą kodu), możesz użyć narzędzia tłumaczenia PyPy do skompilowania wersji zgodnej z RPython lub Cython do zbudowania modułu rozszerzeń, z których oba są szybsze niż wersja C w moich testach, z modułem Cython prawie dwa razy szybszym. Dla odniesienia i zawierać C i PyPy benchmark wyniki, jak również:

C (skompilowany z 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 (przy użyciu najnowszej wersji 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

Wersja RPython ma kilka kluczowych zmian. Aby przetłumaczyć na samodzielny program, musisz zdefiniować swoją target, która w tym przypadku jest funkcją main. Oczekuje się, że zaakceptuje sys.argv jako jedyny argument i jest wymagane zwrócenie int. Można go przetłumaczyć za pomocą translate.py, % translate.py euler12-rpython.py co przekłada się na C i kompiluje go dla Ciebie.

# 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

Wersja Cython została przepisana jako moduł rozszerzenia _euler12.pyx, który importuję i wywołuję ze zwykłego pliku Pythona. _euler12.pyx jest zasadniczo taka sama jak twoja wersja, z dodatkowymi deklaracjami typu statycznego. Na setup.py posiada normalną płytkę kotła do zbudowania rozszerzenia, używając 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
)

Szczerze mówiąc mam bardzo małe doświadczenie z Rpythonem lub Cythonem i byłem mile zaskoczony wynikami. Jeśli używasz CPython, pisanie intensywnych bitów kodu w module rozszerzeń Cython wydaje się naprawdę łatwym sposobem na optymalizację programu.

Pytanie 3: Czy możesz mi podać kilka wskazówek, jak zoptymalizować te wdrożenia bez zmiany sposobu określania czynników? Optymalizacja w każdym sposób: ładniejszy, szybszy, bardziej "natywny" dla języka.

Implementacja C jest nieoptymalna (jak zasugerował Thomas M. DuBuisson), wersja używa 64-bitowych liczb całkowitych (tj. long datatype). Zbadam listę zgromadzeń później, ale z wykształconym domysłem, są pewne dostępy do pamięci w skompilowanym kodzie, co sprawia, że używanie 64-bitowych liczb całkowitych jest znacznie wolniejsze. Chodzi o to, że lub wygenerowany kod (czy to fakt, że można zmieścić mniej 64-bitowych wejść w rejestrze SSE lub zaokrąglenie podwójnego do 64-bitowej liczby całkowitej jest wolniejsze).

Oto zmodyfikowany kod (po prostu zamień long na int i wyraźnie inlined factorCount, chociaż nie sądzę, że jest to konieczne z 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);
}

Running + timing it gives:

$ gcc -O3 -lm -o euler12 euler12.c; time ./euler12
842161320
./euler12  2.95s user 0.00s system 99% cpu 2.956 total

Dla odniesienia, Haskell implementacja przez Thomas we wcześniejszej odpowiedzi daje:

$ 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

Wniosek: biorąc nic z dala od ghc, to świetny kompilator, ale GCC normalnie generuje szybszy kod.

Spójrz na Ten blog . W ciągu ostatniego roku zrobił kilka problemów z projektem Euler w Haskell i Pythonie i ogólnie uznał Haskell za znacznie szybszy. Myślę, że między tymi językami ma to więcej wspólnego z Twoją płynnością i stylem kodowania.

Jeśli chodzi o szybkość Pythona, używasz niewłaściwej implementacji! Spróbuj PyPy , a za takie rzeczy okaże się, że będzie znacznie, znacznie szybciej.

Twoja implementacja Haskell może zostać znacznie przyspieszona przez użycie niektórych funkcji z pakietów Haskell. W tym przypadku użyłem primes, który jest właśnie zainstalowany z '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)

Czas:

Twój oryginalny program:

PS> measure-command { bin\012_slow.exe }

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Ulepszona implementacja

PS> measure-command { bin\012.exe }

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Jak widzisz, ten działa w 38 milisekund na tej samej maszynie, na której twoja biegła w 16 sekund:)

Polecenia kompilacji:

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

Tylko dla Zabawy. Poniżej znajduje się bardziej "natywna" implementacja Haskella:

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

Używając ghc -O3, to działa w czasie 0,55-0,58 sekundy na moim komputerze (1,73 GHz Core i7).

Bardziej wydajna funkcja factorCount dla wersji 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;
}

Zmieniając Longi na ints w main, używając gcc -O3 -lm, to konsekwentnie trwa 0,31-0,35 sekundy.

Oba mogą działać jeszcze szybciej, jeśli skorzystamy z faktu, że N-ta liczba trójkąta = n*(n+1) / 2, oraz n i (n+1) mają zupełnie różne faktoryzacje pierwsze, więc liczbę czynników każdej połowy można pomnożyć, aby znaleźć liczbę czynników całości. :

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

Skróci czas wykonywania kodu c do 0.17-0.19 sekund, i może obsłużyć znacznie większe wyszukiwania - większe niż 10000 czynników zajmuje około 43 sekund na mojej maszynie. Podobny Haskell speedup pozostawiam zainteresowanemu czytelnikowi.

Pytanie 1: Czy erlang, python i haskell tracą prędkość z powodu używania liczb całkowitych o dowolnej długości, czy nie tak długo, jak wartości są mniejsze niż MAXINT?

EDIT: no cóż, zauważam, że używasz Pythona 3 więc range() nie zwraca listy, ale generator. W tym przypadku mój punkt dotyczący przydzielania list jest w połowie błędny: funkcja po prostu przydziela range obiekty, które mimo wszystko są nieefektywne, ale nie tak nieefektywne jak przydzielanie listy z dużą ilością elementów.

Pytanie 2: Dlaczego haskell jest tak powolny? Czy istnieje flaga kompilatora, która wyłącza hamulce, czy jest to moja implementacja? (Ta ostatnia jest całkiem prawdopodobna, ponieważ haskell jest dla mnie książką z siedmioma pieczęciami.)

Czy używasz uścisków ? Uściski są bardzo powolne Tłumacz. Jeśli go używasz, może uda Ci się uzyskać lepszy czas z GHC - Ale ja tylko wymyślam hipotezę, to co robi dobry kompilator Haskell pod maską jest dość fascynujące i daleko poza moim zrozumieniem:)

Pytanie 3: Czy możesz mi podać kilka wskazówek, jak zoptymalizować te wdrożenia bez zmiany sposobu określania czynników? Optymalizacja w dowolny sposób: ładniejsza, szybsza, bardziej "natywna" dla języka.

Powiedziałbym, że grasz w unfunny gra. Najlepszą częścią znajomości różnych języków jest używanie ich w jak najbardziej różny sposób:) ale dygresję, po prostu nie mam żadnej rekomendacji do tego punktu. Przepraszam, mam nadzieję, że ktoś może Ci pomóc w tym przypadku:)

Pytanie 4: Czy moje implementacje funkcjonalne pozwalają na LCO i tym samym unikają dodawania niepotrzebnych ramek na stosie wywołań?

Z tego co pamiętam, musisz tylko upewnić się, że wywołanie rekurencyjne jest ostatnią komendą przed zwróceniem wartości. W innymi słowy, funkcja taka jak ta poniżej może użyć takiej optymalizacji:

def factorial(n, acc=1):
    if n > 1:
        acc = acc * n
        n = n - 1
        return factorial(n, acc)
    else:
        return acc

Nie miałbyś jednak takiej optymalizacji, gdyby twoja funkcja była taka jak ta poniżej, ponieważ po wywołaniu rekurencyjnym istnieje operacja (mnożenie):

def factorial2(n):
    if n > 1:
        f = factorial2(n-1)
        return f*n
    else:
        return 1

Oddzieliłem operacje w niektórych zmiennych lokalnych, aby było jasne, które operacje są wykonywane. Jednak najczęściej jest to, aby zobaczyć te funkcje jak poniżej, ale są one równoważne dla punktu jestem wykonanie:

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

Zauważ, że to kompilator / interpreter decyduje, czy rekurencja ogonowa będzie wykonywana. Na przykład interpreter Pythona nie robi tego, jeśli dobrze pamiętam (użyłem Pythona w moim przykładzie tylko ze względu na jego płynną składnię). W każdym razie, jeśli znajdziesz dziwne rzeczy, takie jak funkcje czynnikowe z dwoma parametrami (a jeden z parametrów ma nazwy takie jakacc, accumulator itd. teraz już wiesz dlaczego ludzie to robią:)

Z Haskell, naprawdę nie trzeba myśleć w rekurencjach wprost.

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

W powyższym kodzie zastąpiłem jawne rekurencje w odpowiedzi @ Thomasa operacjami common list. Kod nadal robi dokładnie to samo, nie martwiąc się o rekurencję ogonową. Biegnie (~ 7.49 S ) o 6% wolniejsza niż wersja w odpowiedzi @ Thomas (~7.04 s) na moim komputerze z GHC 7.6.2, podczas gdy Wersja C z @Raedwulf działa ~ 3.15 s. Wygląda na to, że GHC poprawiła się w ciągu roku.

PS. Wiem, że to stare pytanie i natknąłem się na nie z wyszukiwarek google (zapomniałem, co szukałem, teraz...). Chciałem tylko skomentować pytanie o LCO i wyrazić moje odczucia dotyczące Haskell w ogóle. Chciałem skomentować górną odpowiedź, ale komentarze nie pozwalają na blokowanie kodu.

Patrząc na Twoją implementację Erlanga. Czas obejmuje uruchomienie całej maszyny wirtualnej, uruchomienie programu i zatrzymanie maszyny wirtualnej. Jestem pewien, że skonfigurowanie i zatrzymanie maszyny wirtualnej erlang zajmuje trochę czasu.

Gdyby czas był wykonywany w samej maszynie wirtualnej Erlanga, wyniki byłyby inne, ponieważ w takim przypadku mielibyśmy rzeczywisty czas tylko dla danego programu. W przeciwnym razie uważam, że całkowity czas potrzebny na rozpoczęcie a Ładowanie maszyny Wirtualnej Erlang plus zatrzymanie jej (jak umieścisz ją w swoim programie) są zawarte w całkowitym czasie, którego metoda używasz do czasu, gdy program jest wyprowadzany. Rozważ użycie samego czasu erlang, którego używamy, gdy chcemy mierzyć nasze programy w samej maszynie wirtualnej timer:tc/1 or timer:tc/2 or timer:tc/3. W ten sposób wyniki z erlang wykluczą czas potrzebny na uruchomienie i zatrzymanie/zatrzymanie/zatrzymanie maszyny wirtualnej. To jest moje rozumowanie tam, pomyśl o tym i spróbuj jeszcze raz.

Właściwie sugeruję, abyśmy spróbowali mierzyć czas programu (dla języków, które mają runtime), w ramach runtime tych języków, aby uzyskać dokładną wartość. Na przykład C nie ma narzutu na uruchamianie i zamykanie systemu uruchomieniowego, podobnie jak Erlang, Python i Haskell (98% pewności tego - popieram korektę). Tak więc (na podstawie tego rozumowania) kończę mówiąc, że ten benchmark nie był precyzyjny / wystarczająco sprawiedliwy dla języków działających na szczycie runtime system. Zróbmy to jeszcze raz z tymi zmianami.

EDIT: poza tym, nawet gdyby wszystkie języki miały systemy uruchomieniowe, koszt uruchomienia każdego z nich i jego zatrzymania byłby różny. proponuję więc czas z poziomu systemów runtime(dla języków, dla których to dotyczy). Wiadomo, że maszyna wirtualna Erlang ma znaczne koszty na starcie!

Kilka liczb i wyjaśnień dla wersji C. Najwyraźniej nikt tego nie robił przez te wszystkie lata. Pamiętaj, aby upvote tej odpowiedzi, aby mógł dostać się na górę dla wszystkich, aby zobaczyć i dowiedzieć się.

Krok pierwszy: Benchmark programów autora

Dane Techniczne Laptopa:

[[22]} CPU i3 M380 (931 MHz - tryb maksymalnego oszczędzania baterii)
• pamięć 4GB
• Win7 64 bity
• Microsoft Visual Studio 2012 Ultimate
• Cygwin z gcc 4.9.3
• Python 2.7.10

Komendy:

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

Nazwy plików to: integertype_architecture_compiler.exe

• integertype jest na razie taki sam jak oryginalny program (więcej o tym później)
• Architektura to x86 lub x64 w zależności od ustawień kompilatora
• kompilator to gcc lub vs2012

VS jest o 250% szybszy niż gcc. The two Kompilatory powinny dawać podobną prędkość. Oczywiście, coś jest nie tak z kodem lub opcjami kompilatora. Zbadajmy to!

Pierwszym punktem zainteresowania są typy całkowite. Konwersje mogą być kosztowne, a spójność jest ważna dla lepszego generowania i optymalizacji kodu. Wszystkie liczby całkowite powinny być tego samego typu.

To mieszany bałagan int i long w tej chwili. Poprawimy to. Jakiego typu użyć? Najszybszy. Gotta benchmark / align = "left" /

----------
$ 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

Typami liczb całkowitych są int long int32_t uint32_t int64_t i uint64_t z #include <stdint.h>

Istnieje wiele typów liczb całkowitych w C, plus kilka podpisanych / niepodpisanych do zabawy, plus wybór kompilacji jako x86 lub x64 (nie mylić z faktycznym rozmiarem liczb całkowitych). To jest dużo wersji do kompilacji i uruchomienia ^^

Krok trzeci: zrozumienie liczb

Ostateczne wnioski:

• 32 liczby całkowite bitów są ~200% szybsze niż 64 bity odpowiedniki
• unsigned 64 bits liczby całkowite są o 25% szybsze niż signed 64 bits (niestety, nie mam na to wyjaśnienia)

Podchwytliwe pytanie: "Jakie są rozmiary int i long w C?"
Prawidłowa odpowiedź brzmi: wielkość int i long w C nie są dobrze zdefiniowane!

Z C spec:

Int ma co najmniej 32 bity
long jest co najmniej int

Ze strony podręcznika gcc (flagi-m32 i-M64):

32-bitowe środowisko ustawia int, long i pointer na 32 bity i generuje kod, który działa na dowolnym systemie i386.
Środowisko 64-bitowe ustawia int na 32 bity, a long I pointer na 64 bity i generuje kod dla architektury AMD x86-64.

Z dokumentacji MSDN (zakresy typów danych) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :

Int, 4 bajty, znany również jako signed
long, 4 bajty, zna również jako long int i signed long int

Na Zakończenie: Wyciągnięte Wnioski

• 32 liczby całkowite bitów są szybsze niż liczby całkowite 64 bitów.

• Standardowe typy liczb całkowitych nie są dobrze zdefiniowane w C ani c++, różnią się w zależności od kompilatorów i architektury. Jeśli potrzebujesz spójności i przewidywalności, użyj rodziny uint32_t integer z #include <stdint.h>.

• Problemy z prędkością rozwiązane. Wszystkie inne języki są z powrotem setki procent w tyle, C & C++ wygrać ponownie ! Jak zawsze. Następnym ulepszeniem będzie wielowątkowość przy użyciu OpenMP: d

Pytanie 1: Czy Erlang, Python i Haskell tracą prędkość z powodu używania dowolne liczby całkowite długości lub nie, o ile wartości są mniejsze niż MAXINT?

Na pytanie pierwsze można odpowiedzieć przecząco dla Erlanga. Na ostatnie pytanie odpowiada się odpowiednio używając Erlanga, jak w:

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

Ponieważ jest szybszy niż twój początkowy przykład C, domyślam się, że jest wiele problemów, ponieważ inne już szczegółowo omówione.

-module(p12dist).  
-author("Jannich Brendle, [email protected], 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.

Poniższy test odbył się na procesorze Intel(r) Atom(TM) N270 @ 1.60 GHz

~$ time erl -noshell -s p12dist start

The result is: 76576500.

^C

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

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

C++11, - Uruchom to tutaj

Rozumiem, że chcesz wskazówki, które pomogą poprawić swoją wiedzę w języku, ale ponieważ zostało to dobrze omówione tutaj, pomyślałem, że dodam trochę kontekstu dla osób, które mogły spojrzeć na komentarz mathematica na twoje pytanie, itp., i zastanawiał się, dlaczego ten kod był tak dużo wolniejszy.

ta odpowiedź ma przede wszystkim zapewnić kontekst, aby pomóc ludziom ocenić kod w twoim pytaniu / innych odpowiedzi są łatwiejsze.

Ten kod używa tylko kilku (brzydkich) optymalizacji, niezwiązanych z używanym językiem, opartych na:

1. każda liczba traingowa ma postać n (n+1) / 2
2. n I n+1 są koprimem
3. liczba dzielników jest funkcją multiplikatywną

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

To zajmuje średnio około 19ms dla mojego komputera stacjonarnego i 80ms dla mojego laptopa, dalekie od większości innych kodów, które widziałem tutaj. I nie ma, nie wątpliwości, wiele optymalizacji nadal dostępne.

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

Otrzymuję:

Oryginalna wersja c: 9.1690 100%
idź.: 8.2520 111%

Ale używając:

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
}

Otrzymuję:

Oryginalna wersja c: 9.1690 100%
wersja C thaumkid: 0.1060 8650%
pierwsza wersja go: 8.2520 111%
druga wersja go: 0.0230 39865%

Próbowałem też Python3. 6 i pypy3.3-5. 5-alfa:

Oryginalna wersja c: 8.629 100%
wersja C thaumkid: 0.109 7916%
Pyton3.6: 54.795 16%
pypy3. 3-5. 5-alfa: 13.291 65%

I z poniższego kodu otrzymałem:

Oryginalna wersja c: 8.629 100%
wersja C thaumkid: 0.109 8650%
Pyton3.6: 1.489 580%
pypy3. 3-5. 5-alfa: 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)

Change: case (divisor(T,round(math:sqrt(T))) > 500) of

Do: case (divisor(T,round(math:sqrt(T))) > 1000) of

To da poprawną odpowiedź dla przykładu wieloprocesowego Erlanga.

Założyłem, że liczba czynników jest duża tylko wtedy, gdy liczba zaangażowanych ma wiele małych czynników. Użyłem więc doskonałego algorytmu thaumkida, ale najpierw użyłem przybliżenia liczby czynników, które nigdy nie są zbyt małe. Jest to dość proste: sprawdź czynniki pierwsze do 29, a następnie sprawdź pozostałą liczbę i Oblicz górną granicę dla nmber czynników. Użyj tego, aby obliczyć górną granicę dla liczby czynników, a jeśli liczba ta jest wystarczająco wysoka, Oblicz dokładną liczba czynników.

Poniższy kod nie wymaga tego założenia dla poprawności, ale aby był szybki. Wydaje się, że działa; tylko około jedna na 100 000 liczb daje oszacowanie, które jest wystarczająco wysokie, aby wymagać pełnego sprawdzenia.

Oto kod:

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

To znajduje 14,753,024 TH trójkątny z 13824 czynniki w około 0.7 sekundy, 879,207,615 TH trójkątny Liczba z 61,440 czynniki w 34 sekund, 12,524,486,975 TH trójkątny Liczba z 138,240 czynniki w 10 minut 5 sekund, a liczba 26 467 792 064 z 172 032 współczynnikami w 21 minut 25 sekund (2,4 GHz Core2 Duo), więc kod ten zajmuje średnio tylko 116 cykli procesora na liczbę. Sama ostatnia liczba trójkątna jest większa niż 2^68, więc

Zmodyfikowałem wersję "Jannich Brendle" na 1000 zamiast 500. I wymień wynik euler12.bin, euler12erl, p12dist.erl. Oba kody erl używają '+ native ' do kompilacji.

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

2.79 s user 0.00 s system 99% cpu 2.794 total