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

Wziąłem Problem nr 12 z Project Euler jako ćwiczenie programistyczne i do porównania moich (na pewno nie optymalnych) implementacji w C, Python, Erlang i Haskell. Aby uzyskać wyższe czasy wykonania, szukam pierwszego numeru trójkąta z więcej niż 1000 dzielników zamiast 500, jak podano w pierwotnym problemie.

Wynik jest następujący:

DO:

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

Pyton:

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

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

Python z 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

Podsumowanie:

• C: 100%
• Python: 692% (118% z PyPy)
• Erlang: 436% (135% dzięki RichardC)
• Haskell: 1421%

Przypuszczam, że C ma dużą zaletę, ponieważ używa długich do obliczeń, a nie liczb całkowitych o dowolnej długości, jak pozostałe trzy. Ponadto nie musi najpierw ładować środowiska wykonawczego (czy inne?).

Pytanie 1: Czy Erlang, Python i Haskell tracą prędkość z powodu użycia liczb całkowitych o dowolnej długości, czy też nie, dopóki wartości są mniejsze niż MAXINT?

Pytanie 2: Dlaczego Haskell jest taki wolny? Czy istnieje flaga kompilatora, która wyłącza hamulce, czy jest to moja implementacja? (To ostatnie jest całkiem prawdopodobne, ponieważ Haskell to książka z siedmioma pieczęciami).

Pytanie 3: Czy możesz mi podpowiedzieć, jak zoptymalizować te wdrożenia bez zmiany sposobu określania czynników? Optymalizacja w jakikolwiek sposób: ładniejsza, szybsza, bardziej „natywna” dla języka.

EDYTOWAĆ:

Pytanie 4: Czy moje implementacje funkcjonalne pozwalają na LCO (optymalizacja ostatniego połączenia, czyli eliminację rekurencji ogona), a tym samym unikają dodawania niepotrzebnych ramek do stosu połączeń?

Naprawdę próbowałem zaimplementować ten sam algorytm jak najbardziej podobny w czterech językach, chociaż muszę przyznać, że moja znajomość Haskell i Erlang jest bardzo ograniczona.

Zastosowane kody źródłowe:

#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

Korzystanie GHC 7.0.3, gcc 4.4.6, Linux 2.6.29na x86_64 Core 2 Duo (2,5 GHz) maszyny, tworzenia stosując ghc -O2 -fllvm -fforce-recompdo Haskell gcc -O3 -lmC.

• Twoja procedura C działa w 8,4 sekundy (prawdopodobnie szybciej niż bieg, prawdopodobnie z powodu -O3)
• Rozwiązanie Haskell działa w ciągu 36 sekund (z powodu -O2flagi)
• Twój factorCount'kod nie jest wyraźnie wpisany i domyślnie ustawiony Integer(dzięki Danielowi za naprawienie mojej błędnej diagnozy tutaj!). Nadanie wyraźnego podpisu typu (co i tak jest standardową praktyką) przy użyciu, Inta czas zmienia się na 11,1 sekundy
• w factorCount'tobie niepotrzebnie zadzwoniłeś fromIntegral. Poprawka skutkuje jednak brakiem zmian (kompilator jest inteligentny, na szczęście dla ciebie).
• Użyłeś modgdzie remjest szybszy i wystarczający. To zmienia czas na 8,5 sekundy .
• factorCount'stale stosuje dwa dodatkowe argumenty, które nigdy się nie zmieniają ( number, sqrt). Transformacja pracownik / opakowanie zapewnia nam:

 $ time ./so
 842161320  

 real    0m7.954s  
 user    0m7.944s  
 sys     0m0.004s  

Zgadza się, 7,95 sekundy . Konsekwentnie pół sekundy szybciej niż roztwór C . Bez -fllvmflagi wciąż otrzymuję 8.182 seconds, więc backend NCG ma się dobrze również w tym przypadku.

Wniosek: Haskell jest niesamowity.

Wynikowy kod

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

EDYCJA: Teraz, kiedy to zbadaliśmy, odpowiedzmy na pytania

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

W Haskell użycie Integerjest wolniejsze niż, Intale o ile wolniejsze, zależy od wykonanych obliczeń. Na szczęście (dla maszyn 64-bitowych) Intwystarczy. Ze względu na przenośność powinieneś prawdopodobnie przepisać mój kod do użycia Int64lub Word64(C nie jest jedynym językiem z long).

