wake-up-neo.com

Geschwindigkeitsvergleich mit Project Euler: C vs Python vs Erlang vs Haskell

Ich habe Problem # 12 aus Project Euler als Programmierübung genommen und meine (sicherlich nicht optimalen) Implementierungen in C, Python, Erlang und Haskell verglichen. Um einige höhere Ausführungszeiten zu erhalten, suche ich nach der ersten Dreieckszahl mit mehr als 1000 Teilern anstelle von 500, wie im ursprünglichen Problem angegeben.

Das Ergebnis ist das Folgende:

C:

[email protected]:~/erlang$ gcc -lm -o euler12.bin euler12.c
[email protected]:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

Python:

[email protected]:~/erlang$ time ./euler12.py 
842161320

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

Python mit PyPy:

[email protected]:~/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:

[email protected]:~/erlang$ erlc euler12.erl 
[email protected]:~/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:

[email protected]:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
[email protected]:~/erlang$ time ./euler12.hsx 
842161320

real    2m37.326s
user    2m37.240s
sys 0m0.080s

Zusammenfassung:

  • C: 100%
  • Python: 692% (118% mit PyPy)
  • Erlang: 436% (135% dank RichardC)
  • Haskell: 1421%

Ich nehme an, dass C einen großen Vorteil hat, da es long für die Berechnungen verwendet und keine Ganzzahlen beliebiger Länge wie die anderen drei. Außerdem muss nicht erst eine Laufzeit geladen werden (die anderen erledigen?).

Frage 1: Verlieren Erlang, Python und Haskell aufgrund der Verwendung von Ganzzahlen beliebiger Länge an Geschwindigkeit oder sind sie nicht so lang wie die Werte sind kleiner als MAXINT?

Frage 2: Warum ist Haskell so langsam? Gibt es ein Compiler-Flag, das die Bremsen ausschaltet, oder ist es meine Implementierung? (Letzteres ist sehr wahrscheinlich, da Haskell für mich ein Buch mit sieben Siegeln ist.)

Frage 3: Können Sie mir einige Hinweise zur Optimierung dieser Implementierungen geben, ohne die Art und Weise zu ändern, in der ich die Faktoren bestimme? Optimierung in irgendeiner Weise: schöner, schneller, "ursprünglicher" in der Sprache.

EDIT:

Frage 4: Ermöglichen meine funktionalen Implementierungen eine LCO (Last Call Optimization, a.k. eine Tail Recursion Elimination) und vermeiden Sie daher das Hinzufügen unnötiger Frames zum Call Stack?

Ich habe wirklich versucht, den gleichen Algorithmus in den vier Sprachen so ähnlich wie möglich zu implementieren, obwohl ich zugeben muss, dass meine Haskell- und Erlang-Kenntnisse sehr begrenzt sind.


Verwendete Quellcodes:

#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
637
Hyperboreus

Verwenden von GHC 7.0.3, gcc 4.4.6, Linux 2.6.29 auf einem x86_64 Core2 Duo-Computer (2,5 GHz), Kompilieren mit ghc -O2 -fllvm -fforce-recomp für Haskell und gcc -O3 -lm für C.

  • Ihre C-Routine läuft in 8,4 Sekunden (schneller als Ihr Lauf wahrscheinlich wegen -O3)
  • Die Haskell-Lösung wird in 36 Sekunden ausgeführt (aufgrund der Markierung -O2)
  • Ihr factorCount' Code ist nicht explizit eingegeben und standardmäßig Integer (Danke an Daniel für die Korrektur meiner Fehldiagnose!). Geben einer expliziten Typensignatur (was ohnehin Standard ist) mit Int und die Zeit ändert sich in 11,1 Sekunden
  • in factorCount' haben Sie fromIntegral unnötigerweise angerufen. Ein Fix führt jedoch zu keiner Änderung (der Compiler ist schlau und hat Glück für Sie).
  • Sie haben mod verwendet, wobei rem schneller und ausreichend ist. Dies ändert die Zeit auf 8,5 Sekunden.
  • factorCount' wendet ständig zwei zusätzliche Argumente an, die sich nie ändern (number, sqrt). Eine Worker/Wrapper-Transformation gibt uns:
 $ time ./so
 842161320  

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

