Question Comparaison de vitesse avec Project Euler: C vs Python vs Erlang vs Haskell


j'ai pris Problème n ° 12 de Projet Euler comme un exercice de programmation et de comparer mes implémentations (certainement pas optimales) en C, Python, Erlang et Haskell. Afin d'obtenir des temps d'exécution plus élevés, je recherche le premier nombre de triangle avec plus de 1000 diviseurs au lieu de 500 comme indiqué dans le problème d'origine.

Le résultat est le suivant:

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

Résumé:

  • C: 100%
  • Python: 692% (118% avec PyPy)
  • Erlang: 436% (135% grâce à RichardC)
  • Haskell: 1421%

Je suppose que C a un gros avantage car il utilise longtemps pour les calculs et non pas des entiers de longueur arbitraire comme les trois autres. De plus, il n'a pas besoin de charger un runtime en premier (les autres?).

Question 1: Est-ce que Erlang, Python et Haskell perdent de la vitesse en raison de l'utilisation d'entiers de longueur arbitraires ou non tant que les valeurs sont inférieures à MAXINT?

Question 2: Pourquoi Haskell est-il si lent? Existe-t-il un drapeau de compilateur qui désactive les freins ou est-ce ma mise en œuvre? (Ce dernier est assez probable car Haskell est un livre avec sept sceaux pour moi.)

Question 3: Pouvez-vous me donner quelques conseils pour optimiser ces implémentations sans changer la façon dont je détermine les facteurs? Optimisation de toute façon: plus agréable, plus rapide, plus "native" à la langue.

MODIFIER:

Question 4: Est-ce que mes implémentations fonctionnelles permettent LCO (optimisation du dernier appel, élimination de la récursivité de la queue a.k.a) et donc éviter d'ajouter des trames inutiles sur la pile d'appels?

J'ai vraiment essayé de mettre en œuvre le même algorithme que possible dans les quatre langues, même si je dois admettre que mes connaissances Haskell et Erlang sont très limitées.


Codes source utilisés:

#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

588
2017-08-06 02:34


origine


Réponses:


En utilisant GHC 7.0.3, gcc 4.4.6, Linux 2.6.29 sur une machine Core2 Duo (2.5GHz) x86_64, compilant ghc -O2 -fllvm -fforce-recomp pour Haskell et gcc -O3 -lm pour C.

  • Votre routine C s'exécute en 8.4 secondes (plus rapide que votre course probablement à cause de -O3)
  • La solution Haskell fonctionne en 36 secondes (en raison de la -O2 drapeau)
  • Votre factorCount' le code n'est pas explicitement typé et par défaut Integer (merci à Daniel pour avoir corrigé mon erreur de diagnostic ici!). Donner une signature de type explicite (ce qui est pratique courante de toute façon) en utilisant Int et le temps passe à 11,1 secondes
  • dans factorCount' vous avez appelé inutilement fromIntegral. Un correctif n'entraîne aucun changement (le compilateur est intelligent, chanceux pour vous).
  • Tu as utilisé mod où rem est plus rapide et suffisant. Cela change le temps de 8.5 secondes.
  • factorCount' applique constamment deux arguments supplémentaires qui ne changent jamais (number, sqrt). Une transformation worker / wrapper nous donne:
 $ time ./so
 842161320  

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

C'est vrai, 7,95 secondes. Régulièrement une demi-seconde plus vite que la solution C. Sans le -fllvmdrapeau je reçois toujours 8.182 seconds, donc le backend NCG se porte bien dans ce cas aussi.

Conclusion: Haskell est génial.

Code résultant

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: Alors maintenant que nous avons exploré cela, permet de répondre aux questions

Question 1: Est-ce que erlang, python et haskell perdent de la vitesse en raison de l'utilisation   longueur arbitraire entiers ou ne le font pas tant que les valeurs sont moins   que MAXINT?

