speed - Comparação de velocidade com o Projeto Euler: C vs Python vs Erlang vs Haskell




performance javascript vs python (12)

Eu peguei o Problema # 12 do Project Euler como um exercício de programação e comparei minhas implementações (certamente não ótimas) em C, Python, Erlang e Haskell. Para obter tempos de execução mais altos, procuro o primeiro número do triângulo com mais de 1000 divisores, em vez de 500, conforme indicado no problema original.

O resultado é o seguinte:

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

Resumo:

  • C: 100%
  • Python: 692% (118% com PyPy)
  • Erlang: 436% (135% obrigado a RichardC)
  • Haskell: 1421%

Suponho que C tenha uma grande vantagem, pois usa muito para os cálculos e não inteiros de comprimento arbitrário como os outros três. Também não precisa carregar um tempo de execução primeiro (faça os outros?).

Pergunta 1: Erlang, Python e Haskell perdem velocidade devido ao uso de inteiros arbitrários ou não, desde que os valores sejam menores que MAXINT ?

Pergunta 2: Por que o Haskell é tão lento? Existe uma bandeira de compilação que desliga os freios ou é minha implementação? (O último é bastante provável, pois Haskell é um livro com sete selos para mim.)

Pergunta 3: Você pode me oferecer algumas dicas sobre como otimizar essas implementações sem alterar a maneira como determino os fatores? Otimização de qualquer maneira: mais agradável, mais rápido, mais "nativo" para o idioma.

EDITAR:

Pergunta 4: As minhas implementações funcionais permitem LCO (otimização de última chamada, eliminação de recursão de cauda) e, portanto, evitam adicionar quadros desnecessários à pilha de chamadas?

Eu realmente tentei implementar o mesmo algoritmo o mais similar possível nos quatro idiomas, embora eu tenha que admitir que o meu conhecimento em Haskell e Erlang é muito limitado.

Códigos-fonte usados:

#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

Pergunta 1: erlang, python e haskell perderam velocidade devido ao uso de inteiros arbitrários ou não, desde que os valores sejam menores que MAXINT?

Isso é improvável. Eu não posso dizer muito sobre Erlang e Haskell (bem, talvez um pouco sobre Haskell abaixo), mas eu posso apontar muitos outros gargalos no Python. Toda vez que o programa tenta executar uma operação com alguns valores em Python, ele deve verificar se os valores são do tipo adequado e se custa um pouco de tempo. Sua função factorCount apenas aloca uma lista com range (1, isquare + 1) várias vezes e a alocação de memória em tempo de execução, malloc -styled é muito mais lenta do que iterar em um intervalo com um contador como em C. Notavelmente, o factorCount() é chamado várias vezes e, portanto, aloca muitas listas. Além disso, não nos esqueçamos que o Python é interpretado e o interpretador CPython não tem grande foco em ser otimizado.

EDIT : oh, bem, eu note que você está usando o Python 3 assim range() não retorna uma lista, mas um gerador. Nesse caso, meu ponto sobre alocação de listas é meio errado: a função apenas aloca objetos de range , que são ineficientes, mas não tão ineficientes quanto a alocação de uma lista com muitos itens.

Pergunta 2: Por que o haskell é tão lento? Existe uma bandeira de compilação que desliga os freios ou é minha implementação? (O último é bastante provável, pois haskell é um livro com sete selos para mim.)

Você está usando Hugs ? Abraços é um interpretador consideravelmente lento. Se você estiver usando, talvez você possa ter um tempo melhor com o GHC - mas eu estou apenas cogitando hipoteses, o tipo de coisa que um bom compilador de Haskell faz sob o capô é muito fascinante e muito além da minha compreensão :)

Pergunta 3: Você pode me oferecer algumas dicas sobre como otimizar essas implementações sem alterar a maneira como determino os fatores? Otimização de qualquer maneira: mais agradável, mais rápido, mais "nativo" para o idioma.