Das stimmt, 7,95 Sekunden. Konsequent eine halbe Sekunde schneller als die C-Lösung. Ohne das -fllvm -Flag erhalte ich immer noch 8.182 seconds, daher läuft das NCG-Backend auch in diesem Fall gut.

Fazit: Haskell ist der Hammer.

Resultierender Code

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

EDIT: Nun, da wir das untersucht haben, wollen wir die Fragen ansprechen

Frage 1: Verlieren erlang, python und haskell an Geschwindigkeit, weil Ganzzahlen beliebiger Länge verwendet werden, oder nicht, solange die Werte kleiner als MAXINT sind?

In Haskell ist die Verwendung von Integer langsamer als Int, aber wie viel langsamer ist, hängt von den durchgeführten Berechnungen ab. Zum Glück (für 64-Bit-Maschinen) ist Int ausreichend. Aus Gründen der Portabilität sollten Sie wahrscheinlich meinen Code umschreiben, um Int64 oder Word64 zu verwenden (C ist nicht die einzige Sprache mit einem long).

Frage 2: Warum ist haskell so langsam? Gibt es ein Compiler-Flag, das die Bremsen ausschaltet, oder ist es meine Implementierung? (Letzteres ist sehr wahrscheinlich, da haskell für mich ein Buch mit sieben Siegeln ist.)

Frage 3: Können Sie mir einige Hinweise zur Optimierung dieser Implementierungen geben, ohne die Art und Weise zu ändern, in der ich die Faktoren bestimme? Optimierung in irgendeiner Weise: schöner, schneller, "ursprünglicher" in der Sprache.

Das habe ich oben beantwortet. Die Antwort war

  • 0) Optimierung über -O2 verwenden
  • 1) Verwenden Sie, wenn möglich, schnelle (insbesondere nicht boxfähige) Typen
  • 2) rem nicht mod (eine häufig vergessene Optimierung) und
  • 3) Worker/Wrapper-Transformation (möglicherweise die häufigste Optimierung).

Frage 4: Ermöglichen meine funktionalen Implementierungen LCO und vermeiden Sie daher das Hinzufügen unnötiger Frames zum Aufrufstapel?

Ja, das war nicht das Problem. Gute Arbeit und ich bin froh, dass du darüber nachgedacht hast.

771

Es gibt einige Probleme mit der Erlang-Implementierung. Als Basis für das Folgende betrug meine gemessene Ausführungszeit für Ihr nicht modifiziertes Erlang-Programm 47,6 Sekunden, verglichen mit 12,7 Sekunden für den C-Code.

Wenn Sie rechenintensiven Erlang-Code ausführen möchten, sollten Sie zunächst systemeigenen Code verwenden. Beim Kompilieren mit erlc +native euler12 wurde die Zeit auf 41,3 Sekunden gesenkt. Dies ist jedoch eine viel geringere Geschwindigkeit (nur 15%) als von der nativen Kompilierung dieser Art von Code erwartet, und das Problem ist Ihre Verwendung von -compile(export_all). Dies ist nützlich für Experimente, aber die Tatsache, dass alle Funktionen möglicherweise von außen erreichbar sind, führt dazu, dass der native Compiler sehr konservativ ist. (Der normale BEAM-Emulator ist nicht so stark betroffen.) Das Ersetzen dieser Deklaration durch -export([solve/0]). führt zu einer deutlich besseren Beschleunigung: 31,5 Sekunden (fast 35% vom Ausgangswert).

Der Code selbst hat jedoch ein Problem: Für jede Iteration in der factorCount-Schleife führen Sie den folgenden Test durch:

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

Der C-Code macht das nicht. Im Allgemeinen kann es schwierig sein, einen fairen Vergleich zwischen verschiedenen Implementierungen desselben Codes vorzunehmen, insbesondere wenn der Algorithmus numerisch ist, da Sie sicherstellen müssen, dass sie tatsächlich dasselbe tun. Ein geringfügiger Rundungsfehler in einer Implementierung aufgrund von Typumwandlungen kann dazu führen, dass viel mehr Iterationen ausgeführt werden als in der anderen, obwohl beide letztendlich das gleiche Ergebnis erzielen.

