Ich las einen Artikel vonhow langsam Haskell ist es im Spiel mit Collatz Vermutung, das im Grunde genommen besagt, dass wenn Sie drei und plus eins mit einer ungeraden Zahl multiplizieren oder eine gerade mit zwei teilen, Sie letztendlich eine erhalten. Zum Beispiel 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

Das in diesem Artikel angegebene Programm berechnet die längste Collatz-Sequenz in einem bestimmten Bereich. Die C-Version ist:

#include <stdio.h>

int main(int argc, char **argv) {
   int max_a0 = atoi(argv[1]); 
   int longest = 0, max_len = 0;
   int a0, len;
   unsigned long a;

   for (a0 = 1; a0 <= max_a0; a0++) {
      a = a0;
      len = 0;

      while (a != 1) {
         len++;
         a = ((a%2==0)? a : 3*a+1)/2;
      }

      if (len > max_len) {
         max_len = len;
         longest = a0;
      }
   }
   printf("(%d, %d)\n", max_len, longest);
   return 0;
}

Kompilieren mit Clang O2, läuft es 0.2s auf meinem Computer.

Die in diesem Artikel angegebene Haskell-Version generiert die gesamte Sequenz explizit als Liste und berechnet dann die Länge der Zwischenliste. Es ist 10x langsamer als die C-Version. Da der Autor jedoch LLVM als Backend verwendet hat, das ich nicht installiert habe, konnte ich dies nicht reproduzieren. Mit GHC 7.8 und dem Standard-Backend läuft es auf meinem Mac 10s, was 50x langsamer ist als die C-Version.

Dann schreibe ich eine Version mit Schwanzrekursion und ohne eine Zwischenliste zu generieren:

collatzNext :: Int -> Int
collatzNext a
  | even a    = a `div` 2
  | otherwise = (3 * a + 1) `div` 2

collatzLen :: Int -> Int
collatzLen n = collatzIter n 0
  where
    collatzIter 1 len = len
    collatzIter n len = collatzIter (collatzNext n) (len + 1)

main = do
  print $ maximum $ [collatzLen x | x <- [1..1000000]]

Mit GHC 7.8 und O2 kompiliert, läuft es 2s, 10x langsamer als die C-Version.

Interessanterweise, als ich @ änderInt in der Typanmerkung zuWord, es hat nur 1s verbracht, 2x schneller!

Ich habe BangPatterns für eine explizite strenge Evaluierung ausprobiert, aber es konnte kein signifikanter Leistungsgewinn festgestellt werden. Ich denke, die strenge Analyse von GHC ist intelligent genug, um mit einem solch einfachen Szenario umzugehen.

Meine Fragen sind:

Warum ist derWord Version so schneller als dieInt einerWarum ist dieses Haskell-Programm im Vergleich zu C so langsam?