Eu diria que você está jogando um jogo sem graça. A melhor parte de conhecer vários idiomas é usá-los da maneira mais diferente possível :) Mas eu discordo, eu simplesmente não tenho nenhuma recomendação para este ponto. Desculpe, espero que alguém possa ajudá-lo neste caso :)

Pergunta 4: As minhas implementações funcionais permitem LCO e, portanto, evitam adicionar quadros desnecessários à pilha de chamadas?

Tanto quanto me lembro, você só precisa ter certeza de que sua chamada recursiva é o último comando antes de retornar um valor. Em outras palavras, uma função como a abaixo poderia usar essa otimização:

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

No entanto, você não teria essa otimização se sua função fosse a seguinte, porque há uma operação (multiplicação) após a chamada recursiva:

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

Eu separei as operações em algumas variáveis ​​locais para deixar claro quais operações são executadas. No entanto, o mais comum é ver essas funções como abaixo, mas elas são equivalentes para o ponto que estou fazendo:

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

Note que cabe ao compilador / intérprete decidir se ele fará a recursão da cauda. Por exemplo, o interpretador Python não faz isso se eu me lembro bem (eu usei Python no meu exemplo apenas por causa de sua sintaxe fluente). De qualquer forma, se você encontrar coisas estranhas como funções fatoriais com dois parâmetros (e um dos parâmetros tem nomes como acc , accumulator etc.) agora você sabe porque as pessoas fazem isso :)


Pergunta 3: Você pode me oferecer algumas dicas sobre como otimizar essas implementações sem alterar a maneira como determino os fatores? Otimização de qualquer maneira: mais agradável, mais rápido, mais "nativo" para o idioma.

A implementação de C é sub-ótima (como sugerido por Thomas M. DuBuisson), a versão usa números inteiros de 64 bits (isto é, tipo de dados longo ). Vou investigar a listagem de montagem mais tarde, mas com um palpite, existem alguns acessos de memória acontecendo no código compilado, o que torna o uso de inteiros de 64 bits significativamente mais lento. É isso ou código gerado (seja o fato de que você pode ajustar menos ints de 64 bits em um registrador SSE ou arredondar um double para um inteiro de 64 bits é mais lento).

Aqui está o código modificado (basta substituir long por int e explicitamente fatorCount, embora eu não ache que isso seja necessário com 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);
}

Correndo + tempo dá:

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

Para referência, a implementação do haskell por Thomas na resposta anterior fornece:

$ 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

Conclusão: Não tirar nada do ghc, é um ótimo compilador, mas o gcc normalmente gera um código mais rápido.


Apenas por diversão. A seguir, uma implementação mais nativa do Haskell:

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

Usando ghc -O3 , isso é executado consistentemente em 0,55-0,58 segundos na minha máquina (Core i7 de 1,73 GHz).

Uma função factorCount mais eficiente para a versão 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;
}

Mudando longs para ints no main, usando gcc -O3 -lm , isto é executado consistentemente em 0.31-0.35 segundos.

Ambos podem ser feitos para rodar ainda mais rápido se você tirar vantagem do fato de que o número n-triplo = n * (n + 1) / 2, e n e (n + 1) têm fatorações primárias completamente díspares, portanto o número de fatores de cada metade pode ser multiplicada para encontrar o número de fatores do todo. Os seguintes:

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

irá reduzir o tempo de execução do código c para 0,17-0,19 segundos, e pode lidar com pesquisas muito maiores - mais de 10000 fatores levam cerca de 43 segundos na minha máquina. Deixo uma aceleração haskell semelhante para o leitor interessado.


Com Haskell, você realmente não precisa pensar em recursões explicitamente.

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

No código acima, substituí as recursões explícitas na resposta do @ Thomas com operações de lista comuns. O código ainda faz exatamente a mesma coisa sem nos preocuparmos com a recursão da cauda.Ele roda (~ 7.49s ) cerca de 6% mais lento que a versão na resposta do @ Thomas (~ 7.04s ) na minha máquina com o GHC 7.6.2, enquanto a versão C do @Raedwulf roda ~ 3.15s . Parece que o GHC melhorou ao longo do ano.

