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

Il y a quelques problèmes avec L'implémentation 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 du code Erlang à forte intensité de calcul est d'utiliser du code natif. Compiler avec erlc +native euler12 a réduit le temps à 41,3 secondes. Ceci est cependant une accélération beaucoup plus faible (juste 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 sont potentiellement accessibles de l'extérieur rend le compilateur natif très conservateur. (L'émulateur de faisceau 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 ceci essai:

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'ils font réellement la même chose. Une légère erreur d'arrondi dans une implémentation due à une typecast 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 cela source d'erreur possible (et se débarrasser du test supplémentaire à chaque itération), j'ai réécrit la fonction factorCount comme suit, étroitement calquée 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, no export_all, et la compilation native, m'ont 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 comparé au code C:

$ time ./a.out 
842161320

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

Considérant Qu'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, en ce qui concerne vos questions:

Question 1: erlang, python et Haskell perdent-ils leur vitesse en utilisant des entiers de longueur arbitraires ou ne le font-ils pas tant 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 ne puisse prouver quelques limites sur vos entiers (et il ne peut généralement pas), il doit vérifier tous les calculs pour voir s'ils peuvent tenir dans un seul mot marqué ou s'il doit les dans des bignums alloués en tas. Même si aucun bignum n'est jamais utilisé en pratique lors de l'exécution, ces vérifications devront être effectuées. D'un autre côté, cela signifie que vous savez que l'algorithme n'échouera jamais à cause d'un wraparound entier inattendu si vous lui donnez soudainement des entrées plus grandes qu'auparavant.

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

Oui, votre code Erlang est correct avec respect de l'optimisation du dernier appel.

En ce qui concerne l'optimisation Python, en plus d'utiliser PyPy (pour des accélérations assez impressionnantes avec zéro changement dans votre code), vous pouvez utiliser translation toolchain de PyPy pour compiler une version compatible RPython, ou Cython pour construire un module d'extension, les deux étant plus rapides que la version C dans mes tests, avec le module Cython presque deux fois plus rapide. Pour référence, j'inclus également les résultats de référence 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 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 modifications clés. Pour traduire en un programme autonome, vous devez définir votre target, qui dans ce cas est la fonction main. Il est attendu d'accepter sys.argv car c'est seulement un argument, et est nécessaire pour renvoyer 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 en tant que 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 setup.py a le standard normal pour construire 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 des résultats. Si vous utilisez CPython, écrire vos bits de code gourmands en CPU dans un module D'extension Cython semble être un moyen très facile d'optimiser votre programme.

Question 3: Pouvez-vous m'offrir quelques conseils pour optimiser ces implémentations sans changer la façon dont je détermine les facteurs? Optimisation dans tout façon: plus beau, plus rapide, plus "natif" de la langue.

L'implémentation C est sous-optimale (comme l'a laissé entendre Thomas M. Dubuisson), la version utilise des entiers 64 bits (c'est-à-dire long datatype). Je vais enquêter sur la liste de l'assemblée plus tard, mais avec une supposition éclairée, il y a des accès à la mémoire dans le code compilé, ce qui rend l'utilisation d'entiers 64 bits significativement plus lente. C'est cela ou le code généré (que ce soit le fait que vous puissiez adapter moins d'ints 64 bits dans un registre SSE ou arrondir un double à un entier 64 bits est plus lent).

Voici le code modifié (remplacez simplement long par int{[15] } et j'ai explicitement intégré 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, le l'implémentation de 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 à ghc, c'est un excellent compilateur, mais gcc génère normalement du code plus rapide.

Jetez un oeil à 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 a généralement trouvé Haskell beaucoup plus rapide. Je pense qu'entre ces langues, cela a plus à voir avec votre aisance et votre style de codage.

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

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 vient d'être installé avec 'cabal install nombres premiers';)

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)

Horaires:

Votre programme original:

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

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Amélioration de la mise en œuvre

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

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Comme vous pouvez le voir, celui-ci fonctionne en 38 millisecondes sur la même machine où le vôtre a couru en 16 secondes:)

Commandes de Compilation:

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

Juste pour le plaisir. Ce qui suit est 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 systématiquement en 0.55-0.58 secondes sur ma machine (1.73 GHz 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 les longs en ints dans main, en utilisant gcc -O3 -lm, cela s'exécute systématiquement en 0,31-0,35 secondes.

Les deux peuvent être faits pour fonctionner encore plus vite si vous profitez du fait que le nième nombre de triangle = n*(n + 1) / 2, et n et (n+1) ont complètement disparates premier factorisations, de sorte que le nombre de facteurs de chaque moitié peut être multipliée pour trouver le nombre de facteurs de l'ensemble. Ce qui suit:

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 Haskell similaire au lecteur intéressé.

Question 1: erlang, python et haskell perdent-ils de la vitesse en utilisant des entiers de longueur arbitraires ou ne le font-ils pas tant que les valeurs sont inférieures à MAXINT?

C'est peu probable. Je ne peux pas en dire beaucoup sur Erlang et Haskell (enfin, peut-être un peu sur Haskell ci-dessous) mais je peux pointer 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 proviennent du type approprié, et cela coûte un peu de temps. Votre fonction factorCount alloue juste une liste avec range (1, isquare + 1) plusieurs fois, et l'exécution, l'allocation de mémoire de style malloc est beaucoup plus lente que l'itération sur une plage avec un compteur comme vous le faites en C. notamment, le {[6] } est appelé plusieurs fois et alloue donc beaucoup de listes. Aussi, n'oublions pas que Python est interprété et que L'interpréteur CPython n'a pas beaucoup d'intérêt à être optimisé.

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

Question 2: Pourquoi haskell est-il si lent? Y a-t-il un drapeau du compilateur qui éteint les freins ou est-ce mon implémentation? (Ce dernier est tout à fait probable que haskell est un livre avec sept sceaux pour moi.)

Utilisez-vouscâlins ? Câlins est un considérablement ralentir interprète. Si vous l'utilisez, peut - être que vous pouvez obtenir un meilleur moment avec GHC - Mais je ne cogite que 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'offrir quelques conseils pour optimiser ces implémentations sans changer la façon dont je détermine les facteurs? Optimisation en aucune façon: plus agréable, plus rapide, plus "natif" de la langue.

Je dirais que vous jouez un pas drôle de jeu. La meilleure partie de la connaissance des différentes langues est de les utiliser de la manière la plus différente possible :) mais je m'égare, Je n'ai tout simplement aucune 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 autorisent LCO et évitent donc d'ajouter des trames inutiles sur la pile d'appels?

Pour autant que je me souvienne, vous devez juste vous assurer que votre appel récursif est la dernière commande avant de renvoyer une valeur. Dans 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'aurait pas une telle optimisation si votre fonction comme 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 habituel est de voir ces fonctions comme ci-dessous, mais elles sont équivalentes pour le point que je suis fabrication:

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 qu'il appartient au compilateur / interpréteur de décider s'il fera une récursivité de queue. Par exemple, l'interpréteur Python ne le fait pas si je me souviens bien (j'ai utilisé Python dans mon exemple seulement à cause de sa syntaxe fluide). Quoi qu'il en soit, 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, accumulator etc.) maintenant, vous savez pourquoi les gens le faire :)

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 par des opérations de Liste communes. Le code fait toujours exactement la même chose sans nous soucier de la récursivité de la queue. Il fonctionne (~ 7.49 s ) à propos de 6% plus lent que la version dans la réponse de @Thomas (~7.04 s) sur ma machine avec GHC 7.6.2, tandis que la version C de @Raedwulf tourne ~ 3.15 s. Il semble GHC s'est améliorée au cours de l'année.