Pytanie 2: Dlaczego Haskell jest taki wolny? Czy istnieje flaga kompilatora, która wyłącza hamulce, czy jest to moja implementacja? (To ostatnie jest całkiem prawdopodobne, ponieważ haskell to książka z siedmioma pieczęciami).

Pytanie 3: Czy możesz mi podpowiedzieć, jak zoptymalizować te wdrożenia bez zmiany sposobu określania czynników? Optymalizacja w jakikolwiek sposób: ładniejsza, szybsza, bardziej „natywna” dla języka.

Tak odpowiedziałem powyżej. Odpowiedź brzmiała:

• 0) Użyj optymalizacji przez -O2
• 1) Jeśli to możliwe, używaj szybkich (zwłaszcza: nieobsługiwanych) typów
• 2) remnie mod(często zapomniana optymalizacja) i
• 3) transformacja pracownik / opakowanie (być może najczęstsza optymalizacja).

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

Tak, to nie był problem. Dobra robota i cieszę się, że to rozważałeś.

Występują pewne problemy z implementacją Erlang. Jako punkt odniesienia dla następującego, mój zmierzony czas wykonania dla niezmodyfikowanego programu Erlang wyniósł 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 Erlanga, jest użycie kodu natywnego. Kompilacja z erlc +native euler12zmniejszyła czas do 41,3 sekundy. Jest to jednak znacznie niższe przyspieszenie (tylko 15%) niż oczekiwano po kompilacji natywnej na tego rodzaju kodzie, a problemem jest twoje użycie -compile(export_all). Jest to przydatne w eksperymentach, ale fakt, że wszystkie funkcje są potencjalnie dostępne z zewnątrz, powoduje, że natywny kompilator jest bardzo konserwatywny. (Normalny emulator BEAM nie ma tak dużego wpływu). Zastąpienie tej deklaracji -export([solve/0]).daje znacznie lepsze przyspieszenie: 31,5 sekundy (prawie 35% od wartości początkowej).

Ale sam kod ma problem: dla każdej iteracji w pętli factorCount wykonuje się ten test:

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

Kod C tego nie robi. Generalnie rzetelne porównanie różnych implementacji tego samego kodu może być trudne, szczególnie jeśli algorytm jest numeryczny, ponieważ musisz mieć pewność, że faktycznie robią to samo. Niewielki błąd zaokrąglenia w jednej implementacji spowodowany gdzieś rzutem czcionki może spowodować, że wykona on o wiele więcej iteracji niż w drugiej, mimo że obie ostatecznie osiągną ten sam wynik.

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

Ta przepisana, nie export_alli natywna kompilacja dała mi następujący czas działania:

$ 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 do kodu 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, jest o 50% wolniejszy niż C w takim programie jak ten, co jest całkiem dobre.

Wreszcie odnośnie twoich pytań:

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

Tak, trochę. W Erlang nie można powiedzieć „używaj arytmetyki 32/64-bitowej z zawijaniem”, więc jeśli kompilator nie udowodni pewnych ograniczeń na liczbach całkowitych (i zwykle nie może), musi sprawdzić wszystkie obliczenia, aby zobaczyć jeśli mogą zmieścić się w jednym oznakowanym słowie lub jeśli musi zamienić je w bignum alokowane na stercie. Nawet jeśli w środowisku wykonawczym nigdy nie są używane bignum, kontrole te należy wykonać. Z drugiej strony oznacza to , że wiesz, że algorytm nigdy nie zawiedzie z powodu nieoczekiwanego zawinięcia liczb całkowitych, jeśli nagle podasz mu większe dane wejściowe niż wcześniej.

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

Tak, Twój kod Erlang jest poprawny w odniesieniu do optymalizacji ostatniego połączenia.