Um diese mögliche Fehlerquelle zu eliminieren (und den zusätzlichen Test in jeder Iteration loszuwerden), habe ich die factorCount-Funktion wie folgt umgeschrieben, wobei ich eng an den C-Code angelehnt war:

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.

Dieses Umschreiben, kein export_all und die native Kompilierung gaben mir die folgende Laufzeit:

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

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

das ist nicht schlecht im Vergleich zum C-Code:

$ time ./a.out 
842161320

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

wenn man bedenkt, dass Erlang überhaupt nicht darauf ausgerichtet ist, numerischen Code zu schreiben, ist es ziemlich gut, in einem Programm wie diesem nur 50% langsamer als C zu sein.

Abschließend zu Ihren Fragen:

Frage 1: Verlieren erlang, python und haskell Geschwindigkeit aufgrund der Verwendung von Ganzzahlen beliebiger Länge oder nicht, solange die Werte kleiner als MAXINT sind?

Ja, etwas. In Erlang gibt es keine Möglichkeit, "32/64-Bit-Arithmetik mit Umbruch verwenden" zu sagen. Wenn der Compiler also keine Grenzen für Ihre Ganzzahlen nachweisen kann (und dies normalerweise nicht kann), muss er alle Berechnungen überprüfen, um sie anzuzeigen ob sie in ein einzelnes mit Tags versehenes Wort passen oder ob sie in Heap-zugewiesene Bignums umgewandelt werden müssen. Auch wenn zur Laufzeit in der Praxis keine Bignums verwendet werden, müssen diese Überprüfungen durchgeführt werden. Andererseits bedeutet dies, dass Sie wissen , dass der Algorithmus niemals aufgrund eines unerwarteten ganzzahligen Umlaufs fehlschlägt, wenn Sie ihm plötzlich größere Eingaben als zuvor geben.

Frage 4: Ermöglichen meine funktionalen Implementierungen LCO und vermeiden Sie daher das Hinzufügen unnötiger Frames zum Aufrufstapel?

Ja, Ihr Erlang-Code ist in Bezug auf die Optimierung des letzten Anrufs korrekt.

217
RichardC

In Bezug auf die Python -Optimierung können Sie neben PyPy (für beeindruckende Beschleunigungen ohne Änderung des Codes) auch PyPy's Übersetzungs-Toolchain zum Kompilieren eines RPython- kompatible Version oder Cython zum Erstellen eines Erweiterungsmoduls, das in meinen Tests schneller als die C-Version ist, mit dem Cython-Modul fast doppelt so schnell. Als Referenz füge ich auch C- und PyPy-Benchmark-Ergebnisse hinzu:

C (kompiliert mit 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 (unter Verwendung der neuesten PyPy-Version, 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

Die RPython-Version enthält einige wichtige Änderungen. Um in ein eigenständiges Programm zu übersetzen, müssen Sie target definieren, in diesem Fall die Funktion main. Es wird erwartet, dass es sys.argv als einziges Argument akzeptiert und ein int zurückgibt. Sie können es übersetzen, indem Sie translate.py, % translate.py euler12-rpython.py verwenden, das in C übersetzt und es für Sie kompiliert.

# 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 __== '__main__':
    main(sys.argv)

def target(*args):
    return main, None

Die Cython-Version wurde als Erweiterungsmodul _euler12.pyx umgeschrieben, das ich aus einer normalen python -Datei importiere und aufrufe. Der _euler12.pyx ist im Wesentlichen derselbe wie Ihre Version, mit einigen zusätzlichen statischen Typdeklarationen. Die setup.py hat das normale Boilerplate, um die Erweiterung mit python setup.py build_ext --inplace zu erstellen.

# _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
)

Ich habe ehrlich gesagt nur sehr wenig Erfahrung mit RPython oder Cython und war angenehm überrascht von den Ergebnissen. Wenn Sie CPython verwenden, scheint das Schreiben Ihrer CPU-intensiven Code-Teile in einem Cython-Erweiterungsmodul eine einfache Möglichkeit zu sein, Ihr Programm zu optimieren.

155
zeekay

Frage 3: Können Sie mir einige Hinweise geben, wie Sie diese Implementierungen optimieren können, ohne die Art und Weise zu ändern, in der ich die Faktoren bestimme? Optimierung in irgendeiner Weise: schöner, schneller, "ursprünglicher" in der Sprache.

Die C-Implementierung ist suboptimal (wie von Thomas M. DuBuisson angedeutet), die Version verwendet 64-Bit-Ganzzahlen (d. H. lang Datentyp). Ich werde die Assembly-Auflistung später untersuchen, aber mit einer begründeten Vermutung gibt es einige Speicherzugriffe im kompilierten Code, die die Verwendung von 64-Bit-Ganzzahlen erheblich verlangsamen. Das ist der oder der generierte Code (sei es, dass Sie weniger 64-Bit-Ints in ein SSE -Register einpassen können oder das Runden eines Double auf eine 64-Bit-Ganzzahl langsamer ist).

Hier ist der geänderte Code (ersetzen Sie einfach long mit int und ich explizit inlined factorCount, obwohl ich nicht denke, dass dies mit gcc -O3) notwendig ist:

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

Laufen + Timing gibt es:

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

Als Referenz liefert die Hashell-Implementierung von Thomas in der vorherigen Antwort:

$ 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

Fazit: ghc nimmt nichts weg, es ist ein großartiger Compiler, aber gcc generiert normalerweise schnelleren Code.

70
Raedwulf

Schauen Sie sich dieses Blog an. Im letzten Jahr hat er einige der Probleme mit Project Euler in Haskell und Python gelöst, und er hat festgestellt, dass Haskell viel schneller ist. Ich denke, dass es zwischen diesen Sprachen mehr mit Ihrer Geläufigkeit und Ihrem Codierungsstil zu tun hat.

Wenn es um Python Geschwindigkeit geht, verwenden Sie die falsche Implementierung! Versuchen Sie PyPy , und für solche Dinge werden Sie feststellen, dass es viel, viel schneller ist.

56
agf

Ihre Haskell-Implementierung könnte durch die Verwendung einiger Funktionen aus Haskell-Paketen erheblich beschleunigt werden. In diesem Fall habe ich Primzahlen verwendet, die nur mit 'cabal install primes' installiert werden;)

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)

Timings:

Ihr ursprüngliches Programm:

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

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Verbesserte Implementierung

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

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Wie Sie sehen können, läuft dieser in 38 Millisekunden auf demselben Computer, auf dem Ihr Computer in 16 Sekunden lief :)

Kompilierungsbefehle:

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

