Geschwindigkeitsvergleich mit Projekt Euler: C vs. Python vs. Erlang vs. Haskell

Question

Ich habe die Problem Nr. 12 de Projekt Euler als Programmierübung und zum Vergleich meiner (sicherlich nicht optimalen) Implementierungen in C, Python, Erlang und Haskell. Um eine höhere Ausführungszeit zu erreichen, suche ich nach der ersten Dreieckszahl mit mehr als 1000 Teilern statt 500, wie im ursprünglichen Problem angegeben.

Das Ergebnis ist das folgende:

C:

lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c
lorenzo@enzo:~/erlang$ time ./euler12.bin
842161320

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

Python:

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

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

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

Zusammenfassung:

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

Ich nehme an, dass C einen großen Vorteil hat, da es für die Berechnungen lange und nicht beliebig lange ganze Zahlen verwendet, wie die anderen drei. Außerdem muss es nicht erst eine Laufzeitumgebung laden (wie die anderen?).

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

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

Frage 3: Können Sie mir Tipps geben, wie ich diese Implementierungen optimieren kann, ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in jeder Hinsicht: schöner, schneller, "nativer" in der Sprache.

EDITAR:

Frage 4: Erlauben meine funktionalen Implementierungen LCO (Last Call Optimization, auch bekannt als Tail Recursion Elimination) und vermeiden damit das Hinzufügen unnötiger Frames auf dem Call Stack?

Ich habe wirklich versucht, denselben Algorithmus so ähnlich wie möglich in den vier Sprachen zu implementieren, obwohl ich zugeben muss, dass meine Kenntnisse in Haskell und Erlang 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

Answer 1

Nur zum Spaß. Das Folgende ist eine eher "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 (\ls@((val,freq):xs) y -> if val == y then (val,freq+1):xs else (y,1):ls) [(0,0)] . factorize

numDivisors :: Int -> Int
numDivisors = foldl (\acc (_,y) -> acc * (y+1)) 1 <$> factorize2

nextTriangleNumber :: (Int,Int) -> (Int,Int)
nextTriangleNumber (n,acc) = (n+1,acc+n+1)

forward :: Int -> (Int, Int) -> Either (Int, Int) (Int, Int)
forward k val@(n,acc) = if numDivisors acc > k then Left val else Right (nextTriangleNumber val)

problem12 :: Int -> (Int, Int)
problem12 n = (!!0) . lefts . scanl (>>=) (forward n (1,1)) . repeat . forward $ n

main = do
  let (n,val) = problem12 1000
  print val

使用方法 ghc -O3 Auf meinem Rechner (1,73 GHz Core i7) läuft dies durchweg in 0,55-0,58 Sekunden.

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

Ändern von longs zu ints in main, mit gcc -O3 -lm Dies geschieht durchweg in 0,31-0,35 Sekunden.

Beide können noch schneller laufen, wenn man sich die Tatsache zunutze macht, dass die n-te Dreieckszahl = n*(n+1)/2 ist und n und (n+1) völlig unterschiedliche Primfaktorzerlegungen haben, so dass die Anzahl der Faktoren jeder Hälfte multipliziert werden kann, um die Anzahl der Faktoren des Ganzen zu ermitteln. Das 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 es kann mit viel größeren Suchvorgängen umgehen - mehr als 10000 Faktoren benötigen auf meinem Rechner etwa 43 Sekunden. Ich überlasse es dem interessierten Leser, eine ähnliche Beschleunigung von Haskell zu ermitteln.

Answer 2

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

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)

Zeitplan:

Ihr Originalprogramm:

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

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Verbesserte Umsetzung

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 Rechner, auf dem Ihrer in 16 Sekunden lief :)

Kompilierungsbefehle:

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

Answer 3

Frage 1: Verlieren Erlang, Python und Haskell an Geschwindigkeit durch die 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 eine Menge anderer Engpässe in Python aufzeigen. Jedes Mal, wenn das Programm versucht, eine Operation mit einigen Werten in Python auszuführen, muss es überprüfen, ob die Werte vom richtigen Typ sind, und das kostet ein bisschen Zeit. Ihr factorCount Funktion ordnet einfach eine Liste mit range (1, isquare + 1) verschiedene Zeiten und Laufzeiten, malloc -gestützte Speicherzuweisung ist wesentlich langsamer als die Iteration über einen Bereich mit einem Zähler wie in C. Vor allem die factorCount() wird mehrfach aufgerufen und belegt daher eine Vielzahl von Listen. Außerdem sollten wir nicht vergessen, dass Python interpretiert wird und der CPython-Interpreter keinen großen Wert auf eine Optimierung legt.

EDIT Oh, nun, ich stelle fest, dass Sie Python 3 verwenden, also range() gibt keine Liste zurück, sondern einen Generator. In diesem Fall ist meine Aussage über die Zuweisung von Listen halb falsch: Die Funktion weist einfach range Objekte, die zwar ineffizient sind, aber nicht so ineffizient wie die Zuweisung einer Liste mit vielen Elementen.

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