Jeśli chodzi o optymalizację Pythona, oprócz korzystania z PyPy (w celu uzyskania imponujących przyspieszeń przy zerowej zmianie kodu), możesz użyć łańcucha narzędzi do tłumaczenia PyPy do skompilowania wersji zgodnej z RPython lub Cython do zbudowania modułu rozszerzenia, zarówno które są szybsze niż wersja C w moich testach, z modułem Cython prawie dwa razy szybszym . Dla porównania dołączam również wyniki testu porównawczego C i PyPy:

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ć swój target, który w tym przypadku jest mainfunkcją. Oczekuje się, że zostanie zaakceptowany, sys.argvponieważ jest to tylko argument, i wymagane jest zwrócenie wartości int. Możesz to przetłumaczyć za pomocą translate.py, % translate.py euler12-rpython.pyktóry tłumaczy na C i kompiluje 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ę z normalnego pliku python. Jest _euler12.pyxto zasadniczo taki sam jak wersja, z pewnymi dodatkowymi deklaracjami typu statycznego. Plik setup.py ma normalną płytę kotłową 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 RPython lub Cython i byłem mile zaskoczony wynikami. Jeśli używasz CPython, pisanie fragmentów kodu obciążających procesor w module rozszerzenia Cython wydaje się bardzo łatwym sposobem na optymalizację programu.

Pytanie 3: Czy możesz mi podpowiedzieć, jak zoptymalizować te wdrożenia bez zmiany sposobu określania czynników? Optymalizacja w jakikolwiek sposób: ładniejsza, szybsza, bardziej „natywna” dla języka.

Implementacja C jest nieoptymalna (jak wskazał Thomas M. DuBuisson), wersja używa 64-bitowych liczb całkowitych (tj. Długi typ danych). Później zbadam listę zestawów, ale przy zgadywanym przypuszczeniu, w skompilowanym kodzie dzieje się dostęp do pamięci, co znacznie spowalnia użycie 64-bitowych liczb całkowitych. Jest to ten lub wygenerowany kod (fakt, że możesz zmieścić mniej 64-bitowych liczb całkowitych w rejestrze SSE lub zaokrąglić liczbę podwójną do 64-bitowej liczby całkowitej, jest wolniejszy).

Oto zmodyfikowany kod (wystarczy wymienić długo z int i jawnie 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);
}

Bieganie + synchronizacja daje:

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

Dla porównania, implementacja haskell przez Thomasa 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: nie bierze nic od ghc, jest to świetny kompilator, ale gcc zwykle generuje szybszy kod.

Spójrz na tego bloga . W ciągu ostatniego roku zrobił kilka problemów z Project Euler w Haskell i Python i ogólnie stwierdził, że Haskell jest 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! Wypróbuj PyPy , a dla takich rzeczy znajdziesz to znacznie, dużo szybciej.

Implementację Haskell można znacznie przyspieszyć, korzystając z niektórych funkcji z pakietów Haskell. W tym przypadku użyłem liczb pierwszych, które są właśnie instalowane z „liczbami początkowymi instalacji cabal”;)

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)

Czasy:

Twój oryginalny program:

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

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Ulepszone wdrożenie

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

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Jak widać, ten działa w 38 milisekundach na tej samej maszynie, na której działał w 16 sekund :)

Polecenia kompilacji:

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

Dla żartu. Poniżej przedstawiono bardziej „natywną” implementację 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

Korzystanie z ghc -O3tego działa konsekwentnie w 0,55-0,58 sekund na moim komputerze (1,73 GHz Core i7).

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

Zmiana gcc -O3 -lmlongs na ints w main, przy użyciu , to konsekwentnie działa w 0,31-0,35 sekund.

Oba mogą działać jeszcze szybciej, jeśli skorzystasz z faktu, że n-ty numer trójkąta = n * (n + 1) / 2, oraz n oraz (n + 1) mają całkowicie odmienne czynniki pierwsze, więc liczba czynników każdej połowy można pomnożyć, aby znaleźć liczbę czynników całości. Następujące:

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 działania kodu c do 0,17-0,19 sekund i może obsługiwać znacznie większe wyszukiwania - ponad 10000 czynników zajmuje około 43 sekund na moim komputerze. Zainteresowanemu czytelnikowi pozostawiam podobne przyspieszenie haskell.

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

To mało prawdopodobne. Nie mogę wiele powiedzieć o Erlangu i Haskellu (cóż, może trochę o Haskellu poniżej), ale mogę wskazać wiele innych wąskich gardeł w Pythonie. Za każdym razem, gdy program próbuje wykonać operację z pewnymi wartościami w Pythonie, powinien sprawdzić, czy wartości pochodzą z właściwego typu, i kosztuje to trochę czasu. Twoja factorCountfunkcja po prostu przydziela listę z range (1, isquare + 1)różnymi czasami i czasem działania,malloc alokacja pamięci w uruchomieniowym jest znacznie wolniejsza niż iteracja w zakresie z licznikiem, tak jak w przypadku C. W szczególności, factorCount()wywoływana jest wiele razy, a więc przydziela wiele list. Nie zapominajmy również, że Python jest interpretowany, a interpreter CPython nie koncentruje się na optymalizacji.

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