Nur zum Spaß. Das Folgende ist eine "native" Haskell-Implementierung:

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 (\[email protected]((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 [email protected](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

Unter Verwendung von ghc -O3 wird dies auf meinem Computer (1,73 GHz Core i7) durchgehend in 0,55 bis 0,58 Sekunden ausgeführt.

Eine effizientere factorCount-Funktion für die C-Version:

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

Wenn Sie Longs mit gcc -O3 -lm in Ints in main ändern, wird dies durchgehend in 0,31 bis 0,35 Sekunden ausgeführt.

Beide können noch schneller ausgeführt werden, wenn Sie die Tatsache ausnutzen, dass die n-te Dreieckszahl = n * (n + 1)/2 und n und (n + 1) völlig unterschiedliche Primfaktoren aufweisen, also die Anzahl der Faktoren jeder Hälfte kann multipliziert werden, um die Anzahl der Faktoren des Ganzen zu ermitteln. Folgende:

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

reduziert die Laufzeit des C-Codes auf 0,17-0,19 Sekunden und kann viel größere Suchvorgänge ausführen - mehr als 10000 Faktoren benötigen auf meinem Computer ungefähr 43 Sekunden. Ich überlasse dem interessierten Leser ein ähnliches Haskell-Speedup.

28
thaumkid
Frage 1: Verlieren erlang, python und haskell Geschwindigkeit aufgrund der Verwendung von Ganzzahlen beliebiger Länge oder nicht, solange die Werte kleiner als MAXINT sind?

Das ist unwahrscheinlich. Ich kann nicht viel über Erlang und Haskell sagen (naja, vielleicht ein bisschen über Haskell weiter unten), aber ich kann viele andere Engpässe in Python aufzeigen. Jedes Mal, wenn das Programm versucht, eine Operation mit bestimmten Werten in Python auszuführen, sollte überprüft werden, ob die Werte vom richtigen Typ sind. Dies kostet etwas Zeit. Ihre factorCount -Funktion weist nur eine Liste mit range (1, isquare + 1) zu verschiedenen Zeitpunkten zu, und die Speicherzuweisung im Stil von Runtime, malloc ist viel langsamer als das Iterieren in einem Bereich mit einem Zähler wie in C. Insbesondere wird die factorCount() mehrfach aufgerufen und weist so viele Listen zu. Vergessen wir auch nicht, dass Python interpretiert wird und der CPython-Interpreter sich nicht besonders darauf konzentriert, optimiert zu werden.

EDIT: oh, nun, ich stelle fest, dass Sie Python 3 verwenden, so dass range() kein zurückgibt Liste, aber ein Generator. In diesem Fall ist meine Überlegung, Listen zuzuweisen, zur Hälfte falsch: Die Funktion weist nur range Objekte zu, die zwar ineffizient sind, aber nicht so ineffizient wie das Zuweisen einer Liste mit vielen Elementen.

Frage 2: Warum ist haskell so langsam? Gibt es ein Compiler-Flag, das die Bremsen ausschaltet, oder ist es meine Implementierung? (Letzteres ist sehr wahrscheinlich, da haskell für mich ein Buch mit sieben Siegeln ist.)

Benutzt du marmungen ? Hugs ist ein sehr langsamer Dolmetscher. Wenn Sie es benutzen, können Sie vielleicht eine bessere Zeit mit GHC - bekommen, aber ich denke nur über Hypotesis nach, die Art von Sachen, die ein guter Haskell-Compiler unter der Haube macht, ist ziemlich faszinierend und weit darüber hinaus mein verständnis :)

Frage 3: Können Sie mir einige Hinweise zur Optimierung dieser Implementierungen geben, ohne die Art und Weise zu ändern, in der ich die Faktoren bestimme? Optimierung in irgendeiner Weise: schöner, schneller, "ursprünglicher" in der Sprache.

Ich würde sagen, Sie spielen ein lustiges Spiel. Das Beste daran, verschiedene Sprachen zu kennen, ist, sie auf möglichst unterschiedliche Weise zu verwenden :) Aber ich schweife ab, ich habe einfach keine Empfehlung für diesen Punkt. Sorry, ich hoffe jemand kann dir in diesem Fall helfen :)

Frage 4: Ermöglichen meine funktionalen Implementierungen LCO und vermeiden Sie daher das Hinzufügen unnötiger Frames zum Aufrufstapel?

Soweit ich mich erinnere, müssen Sie nur sicherstellen, dass Ihr rekursiver Aufruf der letzte Befehl ist, bevor Sie einen Wert zurückgeben. Mit anderen Worten, eine Funktion wie die folgende könnte eine solche Optimierung verwenden:

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

Eine solche Optimierung hätten Sie jedoch nicht, wenn Ihre Funktion die folgende wäre, da nach dem rekursiven Aufruf eine Operation (Multiplikation) erfolgt:

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

Ich habe die Operationen in einige lokale Variablen aufgeteilt, um zu verdeutlichen, welche Operationen ausgeführt werden. Am gebräuchlichsten ist es jedoch, diese Funktionen wie folgt zu betrachten, sie entsprechen jedoch dem Punkt, den ich anspreche:

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

Beachten Sie, dass es Sache des Compilers/Interpreters ist, zu entscheiden, ob eine Endrekursion durchgeführt wird. Zum Beispiel macht der Interpreter Python es nicht, wenn ich mich gut erinnere (ich habe Python in meinem Beispiel nur wegen seiner fließenden Syntax verwendet). Wie auch immer, wenn Sie seltsame Dinge finden, wie z. B. Fakultätsfunktionen mit zwei Parametern (und einer der Parameter hat Namen wie acc, accumulator usw.), wissen Sie jetzt, warum die Leute das tun :)

13
brandizzi

Mit Haskell müssen Sie nicht explizit an Rekursionen denken.

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