PS.Eu sei que é uma questão antiga, e eu me deparo com isso de pesquisas no Google (eu esqueci o que eu estava procurando, agora ...). Só queria comentar a questão sobre LCO e expressar meus sentimentos sobre Haskell em geral. Eu queria comentar sobre a resposta principal, mas os comentários não permitem bloqueios de código.


Existem alguns problemas com a implementação do Erlang. Como referência para o seguinte, o tempo de execução medido para o programa Erlang não modificado foi de 47,6 segundos, comparado a 12,7 segundos para o código C.

A primeira coisa que você deve fazer se quiser executar um código Erlang intensivo em computação é usar o código nativo. Compilando com erlc +native euler12 o tempo para 41.3 segundos. No entanto, esta é uma aceleração muito menor (apenas 15%) do que a esperada da compilação nativa nesse tipo de código, e o problema é o uso de -compile(export_all) . Isso é útil para experimentação, mas o fato de que todas as funções são potencialmente acessíveis a partir do exterior faz com que o compilador nativo seja muito conservador. (O emulador BEAM normal não é muito afetado.) Substituindo esta declaração por -export([solve/0]). dá uma aceleração muito melhor: 31,5 segundos (quase 35% da linha de base).

Mas o próprio código tem um problema: para cada iteração no loop factorCount, você realiza este teste:

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

O código C não faz isso. Em geral, pode ser complicado fazer uma comparação justa entre diferentes implementações do mesmo código e, em particular, se o algoritmo é numérico, porque você precisa ter certeza de que eles estão realmente fazendo a mesma coisa. Um ligeiro erro de arredondamento em uma implementação devido a algum typecast em algum lugar pode fazer com que ele faça muito mais iterações do que o outro, embora ambos eventualmente alcancem o mesmo resultado.

Para eliminar essa possível fonte de erro (e livrar-se do teste extra em cada iteração), reescrevi a função factorCount da seguinte maneira, modelada de perto no código 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.

Essa reescrita, no export_all e nativa, me deu o seguinte tempo de execução:

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

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

o que não é muito ruim comparado ao código C:

$ time ./a.out 
842161320

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

Considerando que Erlang não é de todo voltado para escrever código numérico, sendo apenas 50% mais lento que C em um programa como este é muito bom.

Finalmente, em relação às suas perguntas:

Pergunta 1: erlang, python e haskell perderam velocidade devido ao uso de inteiros arbitrários ou não, desde que os valores sejam menores que MAXINT?

Sim, um pouco. Em Erlang, não há como dizer "use aritmética de 32/64-bit com wrap-around", a menos que o compilador possa provar alguns limites em seus inteiros (e geralmente não pode), ele deve checar todas as computações para ver se eles puderem se encaixar em uma única palavra marcada ou se ela precisar transformá-los em bignums alocados em heap. Mesmo que nenhum bignums seja usado na prática em tempo de execução, essas verificações terão que ser realizadas. Por outro lado, isso significa que você sabe que o algoritmo nunca falhará devido a um inteiro inesperado se você de repente fornecer insumos maiores do que antes.

Pergunta 4: As minhas implementações funcionais permitem LCO e, portanto, evitam adicionar quadros desnecessários à pilha de chamadas?

Sim, o seu código Erlang está correto em relação à otimização da última chamada.


No que diz respeito à otimização do Python, além de usar o PyPy (para acelerações bastante impressionantes sem mudar o código), você poderia usar o toolchain de tradução do PyPy para compilar uma versão compatível com o RPython, ou o Cython para construir um módulo de extensão. que são mais rápidos que a versão C nos meus testes, com o módulo Cython quase duas vezes mais rápido . Para referência eu também incluo os resultados de benchmark C e PyPy:

C (compilado com 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 (usando a última revisão do c2f583445aee , 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

A versão do RPython tem algumas mudanças importantes. Para traduzir em um programa autônomo, você precisa definir seu target , que neste caso é a função main . Espera-se aceitar sys.argv como é apenas argumento, e é necessário retornar um int. Você pode traduzi-lo usando translate.py, % translate.py euler12-rpython.py que se traduz em C e o compila para você.

# 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

A versão do Cython foi reescrita como um módulo de extensão _euler12.pyx , que eu importo e chamo de um arquivo python normal. O _euler12.pyx é essencialmente o mesmo que sua versão, com algumas declarações de tipo estáticas adicionais. O setup.py tem o clichê normal para construir a extensão, usando o 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
)

Eu honestamente tenho pouca experiência com RPython ou Cython, e fiquei agradavelmente surpreso com os resultados. Se você estiver usando o CPython, escrever seus bits de código intensivos de CPU em um módulo de extensão do Cython parece ser uma maneira realmente fácil de otimizar seu programa.


Usando o GHC 7.0.3 , gcc 4.4.6 , Linux 2.6.29 em uma máquina x86_64 Core2 Duo (2.5GHz), compilando usando ghc -O2 -fllvm -fforce-recomp para Haskell e gcc -O3 -lm para C.

  • Sua rotina C é executada em 8,4 segundos (mais rápido que sua corrida provavelmente por causa de -O3 )
  • A solução Haskell é executada em 36 segundos (devido à sinalização -O2 )
  • factorCount' código do seu factorCount' não é explicitamente digitado e padronizado como Integer (graças a Daniel por corrigir o meu erro de diagnóstico aqui!). Dar uma assinatura de tipo explícita (que é a prática padrão de qualquer maneira) usando Int e a hora muda para 11.1 segundos
  • em factorCount' você chamou desnecessariamente de fromIntegral . Uma correção resulta em nenhuma mudança embora (o compilador é inteligente, sorte para você).
  • Você usou mod onde rem é mais rápido e suficiente. Isso muda o tempo para 8,5 segundos .
  • factorCount' está constantemente aplicando dois argumentos extras que nunca mudam ( number , sqrt ). Uma transformação de trabalhador / wrapper nos dá:
 $ time ./so
 842161320  

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

Isso mesmo, 7,95 segundos . Consistentemente meio segundo mais rápido que a solução C. Sem o sinalizador -fllvm eu ainda estou conseguindo 8.182 seconds , então o backend do NCG está indo bem também neste caso.

Conclusão: Haskell é incrível.

Código resultante

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: Então agora que nós exploramos isso, vamos abordar as questões

Pergunta 1: O erlang, o python e o haskell perdem velocidade devido ao uso de inteiros arbitrários ou não, desde que os valores sejam menores que MAXINT?

Em Haskell, usar Integer é mais lento que Int mas quanto mais lento depende dos cálculos realizados. Felizmente (para máquinas de 64 bits) Int é suficiente. Por portabilidade você provavelmente deveria reescrever meu código para usar Int64 ou Word64 (C não é o único idioma com um long ).

Pergunta 2: Por que o haskell é tão lento? Existe uma bandeira de compilação que desliga os freios ou é minha implementação? (O último é bastante provável, pois haskell é um livro com sete selos para mim.)

Pergunta 3: Você pode me oferecer algumas dicas sobre como otimizar essas implementações sem alterar a maneira como determino os fatores? Otimização de qualquer maneira: mais agradável, mais rápido, mais "nativo" para o idioma.

Isso foi o que eu respondi acima. A resposta foi

  • 0) Use a otimização via -O2
  • 1) Use tipos rápidos (notavelmente: unbox-able) quando possível
  • 2) rem não mod (uma otimização freqüentemente esquecida) e
  • 3) transformação de trabalhador / wrapper (talvez a otimização mais comum).

Pergunta 4: As minhas implementações funcionais permitem LCO e, portanto, evitam adicionar quadros desnecessários à pilha de chamadas?

Sim, esse não era o problema. Bom trabalho e feliz que você considerou isso.


C ++ 11, <20ms para mim - Execute aqui

Eu entendo que você quer dicas para ajudar a melhorar o seu conhecimento específico da língua, mas desde que foi bem abordado aqui, eu pensei em adicionar algum contexto para pessoas que possam ter olhado para o comentário da matemática sobre sua questão, etc, e perguntado por que isso código era muito mais lento.