Pytanie 2: Dlaczego Haskell jest taki wolny? Czy istnieje flaga kompilatora, która wyłącza hamulce, czy jest to moja implementacja? (To ostatnie jest całkiem prawdopodobne, ponieważ haskell to książka z siedmioma pieczęciami).

Czy używasz uścisków ? Uściski są znacznie powolnym tłumaczem. Jeśli go używasz, być może możesz uzyskać lepszy czas z GHC spędzić - ale jestem tylko apogeum hipotezy, takie rzeczy, które dobry kompilator Haskell robi pod maską, jest dość fascynujące i daleko poza moim zrozumieniem :)

Pytanie 3: Czy możesz mi podpowiedzieć, jak zoptymalizować te wdrożenia bez zmiany sposobu określania czynników? Optymalizacja w jakikolwiek sposób: ładniejsza, szybsza, bardziej „natywna” dla języka.

Powiedziałbym, że grasz w zabawną grę. Najlepszą częścią znajomości różnych języków jest używanie ich w jak najbardziej odmienny sposób :) Ale dygresję, po prostu nie mam żadnych rekomendacji w tym zakresie. Przepraszam, mam nadzieję, że ktoś może ci w tym pomóc :)

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

O ile pamiętam, musisz tylko upewnić się, że wywołanie rekurencyjne jest ostatnim poleceniem przed zwróceniem wartości. Innymi słowy, funkcja taka jak ta poniżej mogłaby 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

Jednak nie byłoby 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

Rozdzieliłem operacje na niektóre zmienne lokalne, aby było jasne, które operacje są wykonywane. Jednak najczęściej spotyka się te funkcje jak poniżej, ale są one równoważne z tym, o czym mówię:

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 od kompilatora / tłumacza należy decyzja, czy wykona rekursję ogona. Na przykład interpreter języka Python nie robi tego, jeśli dobrze pamiętam (użyłem Python w moim przykładzie tylko ze względu na jego płynną składnię). W każdym razie, jeśli okaże się dziwne rzeczy, takie jak czynnikowych funkcji z dwoma parametrami (i jeden z parametrów ma nazwy, takie jak acc, accumulatoritd.), Teraz wiesz, dlaczego ludzie to zrobić :)

Dzięki Haskell naprawdę nie musisz myśleć wyraźnie o rekurencjach.

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 @Thomas zwykłymi operacjami na liście. Kod nadal robi dokładnie to samo, nie martwiąc się o rekurencję ogona. Działa (~ 7,49s ) około 6% wolniej niż wersja w odpowiedzi @Thomas (~ 7,04s ) na moim komputerze z GHC 7.6.2, podczas gdy wersja C z @Raedwulf działa ~ 3,15s . Wygląda na to, że GHC poprawił się w ciągu roku.

PS. Wiem, że to stare pytanie, i natknąłem się na nie z wyszukiwań w Google (teraz zapomniałem, czego szukałem ...). Chciałem tylko skomentować pytanie dotyczące LCO i wyrazić swoje odczucia na temat Haskell w ogóle. Chciałem skomentować najwyższą odpowiedź, ale komentarze nie pozwalają na bloki kodu.

Więcej liczb i objaśnień dla wersji C. Najwyraźniej nikt nie robił tego przez te wszystkie lata. Pamiętaj, aby głosować na tę odpowiedź, aby wszyscy mogli ją zobaczyć i nauczyć się.

Krok pierwszy: Benchmark programów autora

Specyfikacja laptopa:

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

Polecenia:

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

• liczba całkowita jest na razie taka sama jak oryginalny program (więcej na ten temat później)
• architektura to x86 lub x64 w zależności od ustawień kompilatora
• Kompilator to gcc lub vs2012

Krok drugi: ponownie zbadaj, ulepsz i przetestuj

VS jest o 250% szybszy niż gcc. Dwa kompilatory powinny dać podobną prędkość. Oczywiście coś jest nie tak z kodem lub opcjami kompilatora. Zbadajmy!

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