Im obigen Code habe ich explizite Rekursionen in @Thomas 'Antwort durch allgemeine Listenoperationen ersetzt. Der Code macht immer noch genau das Gleiche, ohne dass wir uns Gedanken über die Schwanzrekursion machen müssen. Es läuft (~ 7.49s) ungefähr 6% langsamer als die Version in @Thomas 'Antwort (~ 7.04s) auf meinem Computer mit GHC 7.6.2, während die C-Version von @Raedwulf ~ .15s ausführt. Es scheint, dass sich GHC im Laufe des Jahres verbessert hat.

PS. Ich weiß, dass es eine alte Frage ist, und ich stolpere über Google Search (ich habe vergessen, wonach ich gesucht habe ...). Ich wollte nur die Frage zu LCO kommentieren und meine Gefühle zu Haskell im Allgemeinen ausdrücken. Ich wollte die oberste Antwort kommentieren, aber Kommentare erlauben keine Codeblöcke.

12
jxy

Noch ein paar Zahlen und Erläuterungen zur C-Version. Anscheinend hat es in all den Jahren niemand getan. Denken Sie daran, diese Antwort zu verbessern, damit jeder sie sehen und lernen kann.

Erster Schritt: Benchmark der Programme des Autors

Laptop-Spezifikationen:

  • CPU i3 M380 (931 MHz - maximaler Batteriesparmodus)
  • 4 GB Speicher
  • Win7 64 Bit
  • Microsoft Visual Studio 2012 Ultimate
  • Cygwin mit gcc 4.9.3
  • Python 2.7.10

Befehle:

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

Dateinamen sind: _integertype_architecture_compiler.exe_

  • integertype ist vorerst das gleiche wie das Originalprogramm (dazu später mehr)
  • Architektur ist x86 oder x64, abhängig von den Compilereinstellungen
  • Compiler ist gcc oder vs2012

Zweiter Schritt: Erneut untersuchen, verbessern und bewerten

VS ist 250% schneller als gcc. Die beiden Compiler sollten eine ähnliche Geschwindigkeit ergeben. Offensichtlich stimmt etwas mit dem Code oder den Compiler-Optionen nicht. Lassen Sie uns untersuchen!

Der erste interessierende Punkt sind die ganzzahligen Typen. Konvertierungen können teuer sein und Konsistenz ist wichtig für eine bessere Codegenerierung und -optimierung. Alle Ganzzahlen sollten vom selben Typ sein.

Es ist ein gemischtes Durcheinander von int und long. Wir werden das verbessern. Welcher Typ ist zu verwenden? Der schnellste. Muss man sie alle messen!

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

Ganzzahlige Typen sind intlong _int32_tuint32_tint64_t_ und _uint64_t_ von _#include <stdint.h>_

Es gibt VIELE Integer-Typen in C sowie einige mit Vorzeichen versehene/nicht mit Vorzeichen versehene zum Spielen und die Möglichkeit, sie als x86 oder x64 zu kompilieren (nicht zu verwechseln mit der tatsächlichen Integer-Größe). Das sind viele Versionen zum kompilieren und ausführen ^^

Schritt drei: Zahlen verstehen

Endgültige Schlussfolgerungen:

  • 32-Bit-Ganzzahlen sind ~ 200% schneller als 64-Bit-Äquivalente
  • 64-Bit-Ganzzahlen ohne Vorzeichen sind 25% schneller als 64-Bit-Ganzzahlen mit Vorzeichen (Leider , Ich habe keine Erklärung dafür)

Trickfrage: "Was sind die Größen von int und long in C?"
Die richtige Antwort lautet: Die Größe von int und long in C ist nicht genau definiert!

Aus der C-Spezifikation:

int ist mindestens 32 Bit
long ist mindestens ein int

Aus der gcc-Manpage (-m32 und -m64 Flags):

Die 32-Bit-Umgebung setzt int, long und pointer auf 32 Bit und generiert Code, der auf jedem i386-System ausgeführt wird.
Die 64-Bit-Umgebung setzt int auf 32 Bit und long und zeigt auf 64 Bit und generiert Code für die x86-64-Architektur von AMD.

Aus der MSDN-Dokumentation (Datentypbereiche) https://msdn.Microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx =:

int, 4 bytes, weiss auch wie signiert
long, 4 Bytes, kennt auch long int und signed long int