À Haskell, en utilisant Integer est plus lent que Int mais combien plus lent dépend des calculs effectués. Heureusement (pour les machines 64 bits) Int est suffisant. Par souci de portabilité, vous devriez probablement réécrire mon code à utiliser Int64 ou Word64 (C n'est pas la seule langue avec un long).

Question 2: Pourquoi le haskell est-il si lent? Y a-t-il un drapeau de compilateur   éteint les freins ou est-ce ma mise en œuvre? (Ce dernier est assez   probable comme haskell est un livre avec sept sceaux pour moi.)

Question 3: Pouvez-vous me donner quelques conseils pour optimiser ces   mises en œuvre sans changer la façon dont je détermine les facteurs?   Optimisation de toute façon: plus agréable, plus rapide, plus "native" à la langue.

C'est ce que j'ai répondu ci-dessus. La réponse était

  • 0) Utiliser l'optimisation via -O2 
  • 1) Utiliser des types rapides (notamment: unbox-able) lorsque cela est possible
  • 2) rem ne pas mod (une optimisation souvent oubliée) et
  • 3) transformation ouvrier / encapsuleur (peut-être l'optimisation la plus courante).

Question 4: Est-ce que mes implémentations fonctionnelles permettent LCO et donc   éviter d'ajouter des trames inutiles sur la pile d'appels?

Oui, ce n'était pas le problème. Bon travail et content que vous ayez réfléchi à cela.


717
2017-08-06 04:25



Il y a quelques problèmes avec la mise en œuvre d'Erlang. Comme référence pour ce qui suit, mon temps d'exécution mesuré pour votre programme Erlang non modifié était de 47,6 secondes, comparé à 12,7 secondes pour le code C.

La première chose à faire si vous voulez exécuter un code Erlang intensif en calcul est d'utiliser du code natif. Compiler avec erlc +native euler12 a eu le temps de descendre à 41,3 secondes. Ceci est cependant une accélération beaucoup plus faible (seulement 15%) que prévu de la compilation native sur ce type de code, et le problème est votre utilisation de -compile(export_all). Ceci est utile pour l'expérimentation, mais le fait que toutes les fonctions soient potentiellement accessibles de l'extérieur fait que le compilateur natif est très conservateur. (L'émulateur BEAM normal n'est pas très affecté.) Remplacer cette déclaration par -export([solve/0]). donne une bien meilleure accélération: 31,5 secondes (près de 35% de la ligne de base).

Mais le code lui-même a un problème: pour chaque itération Dans la boucle factorCount, vous effectuez ce test:

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

Le code C ne le fait pas. En général, il peut être difficile de faire une comparaison équitable entre différentes implémentations du même code, et en particulier si l'algorithme est numérique, car vous devez être sûr qu'il fait la même chose. Une légère erreur d'arrondi dans une mise en œuvre due à une mise en page quelque part peut l'amener à faire beaucoup plus d'itérations que l'autre, même si les deux finissent par atteindre le même résultat.

Pour éliminer cette source d'erreur possible (et se débarrasser du test supplémentaire dans chaque itération), j'ai réécrit la fonction factorCount comme suit, étroitement modélisé sur le code 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.

Cette réécriture, pas export_allet compilation native, m'a donné le temps d'exécution suivant:

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

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

ce qui n'est pas trop mal par rapport au code C:

$ time ./a.out 
842161320

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

Considérant que Erlang n'est pas du tout orienté vers l'écriture de code numérique, être seulement 50% plus lent que C sur un programme comme celui-ci est plutôt bon.

Enfin, concernant vos questions:

Question 1: Est-ce que erlang, python et haskell perdent leur vitesse en raison de l'utilisation d'entiers de longueur arbitraires ou N'est-ce pas aussi longtemps que les valeurs sont inférieures à MAXINT?

Oui, un peu. Dans Erlang, il n'y a aucun moyen de dire "utiliser l'arithmétique 32/64 bits avec wrap-around", donc à moins que le compilateur puisse prouver des limites sur vos entiers (et il ne le peut généralement pas), il doit vérifier tous les calculs pour voir si elles peuvent tenir dans un seul mot étiqueté ou s'il doit les transformer en bignums alloués par tas. Même si aucun bignum n'est utilisé en pratique au moment de l'exécution, ces vérifications devront être effectuées. D'un autre côté, cela signifie que vous connaître que l'algorithme n'échouera jamais à cause d'un retour d'entier inattendu si vous lui donnez soudainement des entrées plus grandes qu'auparavant.

Question 4: Est-ce que mes implémentations fonctionnelles permettent LCO et donc éviter d'ajouter des trames inutiles sur la pile d'appels?

Oui, votre code Erlang est correct en ce qui concerne l'optimisation du dernier appel.


210
2017-08-06 14:20



En ce qui concerne l'optimisation Python, en plus d'utiliser PyPy (pour des accélérations assez impressionnantes avec zéro changement de code), vous pouvez utiliser PyPy outil de traduction compiler une version conforme à RPython, ou Cython pour construire un module d'extension, les deux sont plus rapides que la version C dans mes tests, avec le module Cython presque deux fois plus vite. À titre de référence, j'inclus également les résultats du benchmark C et PyPy:

C (compilé avec 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 (en utilisant la dernière révision de 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

La version RPython a quelques changements clés. Pour traduire en un programme autonome, vous devez définir votre target, qui dans ce cas est le main fonction. Il est prévu d'accepter sys.argv comme c'est seulement un argument, et est nécessaire pour retourner un int. Vous pouvez le traduire en utilisant translate.py, % translate.py euler12-rpython.py ce qui se traduit par C et le compile pour vous.

# 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

La version Cython a été réécrite comme un module d'extension _euler12.pyx, que j'importe et appelle à partir d'un fichier python normal. le _euler12.pyx est essentiellement le même que votre version, avec quelques déclarations de type statique supplémentaires. Le fichier setup.py a la valeur standard pour créer l'extension, en utilisant 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
)

Honnêtement, j'ai très peu d'expérience avec RPython ou Cython, et j'ai été agréablement surpris par les résultats. Si vous utilisez CPython, l'écriture de vos bits de code gourmands en CPU dans un module d'extension Cython semble être un moyen très simple d'optimiser votre programme.


148
2017-08-07 20:04



Question 3:Pouvez-vous me donner quelques conseils pour optimiser ces implémentations?   sans changer la façon dont je détermine les facteurs? Optimisation dans tout   moyen: plus agréable, plus rapide, plus "natif" à la langue.

L'implémentation C est sous-optimale (comme suggéré par Thomas M. DuBuisson), la version utilise des entiers 64 bits (c.-à-d. longue Type de données). Je vais étudier la liste d'assemblage plus tard, mais avec une supposition éclairée, il y a des accès mémoire dans le code compilé, ce qui rend l'utilisation des entiers 64 bits beaucoup plus lente. C'est le code généré ou généré (que ce soit le fait que vous pouvez insérer moins d'octets 64 bits dans un registre SSE ou arrondir un double à un entier 64 bits est plus lent).

Voici le code modifié (remplacez simplement longue avec int et j'ai explicitement souligné factorCount, bien que je ne pense pas que cela soit nécessaire avec 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);
}

Courir + chronométrer cela donne:

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

Pour référence, la mise en œuvre haskell par Thomas dans la réponse précédente donne:

$ 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

Conclusion: Ne rien enlever de ghc, c'est un excellent compilateur, mais gcc génère normalement du code plus rapide.


66
2017-08-12 08:53



Jeter un coup d'œil à ce blog. Au cours de la dernière année, il a fait quelques-uns des problèmes du projet Euler dans Haskell et Python, et il est généralement trouvé Haskell être beaucoup plus rapide. Je pense que, entre ces langues, cela a plus à voir avec votre aisance et votre style de codage.

Quand il s'agit de la vitesse Python, vous utilisez la mauvaise implémentation! Essayer PyPy, et pour des choses comme ça, vous le trouverez beaucoup, beaucoup plus rapide.


53
2017-08-06 03:12



Votre implémentation Haskell pourrait être grandement accélérée en utilisant certaines fonctions des paquets Haskell. Dans ce cas, j'ai utilisé des nombres premiers, qui sont juste installés avec 'cabal install primes';)

import Data.Numbers.Primes
import Data.List

triangleNumbers = scanl1 (+) [1..]
nDivisors n = product $ map ((+1) . length) (group (primeFactors n))
answer = head $ filter ((> 500) . nDivisors) triangleNumbers

main :: IO ()
main = putStrLn $ "First triangle number to have over 500 divisors: " ++ (show answer)

Timings:

Votre programme original:

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

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Mise en œuvre améliorée

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

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Comme vous pouvez le voir, celui-ci s'exécute en 38 millisecondes sur la même machine où la vôtre a fonctionné en 16 secondes :)

Commandes de compilation:

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

30
2017-10-12 04:43



Juste pour le fun. Voici une implémentation Haskell plus "native":

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

En utilisant ghc -O3, cela fonctionne toujours en 0.55-0.58 secondes sur ma machine (1.73GHz Core i7).

Une fonction factorCount plus efficace pour la version 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;
}

Changer longs à ints en main, en utilisant gcc -O3 -lm, cela fonctionne systématiquement dans 0.31-0.35 secondes.

Les deux peuvent être rendus encore plus rapides si vous prenez avantage du fait que le nième nombre de triangles = n * (n + 1) / 2, et n et (n + 1) ont des factorisations premières complètement disparates, donc le nombre de facteurs de chaque moitié peut être multiplié pour trouver le nombre de facteurs de l'ensemble. Le suivant:

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

réduira le temps d'exécution du code c à 0.17-0.19 secondes, et il peut gérer des recherches beaucoup plus importantes - plus de 10000 facteurs prend environ 43 secondes sur ma machine. Je laisse une accélération de haskell similaire au lecteur intéressé.


27
2018-02-20 05:58



Question 1: Est-ce que erlang, python et haskell perdent de la vitesse en raison de l'utilisation d'entiers de longueur arbitraires ou non tant que les valeurs sont inférieures à MAXINT?

C'est improbable. Je ne peux pas en dire beaucoup sur Erlang et Haskell (enfin, peut-être un peu sur Haskell ci-dessous) mais je peux signaler beaucoup d'autres goulots d'étranglement en Python. Chaque fois que le programme essaie d'exécuter une opération avec des valeurs en Python, il doit vérifier si les valeurs sont du bon type, et cela coûte un peu de temps. Votre factorCount fonction attribue juste une liste avec range (1, isquare + 1) plusieurs fois, et l'exécution, mallocl'allocation de mémoire styled est beaucoup plus lente que l'itération sur une plage avec un compteur comme vous le faites en C. Notamment, le factorCount() est appelé plusieurs fois et alloue donc beaucoup de listes. N'oublions pas non plus que Python est interprété et que l'interpréteur CPython n'a pas grand intérêt à être optimisé.

MODIFIER: oh, eh bien, je note que vous utilisez Python 3 donc range() ne renvoie pas une liste, mais un générateur. Dans ce cas, mon point sur l'allocation de listes est à moitié faux: la fonction alloue juste range les objets, qui sont néanmoins inefficaces mais pas aussi inefficaces que l'allocation d'une liste avec beaucoup d'objets.

Question 2: Pourquoi le haskell est-il si lent? Existe-t-il un drapeau de compilateur qui désactive les freins ou est-ce ma mise en œuvre? (Ce dernier est assez probable car haskell est un livre avec sept sceaux pour moi.)

Utilises-tu Câlins? Hugs est un interprète considérablement lent. Si vous l'utilisez, peut-être que vous pouvez passer un meilleur moment avec GHC - mais je ne fais que cogiter l'hypotèse, le genre de choses qu'un bon compilateur Haskell fait sous le capot est assez fascinant et bien au-delà de ma compréhension :)

Question 3: Pouvez-vous m'indiquer comment optimiser ces implémentations sans changer la façon dont je détermine les facteurs? Optimisation de toute façon: plus agréable, plus rapide, plus "native" à la langue.

Je dirais que vous jouez à un jeu peu ordinaire. La meilleure partie de la connaissance de diverses langues est de les utiliser le plus différemment possible :) Mais je m'égare, je n'ai tout simplement pas de recommandation pour ce point. Désolé, j'espère que quelqu'un peut vous aider dans ce cas :)