Esta resposta é principalmente para fornecer contexto para ajudar as pessoas a avaliar o código em sua pergunta / outras respostas com mais facilidade.

Este código usa apenas algumas otimizações (feias), não relacionadas ao idioma usado, com base em:

  1. todo número de traingle é da forma n (n + 1) / 2
  2. n e n + 1 são coprime
  3. o número de divisores é uma função multiplicativa

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

Isso leva cerca de 19ms em média para o meu desktop e 80ms para o meu laptop, muito longe da maioria dos outros códigos que vi aqui. E há, sem dúvida, muitas otimizações ainda disponíveis.


Tentando ir:

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

Eu recebo:

versão original c: 9.1690 100%
go: 8.2520 111%

Mas usando:

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
}

Eu recebo:

versão original c: 9.1690 100%
versão c do thaumkid: 0.1060 8650%
primeira versão go: 8.2520 111%
segunda versão go: 0.0230 39865%

Eu também tentei Python3.6 e pypy3.3-5.5-alpha:

versão original c: 8.629 100%
versão c do thaumkid: 0.109 7916%
Python3.6: 54.795 16%
pypy3.3-5.5-alpha: 13.291 65%

e então com o seguinte código eu obtive:

versão original c: 8.629 100%
versão c do 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)

Eu assumi que o número de fatores é grande apenas se os números envolvidos tiverem muitos fatores pequenos. Então eu usei o excelente algoritmo da thaumkid, mas primeiro usei uma aproximação para a contagem de fator que nunca é muito pequena. É bastante simples: Verifique os fatores primos até 29, depois verifique o número restante e calcule um limite superior para o número de fatores. Use isso para calcular um limite superior para o número de fatores e, se esse número for alto o suficiente, calcule o número exato de fatores.

O código abaixo não precisa dessa suposição para correção, mas para ser rápido. Parece funcionar; apenas cerca de um em 100.000 números fornece uma estimativa que é alta o suficiente para exigir uma verificação completa.

Aqui está o código:

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

Este encontra o 14,753,024º triangular com 13824 fatores em cerca de 0,7 segundos, o 879,207,615º número triangular com 61,440 fatores em 34 segundos, o 12,524,486,975º número triangular com 138,240 fatores em 10 minutos 5 segundos e o 26,467,792,064º número triangular com 172,032 fatores em 21 minutos e 25 segundos (2.4GHz Core2 Duo), portanto, este código leva apenas 116 ciclos de processador por número, em média. O último número triangular em si é maior que 2 ^ 68, então


Mais alguns números e explicações para a versão C. Aparentemente, ninguém fez isso durante todos esses anos. Lembre-se de defender esta resposta para que ela possa ficar no topo para que todos vejam e aprendam.

Primeiro Passo: Benchmark dos programas do autor

Especificações do Laptop:

  • CPU i3 M380 (931 MHz - modo de economia máxima de bateria)
  • Memória de 4GB
  • Win7 64 bits
  • Microsoft Visual Studio 2012 Ultimate
  • Cygwin com gcc 4.9.3
  • Python 2.7.10

Comandos:

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

Nomes de arquivos são: integertype_architecture_compiler.exe

  • integertype é o mesmo que o programa original por enquanto (mais sobre isso depois)
  • arquitetura é x86 ou x64, dependendo das configurações do compilador
  • compilador é gcc ou vs2012

Etapa dois: investigar, melhorar e avaliar novamente

O VS é 250% mais rápido que o gcc. Os dois compiladores devem dar uma velocidade semelhante. Obviamente, algo está errado com o código ou as opções do compilador. Vamos investigar!

O primeiro ponto de interesse é os tipos inteiros. As conversões podem ser caras e a consistência é importante para uma melhor geração de códigos e otimizações. Todos os inteiros devem ser do mesmo tipo.