Um dies abzuschließen: Lessons Learned

  • 32-Bit-Ganzzahlen sind schneller als 64-Bit-Ganzzahlen.

  • Standard-Ganzzahlentypen sind in C oder C++ nicht genau definiert. Sie variieren je nach Compiler und Architektur. Wenn Sie Konsistenz und Vorhersagbarkeit benötigen, verwenden Sie die Ganzzahlfamilie _uint32_t_ aus _#include <stdint.h>_.

  • Geschwindigkeitsprobleme behoben. Alle anderen Sprachen sind hundertprozentig zurück, C & C++ gewinnt wieder! Sie tun es immer. Die nächste Verbesserung wird Multithreading mit OpenMP: D sein

10
user5994461

Betrachten Sie Ihre Erlang-Implementierung. Das Timing umfasste den Start der gesamten virtuellen Maschine, das Ausführen Ihres Programms und das Anhalten der virtuellen Maschine. Bin mir ziemlich sicher, dass das Einrichten und Stoppen des erlang vm einige Zeit in Anspruch nimmt.

Wenn das Timing innerhalb der virtuellen Maschine selbst durchgeführt würde, wären die Ergebnisse anders, da in diesem Fall die tatsächliche Zeit nur für das betreffende Programm verfügbar wäre. Ansonsten glaube ich, dass die Gesamtzeit für das Starten und Laden des Erlang Vm plus das Anhalten (wie Sie es in Ihr Programm einfügen) in der Gesamtzeit enthalten ist, die die Methode verwendet, um die Zeit zu bestimmen Programm wird ausgegeben. Erwägen Sie, das Erlang-Timing selbst zu verwenden, wenn Sie unsere Programme innerhalb der virtuellen Maschine selbst zeitlich festlegen möchten timer:tc/1 or timer:tc/2 or timer:tc/3 . Auf diese Weise schließen die Ergebnisse von erlang die Zeit aus, die zum Starten und Stoppen/Beenden/Anhalten der virtuellen Maschine benötigt wird. Das ist meine Überlegung, überlege es dir und versuche es dann noch einmal.

Ich schlage tatsächlich vor, dass wir versuchen, das Programm (für Sprachen, die eine Laufzeit haben) innerhalb der Laufzeit dieser Sprachen zu timen, um einen genauen Wert zu erhalten. C zum Beispiel hat keinen Overhead beim Starten und Herunterfahren eines Laufzeitsystems wie Erlang, Python und Haskell (98% sicher - ich stehe zur Korrektur). Aus diesem Grund möchte ich abschließend sagen, dass dieser Benchmark für Sprachen, die auf einem Laufzeitsystem ausgeführt werden, nicht präzise/fair genug war. Machen wir es mit diesen Änderungen noch einmal.

BEARBEITEN: Abgesehen davon, dass alle Sprachen über Laufzeitsysteme verfügten, wäre der Aufwand für das Starten und Stoppen der einzelnen Sprachen unterschiedlich. Daher schlage ich vor, dass wir die Zeit innerhalb der Laufzeitsysteme einstellen (für die Sprachen, für die dies gilt). Es ist bekannt, dass der Erlang VM beim Start einen erheblichen Overhead verursacht!

8
Muzaaya Joshua

Frage 1: Verlieren Erlang, Python und Haskell durch die Verwendung von Ganzzahlen beliebiger Länge an Geschwindigkeit oder nicht, solange die Werte kleiner als MAXINT sind?

Die erste Frage kann für Erlang verneint werden. Die letzte Frage wird mit Erlang beantwortet, wie in:

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

Da es schneller ist als Ihr erstes C-Beispiel, gibt es vermutlich zahlreiche Probleme, die bereits von anderen ausführlich behandelt wurden.

Dieses Erlang-Modul wird auf einem billigen Netbook in etwa 5 Sekunden ausgeführt. Es verwendet das Netzwerkthreadmodell in Erlang und demonstriert als solches, wie man das Ereignismodell ausnutzt. Es könnte über viele Knoten verteilt sein. Und es geht schnell. Nicht mein Code.

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

Der folgende Test fand auf einer Intel (R) Atom (TM) -CPU N270 bei 1,60 GHz statt

~$ 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
7
Mark Washeim

C++ 11, <20ms für mich - hier ausführen