PS. Je sais que c'est une vieille question, et je trébuche sur elle à partir des recherches google (j'ai oublié ce que je cherchais, maintenant...). Je voulais juste commenter la question sur LCO et exprimer mes sentiments à propos de Haskell en général. Je voulais commenter la réponse supérieure, mais les commentaires n'autorisent pas les blocs de code.

En regardant votre implémentation Erlang. Le calendrier a inclus le démarrage de l'ensemble de la machine virtuelle, l'exécution de votre programme et l'arrêt de la machine virtuelle. Je suis sûr que la configuration et l'arrêt de la machine virtuelle erlang prennent du temps.

Si le timing était fait dans la machine virtuelle erlang elle-même, les résultats seraient différents car dans ce cas, nous aurions le temps réel pour seulement le programme en question. Sinon, je crois que le temps total pris par le processus de démarrage et le chargement de la machine virtuelle Erlang plus celui de l'arrêter (comme vous le mettez dans votre programme) sont tous inclus dans le temps total pendant lequel la méthode que vous utilisez pour chronométrer le programme sort. Pensez à utiliser le timing erlang lui même que nous utilisons lorsque nous voulons chronométrer nos programmes dans la machine virtuelle elle même timer:tc/1 or timer:tc/2 or timer:tc/3. De cette façon, les résultats d'erlang excluront le temps nécessaire pour démarrer et arrêter/tuer/arrêter la machine virtuelle. C'est mon raisonnement là-bas, pensez-y, et ensuite, essayez à nouveau votre point de repère.

En fait, je suggère que nous essayions de chronométrer le programme (pour les langues qui ont un runtime), dans le runtime de ces langues afin d'obtenir une valeur précise. C par exemple n'a pas de surcharge de démarrage et d'arrêt d'un système d'exécution comme le font Erlang, Python et Haskell (98% sûr de cela - je tiens la correction). Donc (sur la base de ce raisonnement), je conclus en disant que ce benchmark n'était pas assez précis /juste pour les langues fonctionnant au-dessus d'un runtime système. Faisons-le à nouveau avec ces changements.

EDIT: de plus, même si toutes les langues avaient des systèmes d'exécution, la surcharge de démarrage et d'arrêt différerait. donc, je suggère de temps à partir des systèmes d'exécution (pour les langues pour lesquelles cela s'applique). La VM Erlang est connue pour avoir des frais généraux considérables au démarrage!

Quelques chiffres et explications supplémentaires pour la version C. Apparemment personne ne l'a fait pendant toutes ces années. Rappelez-vous de voter cette réponse afin qu'elle puisse être au top pour que tout le monde puisse voir et apprendre.

Première étape: Benchmark des programmes de l'auteur

Ordinateur Portable Spécifications:

• CPU I3 M380 (931 MHz - mode d'économie de batterie maximale)
• 4 Go de mémoire
• Win7 64 bits
• Microsoft Visual Studio 2012 Ultime
• Cygwin avec gcc 4.9.3
• Python 2.7.10

Commandes:

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

Les noms de fichiers sont: integertype_architecture_compiler.exe

• integertype est le même que le programme d'origine pour l'instant (plus sur cela plus tard)
• l'architecture Est x86 ou x64 en fonction des paramètres du compilateur
• compilateur est gcc ou vs2012

Deuxième étape: enquêter, améliorer et Benchmark à nouveau

VS est 250% plus rapide que gcc. Les deux les compilateurs devraient donner une vitesse similaire. Évidemment, quelque chose ne va pas avec le code ou les options du compilateur. Examinons de plus près!

Le premier point d'intérêt est les types entiers. Les Conversions peuvent être coûteuses et la cohérence est importante pour une meilleure génération de code et optimisations. Tous les entiers doivent être du même type.

C'est un gâchis mixte de int et long en ce moment. Nous allons l'améliorer. Quel type d'utilisation? La manière la plus rapide. Dois référence eux tous!

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

Les types d'Entiers sont int long int32_t uint32_t int64_t et uint64_t à partir de #include <stdint.h>

Il y a beaucoup de types entiers en C, plus certains signés / non signés pour jouer avec, plus le choix de compiler EN x86 ou x64 (à ne pas confondre avec la taille entière réelle). C'est beaucoup de versions à compiler et à exécuter ^^

Troisième étape: comprendre les nombres

Conclusions Définitives:

• 32 bits entiers sont ~200% PLUS RAPIDE QUE 64 bits équivalents
• 64 bits non signés les entiers sont 25 % plus rapides que 64 bits signés (malheureusement, je n'ai aucune explication à cela)

Question Trick: "quelles sont les tailles de int et long en C?"
La bonne réponse est: la taille de int et long en C ne sont pas bien définies!

De la spécification C:

Int est au moins 32 bits
long est au moins un int

À partir de la page de manuel gcc (drapeaux-m32 et-m64):

L'environnement 32 bits définit int, long et pointer sur 32 bits et génère du code qui s'exécute sur n'importe quel système i386.
L'environnement 64 bits définit int sur 32 bits et long et le pointeur sur 64 bits et génère du code pour L'architecture x86-64 D'AMD.

De la documentation MSDN (plages de types de données) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :

Int, 4 octets, sait aussi comme signé
long, 4 octets, sait aussi long int et signé long int

Pour Conclure Ceci: Leçons Apprises

• 32 les entiers de bits sont plus rapides que les entiers de 64 bits.

• Les types D'entiers Standard ne sont pas bien définis en C ni en C++, ils varient en fonction des compilateurs et architecture. Lorsque vous avez besoin de cohérence et de prévisibilité, utilisez la famille d'entiers uint32_t de #include <stdint.h>.

• Problèmes de vitesse résolus. Toutes les autres langues sont de retour des centaines pour cent derrière, c & c++ gagner à nouveau ! Ils le font toujours. La prochaine amélioration sera multithreading en utilisant OpenMP: d

Question 1: Erlang, Python et Haskell perdent-ils de la vitesse en utilisant entiers de longueur arbitraire ou ne le font-ils pas tant que les valeurs sont inférieures que exemple maxint?

On peut répondre à la première question par la négative pour Erlang. La dernière question Est répondue en utilisant Erlang de manière appropriée, comme dans:

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

Comme il est plus rapide que votre exemple c initial, je suppose qu'il y a de nombreux problèmes comme d'autres ont déjà abordé en détail.

Ce module Erlang s'exécute sur un netbook bon marché en environ 5 secondes ... Il utilise le modèle de threads réseau dans erlang et, en tant que tel, montre comment tirer parti du modèle d'événement. Il pourrait être distribué sur de nombreux nœuds. Et c'est rapide. Pas mon code.

-module(p12dist).  
-author("Jannich Brendle, jannich@bredsaal.dk, 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.

Le test ci-dessous a eu lieu sur un: Intel (R) Atom (TM) CPU N270 @ 1.60 GHz

~$ time erl -noshell -s p12dist start

The result is: 76576500.

^C

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

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

C++11, - Exécuter ici

Je comprends que vous voulez des conseils pour aider à améliorer vos connaissances spécifiques à la langue, mais comme cela a été bien couvert ici, j'ai pensé ajouter un peu de contexte pour les personnes qui ont peut-être regardé le commentaire mathematica sur votre question, etc, et je me demandais pourquoi ce code était tellement plus lent.

Cette réponse est principalement pour fournir un contexte pour aider les gens à évaluer le code dans votre question / autre des réponses plus facilement.

CE code n'utilise que quelques optimisations (laides), sans rapport avec le langage utilisé, basées sur:

1. chaque nombre de traingle est de la forme n (n+1)/2
2. n et n+1 sont premiers entre eux
3. le nombre de diviseurs est une fonction multiplicative

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

Cela prend environ 19ms en moyenne pour mon bureau et 80ms pour mon ordinateur portable, loin de la plupart des autres codes que j'ai vus ici. Et il y a, non doute, de nombreuses optimisations encore disponibles.

Essayer GO:

package main

import "fmt"
import "math"

func main() {
    var n, m, c int
    for i := 1; ; i++ {
        n, m, c = i * (i + 1) / 2, int(math.Sqrt(float64(n))), 0
        for f := 1; f < m; f++ {
            if n % f == 0 { c++ }
    }
    c *= 2
    if m * m == n { c ++ }
    if c > 1001 {
        fmt.Println(n)
        break
        }
    }
}

Je reçois:

Original version c: 9.1690 100%
aller: 8.2520 111%

, Mais en utilisant:

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
}

Je reçois:

Original version c: 9.1690 100%
la version c de thaumkid: 0.1060 8650%
allez d'abord la version: 8.2520 111%
deuxième version: 0.0230 39865%

J'ai aussi essayé Python3. 6 et pypy3. 3-5. 5-alpha:

D'origine c version: 8.629 100%
la version c de thaumkid: 0.109 7916%
Python3.6: 54.795 16%
pypy3. 3-5. 5-alpha: 13.291 65%

Et puis avec le code suivant j'ai eu:

Original version c: 8.629 100%
la version c de thaumkid: 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)

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

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

Cela produira la bonne réponse pour L'exemple Erlang multi-process.

J'ai fait l'hypothèse que le nombre de facteurs n'est important que si les nombres impliqués ont beaucoup de petits facteurs. J'ai donc utilisé l'excellent algorithme de thaumkid, mais j'ai d'abord utilisé une approximation du nombre de facteurs qui n'est jamais trop petit. C'est assez simple: vérifiez les facteurs premiers jusqu'à 29, puis vérifiez le nombre restant et calculez une limite supérieure pour le nombre de facteurs. Utilisez ceci pour calculer une limite supérieure pour le nombre de facteurs, et si ce nombre est assez élevé, calculez le nombre exact certain nombre de facteurs.

Le code ci-dessous n'a pas besoin de cette hypothèse pour l'exactitude, mais pour être rapide. Cela semble fonctionner; seulement environ un nombre Sur 100 000 donne une estimation suffisamment élevée pour nécessiter une vérification complète.

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

Cela trouve le 14,753,024 ème triangulaire avec 13824 facteurs en environ 0,7 secondes, le 879,207,615 ème nombre triangulaire avec 61,440 facteurs en 34 secondes, le 12,524,486,975 ème nombre triangulaire avec 138,240 facteurs en 10 minutes 5 secondes, et le 26,467,792,064 e Nombre triangulaire avec 172,032 facteurs en 21 minutes 25 secondes (2,4 GHz Core2 Duo), de sorte que ce code ne prend que 116 cycles de processeur par nombre en moyenne. Le dernier nombre triangulaire lui-même est plus grand que 2 ^ 68, donc

J'ai modifié la version "Jannich Brendle" à 1000 au lieu de 500. Et liste le résultat de euler12.bin, euler12.erl, p12dist.erl. Les deux codes erl utilisent '+ native ' pour compiler.

zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s p12dist start
The result is: 842161320.

real    0m3.879s
user    0m14.553s
sys     0m0.314s
zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s euler12 solve
842161320

real    0m10.125s
user    0m10.078s
sys     0m0.046s
zhengs-MacBook-Pro:workspace zhengzhibin$ time ./euler12.bin 
842161320

real    0m5.370s
user    0m5.328s
sys     0m0.004s
zhengs-MacBook-Pro:workspace zhengzhibin$

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square+1;
    long candidate = 2;
    int count = 1;
    while(candidate <= isquare && candidate<=n){
        int c = 1;
        while (n % candidate == 0) {
           c++;
           n /= candidate;
        }
        count *= c;
        candidate++;
    }
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

Gcc-lm-Ofast euler.c

Temps ./un.hors

2.79 s Utilisateur 0.00 s système 99% cpu 2.794 total