Verwenden Sie Umarmungen ? Hugs ist ein sehr langsamer Interpreter. Wenn Sie ihn benutzen, können Sie vielleicht eine bessere Zeit mit GHC - aber ich denke nur über Hypotesis nach, die Dinge, die ein guter Haskell-Compiler unter der Haube macht, sind ziemlich faszinierend und gehen weit über mein Verständnis hinaus :)

Frage 3: Können Sie mir Tipps geben, wie ich diese Implementierungen optimieren kann, ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in jeder Hinsicht: schöner, schneller, "nativer" in der Sprache.

Ich würde sagen, Sie spielen ein unlustiges 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. Tut mir leid, ich hoffe, jemand kann dir in diesem Fall helfen :)

Frage 4: Erlauben meine funktionalen Implementierungen LCO und vermeiden damit das Hinzufügen unnötiger Frames auf dem 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 nutzen:

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

Eine solche Optimierung wäre jedoch nicht möglich, wenn Ihre Funktion wie die folgende wäre, da nach dem rekursiven Aufruf eine Operation (Multiplikation) folgt:

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, damit klar ist, welche Operationen ausgeführt werden. Üblicherweise werden diese Funktionen jedoch wie unten dargestellt, aber sie sind für den Punkt, den ich anspreche, gleichwertig:

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

Es ist zu beachten, dass es dem Compiler/Interpreter überlassen bleibt, ob er eine Schwanzrekursion durchführt. Der Python-Interpreter zum Beispiel macht das nicht, wenn ich mich recht erinnere (ich habe Python in meinem Beispiel nur wegen seiner flüssigen Syntax verwendet). Wie auch immer, wenn Sie seltsame Dinge finden, wie z. B. faktorielle Funktionen mit zwei Parametern (und einer der Parameter hat Namen wie acc , accumulator usw.) Jetzt wissen Sie, warum die Leute das tun :)

Answer 4

In Haskell braucht man nicht explizit in Rekursionen zu 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 die expliziten Rekursionen in @Thomas' Antwort durch allgemeine Listenoperationen ersetzt. Der Code tut immer noch genau das Gleiche, ohne dass wir uns über Schwanzrekursionen Gedanken machen müssen. Er führt (~ 7.49s ) über 6% langsamer als die Version in @Thomas' Antwort (~ 7.04s ) auf meinem Rechner mit GHC 7.6.2, während die C-Version von @Raedwulf ~ 3.15s . Es scheint, dass sich GHC im Laufe des Jahres verbessert hat.

PS. Ich weiß, es ist eine alte Frage, und ich stolpere über sie von Google-Suchen (ich habe vergessen, was ich suchte, jetzt...). Ich wollte nur die Frage über LCO kommentieren und meine Gefühle über Haskell im Allgemeinen ausdrücken. Ich wollte die oberste Antwort kommentieren, aber Kommentare lassen keine Codeblöcke zu.

Answer 5

Ich sehe mir Ihre Erlang-Implementierung an. Der Zeitplan umfasst das Starten der gesamten virtuellen Maschine, die Ausführung Ihres Programms und das Anhalten der virtuellen Maschine. Ich bin mir ziemlich sicher, dass das Einrichten und Anhalten der Erlang-VM einige Zeit in Anspruch nimmt.

Wenn die Zeitmessung innerhalb der virtuellen Erlang-Maschine selbst durchgeführt würde, wären die Ergebnisse anders, da wir in diesem Fall nur die tatsächliche Zeit für das betreffende Programm hätten. Andernfalls glaube ich, dass die Gesamtzeit, die für das Starten und Laden der Erlang-VM benötigt wird, sowie die Zeit für das Anhalten der Maschine (wie Sie es in Ihrem Programm formulieren) in der Gesamtzeit enthalten sind, die die von Ihnen verwendete Methode zur Zeitmessung des Programms ausgibt. Betrachten Sie die Erlang-Zeitmessung selbst, die wir verwenden, wenn wir unsere Programme innerhalb der virtuellen Maschine selbst zeitlich steuern wollen timer:tc/1 or timer:tc/2 or timer:tc/3 . Auf diese Weise wird in den Ergebnissen von erlang die Zeit, die zum Starten und Stoppen/Abschalten/Halten der virtuellen Maschine benötigt wird, nicht berücksichtigt. Das ist meine Argumentation, denken Sie darüber nach und versuchen Sie es dann noch einmal mit Ihrem Benchmark.

Ich schlage 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 durch das Starten und Beenden eines Laufzeitsystems, ebenso wie Erlang, Python und Haskell (ich bin mir da zu 98% sicher - ich korrigiere mich). Daraus schließe ich, dass dieser Benchmark für Sprachen, die auf einem Laufzeitsystem laufen, nicht genau/gerecht genug war. Lassen Sie es uns mit diesen Änderungen noch einmal machen.

EDIT: Außerdem, selbst wenn alle Sprachen Laufzeitsysteme hätten, wäre der Overhead beim Starten und Anhalten unterschiedlich. Daher schlage ich vor, die Zeit innerhalb der Laufzeitsysteme zu messen (für die Sprachen, für die dies gilt). Es ist bekannt, dass die Erlang-VM beim Starten einen erheblichen Overhead hat!