To mieszany bałagan inti longteraz. Zamierzamy to poprawić. Jakiego typu użyć? Najszybszy. Muszę je wszystkie porównać!

----------
$ 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 całkowitymi są int long int32_t uint32_t int64_tiuint64_t od#include <stdint.h>

W C znajduje się DUŻO liczb całkowitych, plus niektóre podpisane / niepodpisane do zabawy, plus wybór kompilacji jako x86 lub x64 (nie mylić z rzeczywistym rozmiarem całkowitym). To jest wiele wersji do skompilowania i uruchomienia ^^

Krok trzeci: Zrozumienie liczb

Ostateczne wnioski:

• 32-bitowe liczby całkowite są ~ 200% szybsze niż 64-bitowe odpowiedniki
• 64-bitowe liczby całkowite bez znaku są o 25% szybsze niż 64-bitowe ze znakiem (Niestety, nie mam na to wytłumaczenia)

Trikowe pytanie: „Jakie są rozmiary int i long w C?”
Prawidłowa odpowiedź to: wielkość int i długa w C nie są dobrze zdefiniowane!

Ze specyfikacji C:

int ma
długość co najmniej 32 bity, co najmniej int

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

32-bitowe środowisko ustawia int, long i wskaźnik na 32 bity i generuje kod, który działa na dowolnym systemie i386.
64-bitowe środowisko ustawia int na 32 bity, a długi wskaźnik 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, również zna jako podpisane
długie, 4 bajty, również zna jako długie int i podpisane long int

Podsumowując: wyciągnięte wnioski

• Liczby całkowite 32-bitowe są szybsze niż liczby całkowite 64-bitowe.

• Standardowe typy liczb całkowitych nie są dobrze zdefiniowane w C ani C ++, różnią się w zależności od kompilatorów i architektur. Gdy potrzebujesz spójności i przewidywalności, użyj uint32_trodziny liczb całkowitych od#include <stdint.h> .

• Rozwiązane problemy z prędkością. Wszystkie pozostałe języki mają setki procent opóźnień, C & C ++ znów wygrywają! Zawsze tak robią. Kolejnym ulepszeniem będzie wielowątkowość z wykorzystaniem OpenMP: D

Patrząc na twoją implementację Erlang. Czas obejmował uruchomienie całej maszyny wirtualnej, uruchomienie programu i zatrzymanie maszyny wirtualnej. Jestem pewien, że konfiguracja i zatrzymanie erlang vm zajmuje trochę czasu.

Gdyby czas został wykonany w samej maszynie wirtualnej erlang, 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 uruchomienie i załadowanie Erlang Vm plus czas jego zatrzymania (jak umieściłeś w swoim programie) są wliczone do całkowitego czasu, którego używasz do pomiaru czasu program się wyświetla. Rozważ użycie samego czasu Erlanga, którego używamy, gdy chcemy mierzyć czas naszych programów 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 do uruchomienia i zatrzymania / zabicia / zatrzymania maszyny wirtualnej. Takie jest moje rozumowanie, zastanów się nad tym, a następnie spróbuj jeszcze raz.

Właściwie sugeruję, abyśmy spróbowali zmierzyć czas programu (dla języków, które mają środowisko wykonawcze), w ramach środowiska uruchomieniowego tych języków, aby uzyskać dokładną wartość. Na przykład C nie ma narzutów związanych z uruchamianiem i zamykaniem systemu uruchomieniowego, podobnie jak Erlang, Python i Haskell (98% pewności tego - ja poprawiam). Tak więc (w oparciu o to rozumowanie) stwierdzam, że ten test porównawczy nie był wystarczająco precyzyjny / sprawiedliwy dla języków działających na systemie uruchomieniowym. Zróbmy to jeszcze raz z tymi zmianami.

EDYCJA: poza tym, nawet jeśli wszystkie języki miałyby systemy wykonawcze, narzut związany z uruchomieniem każdego z nich i jego zatrzymaniem byłby inny. więc sugeruję, abyśmy spędzili czas z poziomu systemów uruchomieniowych (dla języków, których dotyczy). Wirtualna maszyna Erlang znana jest z dużego obciążenia podczas uruchamiania!