Ich verstehe, dass Sie Tipps wünschen, um Ihre sprachspezifischen Kenntnisse zu verbessern, aber da dies hier ausführlich behandelt wurde, dachte ich, ich würde einen Kontext für Leute hinzufügen, die sich den mathematica-Kommentar zu Ihrer Frage usw. angesehen haben, und fragte mich, warum dies so ist Code war so viel langsamer.

Diese Antwort dient hauptsächlich dazu, einen Kontext bereitzustellen, der den Menschen hoffentlich dabei hilft, den Code in Ihrer Frage oder in anderen Antworten leichter zu bewerten.

In diesem Code werden nur einige (hässliche) Optimierungen verwendet, die nicht mit der verwendeten Sprache zusammenhängen. Sie basieren auf:

  1. jede Traingle-Zahl hat die Form n (n + 1)/2
  2. n und n + 1 sind Koprime
  3. die Anzahl der Teiler ist eine multiplikative Funktion
#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;
}

Das dauert durchschnittlich 19 ms für meinen Desktop und 80 ms für meinen Laptop, weit entfernt von den meisten anderen Codes, die ich hier gesehen habe. Und es gibt zweifellos noch viele Optimierungen.

5
user3125280

GO versuchen:

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

Ich bekomme:

ursprüngliche c-Version: 9.1690 100%
go: 8,2520 111%

Aber mit:

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
}

Ich bekomme:

ursprüngliche c-Version: 9.1690 100%
Thaumkids c-Version: 0,1060 8650%
first go version: 8.2520 111%
second go version: 0.0230 9865%

Ich habe auch Python3.6 und pypy3.3-5.5-alpha ausprobiert:

ursprüngliche c-Version: 8.629 100%
Thaumkids c-Version: 0,109 7916%
Python3.6: 54.795 16%
pypy3.3-5.5-alpha: 13.291 65%

und dann mit folgendem code habe ich bekommen:

ursprüngliche c-Version: 8.629 100%
Thaumkids c-Version: 0,109 8650%
Python3.6: 1.489 580%
[...] pypy3.3-5.5-alpha: 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)
5
thanos

Ich bin davon ausgegangen, dass die Anzahl der Faktoren nur dann groß ist, wenn es sich um viele kleine Faktoren handelt. Also habe ich den exzellenten Algorithmus von Thaumkid verwendet, aber zuerst eine Annäherung an die Faktorenzahl, die niemals zu klein ist. Ganz einfach: Suchen Sie nach Primfaktoren bis 29, überprüfen Sie dann die verbleibende Zahl und berechnen Sie eine Obergrenze für die Anzahl der Faktoren. Verwenden Sie dies, um eine Obergrenze für die Anzahl der Faktoren zu berechnen. Wenn diese Anzahl hoch genug ist, berechnen Sie die genaue Anzahl der Faktoren.

Der folgende Code benötigt diese Annahme nicht, um korrekt zu sein, sondern um schnell zu sein. Es scheint zu funktionieren; Nur eine von 100.000 Zahlen ergibt eine Schätzung, die hoch genug ist, um eine vollständige Überprüfung zu erfordern.

Hier ist der Code:

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

Dies ergibt das 14.753.024ste Dreieck mit 13824 Faktoren in etwa 0,7 Sekunden, das 879.207.615ste Dreieck mit 61.440 Faktoren in 34 Sekunden, das 12.524.486.975ste Dreieck mit 138.240 Faktoren in 10 Minuten und 5 Sekunden und das 26.467.792.064ste Dreieck mit 172.032 Faktoren in 21 Minuten 25 Sekunden (2,4 GHz Core2 Duo), sodass dieser Code durchschnittlich nur 116 Prozessorzyklen pro Nummer benötigt. Die letzte Dreieckszahl selbst ist also größer als 2 ^ 68

1
gnasher729

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

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

Auf diese Weise erhalten Sie die richtige Antwort für das Erlang-Beispiel mit mehreren Prozessen.

1
user3051214

Ich habe die "Jannich Brendle" -Version auf 1000 anstatt auf 500 geändert. Und das Ergebnis von euler12.bin, euler12.erl, p12dist.erl aufgelistet. Beide Erl-Codes kompilieren mit '+ 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$
0
Witeman
#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

zeit ./a.out

2,79s Benutzer 0,00s System 99% CPU 2,794 insgesamt

0
user3250089