Question 4: Est-ce que mes implémentations fonctionnelles permettent LCO et donc éviter d'ajouter des trames inutiles sur la pile d'appels?

Aussi loin que je me souvienne, vous devez juste vous assurer que votre appel récursif est la dernière commande avant de renvoyer une valeur. En d'autres termes, une fonction comme celle ci-dessous pourrait utiliser une telle optimisation:

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

Cependant, vous n'auriez pas une telle optimisation si votre fonction était telle que celle ci-dessous, car il y a une opération (multiplication) après l'appel récursif:

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

J'ai séparé les opérations dans certaines variables locales pour préciser quelles opérations sont exécutées. Cependant, le plus courant est de voir ces fonctions comme ci-dessous, mais elles sont équivalentes pour le point que je suis en train de faire:

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

Notez que c'est au compilateur / interprète de décider s'il fera une récursion en queue. Par exemple, l'interpréteur Python ne le fait pas si je me souviens bien (j'ai utilisé Python dans mon exemple uniquement à cause de sa syntaxe courante). De toute façon, si vous trouvez des choses étranges telles que des fonctions factorielles avec deux paramètres (et l'un des paramètres a des noms tels que acc, accumulatoretc.) maintenant vous savez pourquoi les gens le font :)


13
2017-08-06 16:44



Avec Haskell, vous n'avez vraiment pas besoin de penser explicitement aux récursions.

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

Dans le code ci-dessus, j'ai remplacé les récursions explicites dans la réponse de @Thomas avec des opérations de liste communes. Le code fait exactement la même chose sans nous inquiéter de la récurrence de la queue. Il court (~ 7.49s) sur 6% plus lent que la version dans la réponse @Thomas (~ 7,04s) sur ma machine avec GHC 7.6.2, alors que la version C de @Raedwulf fonctionne ~ 3.15s. Il semble que GHC s'est amélioré au cours de l'année.

PS. Je sais que c'est une vieille question, et je tombe sur des recherches google (j'ai oublié ce que je cherchais, maintenant ...). Je voulais juste commenter la question sur la CDO et exprimer mes sentiments à propos de Haskell en général. Je voulais commenter sur la première réponse, mais les commentaires ne permettent pas les blocs de code.


12
2018-02-28 19:26