É uma bagunça misturada inte longagora mesmo. Nós vamos melhorar isso. Que tipo usar? O mais rápido. Tenho que me comparar com todos!

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

Tipos inteiros são int long int32_t uint32_t int64_te uint64_tde#include <stdint.h>

Existem LOTES de tipos inteiros em C, além de alguns assinados / não assinados para serem usados, além da opção de compilar como x86 ou x64 (não confundir com o tamanho real do inteiro). Isso é um monte de versões para compilar e executar ^^

Terceiro Passo: Entendendo os Números

Conclusões definitivas:

  • 32 bits inteiros são ~ 200% mais rápidos do que 64 bits equivalentes
  • inteiros de 64 bits não assinados são 25% mais rápidos que os 64 bits assinados (Infelizmente, não tenho explicação para isso)

Pergunta enganosa: "Quais são os tamanhos de int e long em C?"
A resposta correta é: O tamanho de int e long em C não está bem definido!

Das especificações C:

int tem pelo menos 32 bits
é pelo menos um int

Na página man do gcc (sinalizadores -m32 e -m64):

O ambiente de 32 bits define int, long e pointer como 32 bits e gera código que é executado em qualquer sistema i386.
O ambiente de 64 bits define int como 32 bits e longo e aponta para 64 bits e gera código para a arquitetura x86-64 da AMD.

Da documentação do MSDN (Data Type Ranges) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :

int, 4 bytes, também sabe como assinada
longa, 4 bytes, também sabe como long int e assinou long int

Para concluir isto: lições aprendidas

  • Os inteiros de 32 bits são mais rápidos que os inteiros de 64 bits.

  • Tipos inteiros padrão não são bem definidos em C nem em C ++, eles variam dependendo de compiladores e arquiteturas. Quando você precisar de consistência e previsibilidade, use a uint32_tfamília de inteiros de #include <stdint.h>.

  • Problemas de velocidade resolvidos. Todas as outras línguas estão de volta centenas por cento atrás, C & C ++ ganham novamente! Eles sempre fazem. A próxima melhoria será multithreading usando OpenMP: D


Olhando para a sua implementação Erlang. O tempo incluiu o arranque de toda a máquina virtual, executando o seu programa e parando a máquina virtual. Tenho certeza de que configurar e parar o Erlang vm leva algum tempo.

Se o tempo fosse feito dentro da própria máquina virtual erlang, os resultados seriam diferentes, pois nesse caso teríamos o tempo real apenas para o programa em questão. Caso contrário, acredito que o tempo total gasto pelo processo de iniciar e carregar o Erlang Vm, mais o de interrompê-lo (como você o coloca em seu programa), está incluído no tempo total que o método que você está usando para cronometrar o tempo. programa está saindo. Considere usar o próprio tempo do erlang que usamos quando queremos programar nossos programas dentro da própria máquina virtual timer:tc/1 or timer:tc/2 or timer:tc/3. Desta forma, os resultados do erlang irão excluir o tempo necessário para iniciar e parar / matar / parar a máquina virtual. Esse é o meu raciocínio aí, pense nisso e, em seguida, tente sua marca de novo.

Na verdade, sugiro que tentemos cronometrar o programa (para linguagens que têm um tempo de execução), dentro do tempo de execução dessas linguagens, a fim de obter um valor preciso. C, por exemplo, não tem nenhuma sobrecarga de iniciar e desligar um sistema em tempo de execução, como fazem Erlang, Python e Haskell (98% de certeza disso - estou em correção). Então (com base nesse raciocínio) eu concluo dizendo que este benchmark não era preciso / justo o suficiente para linguagens rodando em cima de um sistema de tempo de execução. Vamos fazer isso de novo com essas mudanças.

EDIT: além disso, mesmo se todas as linguagens tivessem sistemas de tempo de execução, a sobrecarga de iniciar cada um e pará-lo seria diferente. Então eu sugiro que o tempo de dentro dos sistemas de tempo de execução (para os idiomas para os quais isso se aplica). O Erlang VM é conhecido por ter uma sobrecarga considerável no arranque!





erlang