Pytanie 1: Czy Erlang, Python i Haskell tracą prędkość z powodu użycia liczb całkowitych o dowolnej długości, czy też nie, o ile wartości są mniejsze niż MAKSYMALNA?

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

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

Ponieważ jest szybszy niż twój początkowy przykład C, sądzę, że istnieje wiele problemów, które inni już szczegółowo opisali.

Ten moduł Erlang wykonuje się na tanim netbooku w około 5 sekund ... Używa modelu wątków sieciowych w erlang i jako taki pokazuje, jak skorzystać z modelu zdarzeń. Może być rozłożony na wiele węzłów. I to jest szybkie. Nie mój kod.

-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.60GHz

~$ time erl -noshell -s p12dist start

The result is: 76576500.

^C

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

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

C ++ 11, <20ms dla mnie - Uruchom tutaj

Rozumiem, że potrzebujesz wskazówek, które pomogą Ci poprawić znajomość języka, ale ponieważ zostało to tutaj dobrze omówione, pomyślałem, że dodam kontekst dla osób, które mogły spojrzeć na komentarz matematyczny do twojego pytania itp., I zastanawiałem się, dlaczego to kod był o wiele wolniejszy.

Ta odpowiedź ma przede wszystkim na celu zapewnienie kontekstu, aby, miejmy nadzieję, pomóc innym w łatwiejszym ocenie kodu w pytaniu / innych odpowiedziach.

Ten kod wykorzystuje tylko kilka (brzydkich) optymalizacji, niezwiązanych z używanym językiem, w oparciu o:

1. każda liczba traingle ma postać n (n + 1) / 2
2. n i n + 1 są chronione prawem autorskim
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 19 ms dla mojego komputera stacjonarnego i 80 ms dla mojego laptopa, co jest dalekie od większości innych kodów, które tu widziałem. I bez wątpienia dostępnych jest jeszcze wiele optymalizacji.

Próbuję 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
        }
    }
}

Dostaję:

oryginalna wersja c: 9.1690 100%
go: 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
}

Dostaję:

oryginalna wersja c: 9.1690 100%
thaumkid's wersja c: 0.1060 8650%
pierwsza wersja: 8.2520 111%
druga wersja: 0.0230 39865%

Próbowałem także Python3.6 i pypy3.5-5.5-alpha:

oryginalna wersja c: 8.629 100%
thaumkid's wersja c: 0.109 7916%
Python3.6: 54,795 16%
pypy3,3-5,5-alfa: 13,291 65%

a następnie z następującym kodem mam:

oryginalna wersja c: 8.629 100%
thaumkid's wersja c: 0.109 8650%
Python3.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)

Zmiana: 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 Erlang.

Przyjąłem założenie, że liczba czynników jest duża tylko wtedy, gdy zaangażowane liczby mają wiele małych czynników. Użyłem więc doskonałego algorytmu thaumkida, ale najpierw zastosowałem przybliżenie liczby czynników, która nigdy nie jest zbyt mała. To bardzo proste: sprawdź czynniki pierwsze do 29, a następnie sprawdź pozostałą liczbę i oblicz górną granicę dla liczby czynników. Użyj tego, aby obliczyć górną granicę liczby czynników, a jeśli liczba ta jest wystarczająco wysoka, oblicz dokładną liczbę czynników.

Poniższy kod nie potrzebuje tego założenia do poprawności, ale musi być szybki. Wydaje się, że działa; tylko około jedna na 100 000 liczb daje oszacowanie 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;
            }
        }
    }
}

Znajduje to 14 753 024 trójkąt z 13824 czynnikami w około 0,7 sekundy, 879 207 615 trójkątną liczbę z 41 440 czynnikami w 34 sekund, 12 524 448 975 75 trójkątną liczbę z 132 840 czynnikami w 10 minut 5 sekund, oraz 26 467 776 064 trójkątną z 172 032 czynników w 21 minut i 25 sekund (Core2 Duo 2,4 GHz), więc ten kod zajmuje średnio tylko 116 cykli procesora na liczbę. Ostatni sam trójkątny numer jest większy niż 2 ^ 68, więc

Zmodyfikowałem wersję „Jannich Brendle” na 1000 zamiast 500. I wypisz wynik euler12.bin, euler12.erl, p12dist.erl. Oba kody erl do kompilacji używają „+ 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

czas ./a.out

2,79s użytkownik 0,00s system 99% procesor 2,794 ogółem