Interpretando um benchmark em C, Clojure, Python, Ruby, Scala e outros [fechado]

91

aviso Legal

Eu sei que benchmarks artificiais são ruins. Eles podem mostrar resultados apenas para situações estreitas muito específicas. Não presumo que uma língua seja melhor que a outra por causa de algum banco estúpido. No entanto, eu me pergunto por que os resultados são tão diferentes. Por favor, veja minhas perguntas no final.

Descrição de benchmark matemático

A referência consiste em cálculos matemáticos simples para encontrar pares de números primos que diferem por 6 (os chamados primos sexy ). Por exemplo, primos sexy abaixo de 100 seriam:(5 11) (7 13) (11 17) (13 19) (17 23) (23 29) (31 37) (37 43) (41 47) (47 53) (53 59) (61 67) (67 73) (73 79) (83 89) (97 103)

Tabela de resultados

Na tabela: tempo de cálculo em segundos Executando: todos, exceto Factor, estavam em execução no VirtualBox (Debian instável amd64 convidado, host Windows 7 x64) CPU: AMD A4-3305M

  Sexy primes up to:        10k      20k      30k      100k               

  Bash                    58.00   200.00     [*1]      [*1]

  C                        0.20     0.65     1.42     15.00

  Clojure1.4               4.12     8.32    16.00    137.93

  Clojure1.4 (optimized)   0.95     1.82     2.30     16.00

  Factor                    n/a      n/a    15.00    180.00

  Python2.7                1.49     5.20    11.00       119     

  Ruby1.8                  5.10    18.32    40.48    377.00

  Ruby1.9.3                1.36     5.73    10.48    106.00

  Scala2.9.2               0.93     1.41     2.73     20.84

  Scala2.9.2 (optimized)   0.32     0.79     1.46     12.01

[* 1] - Tenho medo de imaginar quanto tempo vai demorar

Listagens de código

C:

int isprime(int x) {
  int i;
  for (i = 2; i < x; ++i)
    if (x%i == 0) return 0;
  return 1;
}

void findprimes(int m) {
  int i;
  for ( i = 11; i < m; ++i)
    if (isprime(i) && isprime(i-6))
      printf("%d %d\n", i-6, i);
}

main() {
    findprimes(10*1000);
}

Rubi:

def is_prime?(n)
  (2...n).all?{|m| n%m != 0 }
end

def sexy_primes(x)
  (9..x).map do |i|
    [i-6, i]
  end.select do |j|
    j.all?{|j| is_prime? j}
  end
end

a = Time.now
p sexy_primes(10*1000)
b = Time.now
puts "#{(b-a)*1000} mils"

Scala:

def isPrime(n: Int) =
  (2 until n) forall { n % _ != 0 }

def sexyPrimes(n: Int) = 
  (11 to n) map { i => List(i-6, i) } filter { _ forall(isPrime(_)) }

val a = System.currentTimeMillis()
println(sexyPrimes(100*1000))
val b = System.currentTimeMillis()
println((b-a).toString + " mils")

Escala otimizada isPrime(a mesma ideia da otimização Clojure):

import scala.annotation.tailrec

@tailrec // Not required, but will warn if optimization doesn't work
def isPrime(n: Int, i: Int = 2): Boolean = 
  if (i == n) true 
  else if (n % i != 0) isPrime(n, i + 1)
  else false

Clojure:

(defn is-prime? [n]
  (every? #(> (mod n %) 0)
    (range 2 n)))

(defn sexy-primes [m]
  (for [x (range 11 (inc m))
        :let [z (list (- x 6) x)]
        :when (every? #(is-prime? %) z)]
      z))

(let [a (System/currentTimeMillis)]
  (println (sexy-primes (* 10 1000)))
  (let [b (System/currentTimeMillis)]
    (println (- b a) "mils")))

Clojure otimizado is-prime?:

(defn ^:static is-prime? [^long n]
  (loop [i (long 2)] 
    (if (= (rem n i) 0)
      false
      (if (>= (inc i) n) true (recur (inc i))))))

Pitão

import time as time_

def is_prime(n):
  return all((n%j > 0) for j in xrange(2, n))

def primes_below(x):
  return [[j-6, j] for j in xrange(9, x+1) if is_prime(j) and is_prime(j-6)]

a = int(round(time_.time() * 1000))
print(primes_below(10*1000))
b = int(round(time_.time() * 1000))
print(str((b-a)) + " mils")

Fator

MEMO:: prime? ( n -- ? )
n 1 - 2 [a,b] [ n swap mod 0 > ] all? ;

MEMO: sexyprimes ( n n -- r r )
[a,b] [ prime? ] filter [ 6 + ] map [ prime? ] filter dup [ 6 - ] map ;

5 10 1000 * sexyprimes . .

Bash (zsh):

#!/usr/bin/zsh
function prime {
  for (( i = 2; i < $1; i++ )); do
    if [[ $[$1%i] == 0 ]]; then
      echo 1
      exit
    fi
  done
  echo 0
}

function sexy-primes {
  for (( i = 9; i <= $1; i++ )); do
    j=$[i-6]
    if [[ $(prime $i) == 0 && $(prime $j) == 0 ]]; then
      echo $j $i
    fi
  done
}

sexy-primes 10000

Questões

  1. Por que o Scala é tão rápido? É por causa da digitação estática ? Ou está apenas usando o JVM de forma muito eficiente?
  2. Por que essa diferença tão grande entre Ruby e Python? Achei que esses dois não eram totalmente diferentes. Talvez meu código esteja errado. Por favor me esclareça! Obrigado. UPD Sim, foi um erro no meu código. Python e Ruby 1.9 são praticamente iguais.
  3. Salto realmente impressionante na produtividade entre as versões Ruby.
  4. Posso otimizar o código Clojure adicionando declarações de tipo? Isso vai ajudar?
defhlt
fonte
6
@mgilson na verdade até, sqrt(n)mas isso pode levar algum tempo para ser computado. Além disso, seu código C imprime os primos à medida que os encontra, enquanto suas outras linguagens os computam em listas e, em seguida, os imprime. Embora C seja surpreendentemente o mais rápido, você pode conseguir obtê-lo mais rápido.
Russ
2
(E, claro, o Sieve de Eratóstenes .. mas este micro benchmark é basicamente um teste de estresse de iteração e operações matemáticas. No entanto, eles ainda não são "justos", pois em alguns são mais preguiçosos.)
2
Acabei de rodar minha versão Go e sua versão C (que são muito parecidas) e praticamente obtive a mesma velocidade em ambas. Eu só tentei a versão 100k: C: 2.723s Go: 2.743s.
Sebastián Grignoli
3
Você não precisa calcular sqrtpara esta verificação. Você pode calcular o quadrado de icomo infor (i = 2; i * i <= x; ++i) ...
ivant
3
Eu sugiro que você anote o Scala otimizado isPrimecom @tailrec, para garantir que está usando a recursão de cauda. É fácil erroneamente fazer algo que evita a recursão da cauda e esta anotação deve avisá-lo se isso acontecer.
Daniel C. Sobral

Respostas:

30

Respostas gerais:

  1. A tipagem estática do Scala está ajudando bastante aqui - isso significa que ele usa a JVM de maneira bastante eficiente, sem muito esforço extra.
  2. Não tenho certeza da diferença Ruby / Python, mas suspeito que (2...n).all?a função is-prime?provavelmente seja muito bem otimizada em Ruby (EDITAR: parece que é esse o caso, veja a resposta de Julian para mais detalhes ...)
  3. Ruby 1.9.3 é muito melhor otimizado
  4. O código Clojure certamente pode ser muito acelerado! Embora o Clojure seja dinâmico por padrão, você pode usar dicas de tipo, matemática primitiva etc. para chegar perto da velocidade do Scala / Java puro em muitos casos, quando necessário.

A otimização mais importante no código Clojure seria usar matemática primitiva digitada is-prime?, algo como:

(set! *unchecked-math* true) ;; at top of file to avoid using BigIntegers

(defn ^:static is-prime? [^long n]
  (loop [i (long 2)] 
    (if (zero? (mod n i))
      false
      (if (>= (inc i) n) true (recur (inc i))))))

Com essa melhoria, eu faço o Clojure completar 10k em 0,635 segundos (ou seja, o segundo mais rápido da sua lista, batendo o Scala)

PS, note que você tem código de impressão dentro de seu benchmark em alguns casos - não é uma boa ideia, pois isso distorce os resultados, especialmente se usar uma função como printpela primeira vez causa a inicialização de subsistemas IO ou algo parecido!

Mikera
fonte
2
Não acho que a parte sobre Ruby e Python seja necessariamente verdadeira, mas, caso contrário, +1 ..
A digitação não mostrou nenhum resultado estável mensurável, mas seu novo is-prime?mostra uma melhoria 2x. ;)
defhlt
isso não poderia ser feito mais rápido se houvesse um mod não verificado?
Hendekagon
1
@Hendekagon - provavelmente! Não tenho certeza de quão bem isso é otimizado pelo compilador Clojure atual, provavelmente há espaço para melhorias. Clojure 1.4 definitivamente ajuda muito em geral para esse tipo de coisa, 1.5 provavelmente será ainda melhor.
Mikera
1
(zero? (mod n i))deve ser mais rápido do que(= (mod n i) 0)
Jonas
23

Esta é uma versão rápida do Clojure, usando os mesmos algoritmos básicos:

(set! *unchecked-math* true)

(defn is-prime? [^long n]
  (loop [i 2]
    (if (zero? (unchecked-remainder-int n i))
      false
      (if (>= (inc i) n)
        true
        (recur (inc i))))))

(defn sexy-primes [m]
  (for [x (range 11 (inc m))
        :when (and (is-prime? x) (is-prime? (- x 6)))]
    [(- x 6) x]))

Ele roda cerca de 20x mais rápido do que o original na minha máquina. E aqui está uma versão que aproveita a nova biblioteca de redutores em 1.5 (requer Java 7 ou JSR 166):

(require '[clojure.core.reducers :as r]) ;'

(defn sexy-primes [m]
  (->> (vec (range 11 (inc m)))
       (r/filter #(and (is-prime? %) (is-prime? (- % 6))))
       (r/map #(list (- % 6) %))
       (r/fold (fn ([] []) ([a b] (into a b))) conj)))

Ele é executado cerca de 40 vezes mais rápido do que o original. Na minha máquina, isso dá 100k em 1,5 segundos.

Justin Kramer
fonte
2
Usando unchecked-remainder-intou apenas em remvez de modjunto com os resultados de tipagem estática para aumentar o desempenho de 4x Agradável!
defhlt
22

Eu vou responder apenas # 2, já que é o único que eu tenho qualquer coisa remotamente inteligente para dizer, mas para o seu código Python, você está criando uma lista intermediária is_prime, enquanto você está usando .mapem sua allem Ruby que é apenas iterando.

Se você mudar is_primepara:

def is_prime(n):
    return all((n%j > 0) for j in range(2, n))

eles estão no mesmo nível.

Eu poderia otimizar o Python ainda mais, mas meu Ruby não é bom o suficiente para saber quando eu dei mais uma vantagem (por exemplo, usando xrangefaz Python ganhar na minha máquina, mas não me lembro se o intervalo de Ruby que você usou cria um intervalo inteiro na memória ou não).

EDIT: Sem ser muito bobo, fazendo o código Python parecer:

import time

def is_prime(n):
    return all(n % j for j in xrange(2, n))

def primes_below(x):
    return [(j-6, j) for j in xrange(9, x + 1) if is_prime(j) and is_prime(j-6)]

a = int(round(time.time() * 1000))
print(primes_below(10*1000))
b = int(round(time.time() * 1000))
print(str((b-a)) + " mils")

o que não muda muito mais, coloca-o em 1.5s para mim e, por ser muito bobo, executá-lo com PyPy o coloca em 0,3s para 10K e 21s para 100K.

Julian
fonte
1
O gerador faz uma grande diferença aqui, pois permite que a função salve o primeiro False(boa pegada).
mgilson
Estou realmente ansioso para eles ficarem entorpecidos no PyPy ... Isso vai ser incrível.
mgilson
Você poderia publicar minha resposta em PyPy? Estou curioso para saber o quão mais rápido isso seria.
steveha
1
Você está totalmente certo sobre a iteração e xrange! Eu consertei e agora Python e Ruby mostram resultados iguais.
defhlt
1
@steveha Farei isso apenas se você prometer agora sair e baixar o PyPy você mesmo :)! pypy.org/download.html tem binários para todos os sistemas operacionais comuns, e seu gerenciador de pacotes, sem dúvida, os tem. De qualquer forma, quanto ao seu benchmark, com uma lru_cacheimplementação aleatória para 2.7 encontrada no AS, 100K roda em 2.3s.
Juliano
16

Você pode tornar o Scala muito mais rápido, modificando seu isPrimemétodo para

  def isPrime(n: Int, i: Int = 2): Boolean = 
    if (i == n) true 
    else if (n % i != 0) isPrime(n, i + 1)
    else false

Não é tão conciso, mas o programa funciona em 40% do tempo!

Cortamos Rangeos Functionobjetos supérfluos e anônimos , o compilador Scala reconhece a recursão final e a transforma em um loop while, que a JVM pode transformar em um código de máquina mais ou menos ideal, por isso não deve estar muito longe do C versão.

Veja também: Como otimizar para compreensões e loops no Scala?

Luigi Plinge
fonte
2
Melhoria 2x. E link legal!
defhlt
aliás, este corpo de método é idêntico ao i == n || n % i != 0 && isPrime(n, i + 1), que é mais curto, embora um pouco mais difícil de ler
Luigi Plinge
1
Você deve ter adicionado a @tailrecanotação, para garantir que fará essa otimização.
Daniel C. Sobral
8

Aqui está minha versão do scala em paralelo e não paralelo, apenas por diversão: (Na minha computação dual core, a versão paralela leva 335ms enquanto a versão não paralela leva 655ms)

object SexyPrimes {
  def isPrime(n: Int): Boolean = 
    (2 to math.sqrt(n).toInt).forall{ n%_ != 0 }

  def isSexyPrime(n: Int): Boolean = isPrime(n) && isPrime(n-6)

  def findPrimesPar(n: Int) {
    for(k <- (11 to n).par)
      if(isSexyPrime(k)) printf("%d %d\n",k-6,k)
  }

  def findPrimes(n: Int) {
    for(k <- 11 to n)
      if(isSexyPrime(k)) printf("%d %d\n",k-6,k)
  }


  def timeOf(call : =>Unit) {
    val start = System.currentTimeMillis
    call
    val end = System.currentTimeMillis
    println((end-start)+" mils")
  }

  def main(args: Array[String]) {
    timeOf(findPrimes(100*1000))
    println("------------------------")
    timeOf(findPrimesPar(100*1000))
  }
}

EDITAR: De acordo com Emil H a sugestão de , mudei meu código para evitar os efeitos de IO e aquecimento jvm:

O resultado mostra em meu cálculo:

List (3432, 1934, 3261, 1716, 3229, 1654, 3214, 1700)

object SexyPrimes {
  def isPrime(n: Int): Boolean = 
    (2 to math.sqrt(n).toInt).forall{ n%_ != 0 }

  def isSexyPrime(n: Int): Boolean = isPrime(n) && isPrime(n-6)

  def findPrimesPar(n: Int) {
    for(k <- (11 to n).par)
      if(isSexyPrime(k)) ()//printf("%d %d\n",k-6,k)
  }

  def findPrimes(n: Int) {
    for(k <- 11 to n)
      if(isSexyPrime(k)) ()//printf("%d %d\n",k-6,k)
  }


  def timeOf(call : =>Unit): Long = {
    val start = System.currentTimeMillis
    call
    val end = System.currentTimeMillis
    end - start 
  }

  def main(args: Array[String]) {
    val xs = timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
             timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
             timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
             timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::Nil
    println(xs)
  }
}
Eastsun
fonte
1
O código é afetado pelo aquecimento jvm? Por exemplo, isSexyPrimepode ser (mais) otimizado quando chamado de findPrimesPare não tanto quando chamado defindPrimes
Emil H
@EmilH Muito justo. Eu mudei meu código para evitar o efeito do aquecimento io e jvm.
Eastsun
Apenas subir até sqrt (n) é uma boa otimização, mas agora você está comparando um algoritmo diferente.
Luigi Plinge
7

Não importa os benchmarks; o problema me interessou e fiz alguns ajustes rápidos. Isso usa o lru_cachedecorador, que memoriza uma função; então, quando ligamos is_prime(i-6), basicamente recebemos aquele cheque principal de graça. Essa mudança reduz o trabalho aproximadamente pela metade. Além disso, podemos fazer as range()chamadas passarem apenas pelos números ímpares, reduzindo o trabalho pela metade novamente.

http://en.wikipedia.org/wiki/Memoization

http://docs.python.org/dev/library/functools.html

Isso requer Python 3.2 ou mais recente para obter lru_cache, mas pode funcionar com um Python mais antigo se você instalar uma receita Python que forneça lru_cache. Se você estiver usando Python 2.x, você realmente deve usar em xrange()vez de range().

http://code.activestate.com/recipes/577479-simple-caching-decorator/

from functools import lru_cache
import time as time_

@lru_cache()
def is_prime(n):
    return n%2 and all(n%i for i in range(3, n, 2))

def primes_below(x):
    return [(i-6, i) for i in range(9, x+1, 2) if is_prime(i) and is_prime(i-6)]

correct100 = [(5, 11), (7, 13), (11, 17), (13, 19), (17, 23), (23, 29),
        (31, 37), (37, 43), (41, 47), (47, 53), (53, 59), (61, 67), (67, 73),
        (73, 79), (83, 89)]
assert(primes_below(100) == correct100)

a = time_.time()
print(primes_below(30*1000))
b = time_.time()

elapsed = b - a
print("{} msec".format(round(elapsed * 1000)))

O texto acima demorou muito pouco para ser editado. Decidi dar um passo adiante e fazer o teste dos primos tentar apenas os divisores primos, e apenas até a raiz quadrada do número que está sendo testado. A maneira como fiz isso só funciona se você verificar os números em ordem, de modo que pode acumular todos os primos à medida que avança; mas esse problema já era verificar os números em ordem, então tudo bem.

No meu laptop (nada de especial; o processador é um AMD Turion II "K625" de 1,5 GHz) esta versão produziu uma resposta para 100K em menos de 8 segundos.

from functools import lru_cache
import math
import time as time_

known_primes = set([2, 3, 5, 7])

@lru_cache(maxsize=128)
def is_prime(n):
    last = math.ceil(math.sqrt(n))
    flag = n%2 and all(n%x for x in known_primes if x <= last)
    if flag:
        known_primes.add(n)
    return flag

def primes_below(x):
    return [(i-6, i) for i in range(9, x+1, 2) if is_prime(i) and is_prime(i-6)]

correct100 = [(5, 11), (7, 13), (11, 17), (13, 19), (17, 23), (23, 29),
        (31, 37), (37, 43), (41, 47), (47, 53), (53, 59), (61, 67), (67, 73),
        (73, 79), (83, 89)]
assert(primes_below(100) == correct100)

a = time_.time()
print(primes_below(100*1000))
b = time_.time()

elapsed = b - a
print("{} msec".format(round(elapsed * 1000)))

O código acima é muito fácil de escrever em Python, Ruby, etc., mas seria mais problemático em C.

Você não pode comparar os números desta versão com os números das outras versões sem reescrever as outras para usar truques semelhantes. Não estou tentando provar nada aqui; Achei que o problema era divertido e queria ver que tipo de melhorias fáceis de desempenho eu poderia obter.

Steveha
fonte
lru_cacheé definitivamente bacana. Para certas classes de problemas, como a geração de números de Fibonacci sucessivos, pode aumentar a velocidade apenas adicionando aquele decorador de uma linha na função! Aqui está um link para uma palestra de Raymond Hettinger que cobre lru_cachecerca de 26 minutos em. Blip.tv/pycon-us-videos-2009-2010-2011/…
steveha
3
Ao usar lru_cache, você realmente usa outro algoritmo em vez do código bruto. Portanto, o desempenho está relacionado ao algoritmo, mas não à linguagem em si.
Eastsun
1
@Eastsun - Não entendo o que você quer dizer. lru_cacheevita repetir um cálculo que já foi feito recentemente e só; Eu não vejo como isso é "realmente usar outro algoritmo". E Python sofre de ser lento, mas se beneficia de ter coisas legais como lru_cache; Não vejo nada de errado em usar as partes benéficas de uma linguagem. E eu disse que não se deve comparar o tempo de execução da minha resposta com as outras linguagens sem fazer alterações semelhantes nas outras. Então, eu não entendo o que você quer dizer.
steveha
@Eastsun está certo, mas por outro lado, a conveniência de uma linguagem de nível superior deve ser permitida, a menos que restrições adicionais sejam fornecidas. lru_cache irá sacrificar memória para velocidade e ajusta a complexidade algorítmica.
Matt Joiner
2
se você usar outro algoritmo, tente o Sieve de Eratóstenes. A versão Python produziu uma resposta de 100K em menos de 0.03segundos ( 30ms) .
jfs
7

Não se esqueça do Fortran! (Principalmente brincando, mas eu esperaria um desempenho semelhante ao C). As declarações com pontos de exclamação são opcionais, mas são de bom estilo. ( !é um caractere de comentário no fortran 90)

logical function isprime(n)
IMPLICIT NONE !
integer :: n,i
do i=2,n
   if(mod(n,i).eq.0)) return .false.
enddo
return .true.
end

subroutine findprimes(m)
IMPLICIT NONE !
integer :: m,i
logical, external :: isprime

do i=11,m
   if(isprime(i) .and. isprime(i-6))then
      write(*,*) i-6,i
   endif
enddo
end

program main
findprimes(10*1000)
end
mgilson
fonte
6

Não pude resistir a fazer algumas das otimizações mais óbvias para a versão C que fez o teste de 100k agora levar 0.3s na minha máquina (5 vezes mais rápido do que a versão C em questão, ambas compiladas com MSVC 2010 / Ox) .

int isprime( int x )
{
    int i, n;
    for( i = 3, n = x >> 1; i <= n; i += 2 )
        if( x % i == 0 )
            return 0;
    return 1;
}

void findprimes( int m )
{
    int i, s = 3; // s is bitmask of primes in last 3 odd numbers
    for( i = 11; i < m; i += 2, s >>= 1 ) {
        if( isprime( i ) ) {
            if( s & 1 )
                printf( "%d %d\n", i - 6, i );
            s |= 1 << 3;
        }
    }
}

main() {
    findprimes( 10 * 1000 );
}

Aqui está a implementação idêntica em Java:

public class prime
{
    private static boolean isprime( final int x )
    {
        for( int i = 3, n = x >> 1; i <= n; i += 2 )
            if( x % i == 0 )
                return false;
        return true;
    }

    private static void findprimes( final int m )
    {
        int s = 3; // s is bitmask of primes in last 3 odd numbers
        for( int i = 11; i < m; i += 2, s >>= 1 ) {
            if( isprime( i ) ) {
                if( ( s & 1 ) != 0 )
                    print( i );
                s |= 1 << 3;
            }
        }
    }

    private static void print( int i )
    {
        System.out.println( ( i - 6 ) + " " + i );
    }

    public static void main( String[] args )
    {
        // findprimes( 300 * 1000 ); // for some JIT training
        long time = System.nanoTime();
        findprimes( 10 * 1000 );
        time = System.nanoTime() - time;
        System.err.println( "time: " + ( time / 10000 ) / 100.0 + "ms" );
    }
}

Com o Java 1.7.0_04, ele funciona quase tão rápido quanto a versão C. Cliente ou servidor VM não mostra muita diferença, exceto que o treinamento JIT parece ajudar o servidor VM um pouco (~ 3%) enquanto quase não tem efeito com o cliente VM. A saída em Java parece ser mais lenta do que em C. Se a saída for substituída por um contador estático em ambas as versões, a versão Java é executada um pouco mais rápido do que a versão C.

Estes são os meus tempos para a corrida de 100k:

  • 319ms C compilado com / Ox e saída para> NIL:
  • 312ms C compilado com / Ox e contador estático
  • VM cliente Java de 324ms com saída para> NIL:
  • 299ms Java cliente VM com contador estático

e a execução de 1M (16386 resultados):

  • 24.95s C compilado com / Ox e contador estático
  • 25.08s Java cliente VM com contador estático
  • 24.86s Java servidor VM com contador estático

Embora isso não responda realmente às suas perguntas, mostra que pequenos ajustes podem ter um impacto notável no desempenho. Portanto, para realmente comparar as linguagens, você deve tentar evitar todas as diferenças algorítmicas tanto quanto possível.

Também dá uma dica por que Scala parece bastante rápido. Ele é executado no Java VM e, portanto, se beneficia de seu desempenho impressionante.

x4u
fonte
1
É mais rápido ir para sqrt (x) em vez de x >> 1 para a função de verificação principal.
Eve Freeman
4

No Scala, tente usar Tuple2 em vez de List, deve ser mais rápido. Apenas remova a palavra 'Lista', pois (x, y) é uma Tupla2.

Tuple2 é especializado para Int, Long e Double, o que significa que não terá que encaixotar / desencaixotar esses tipos de dados brutos. Fonte Tuple2 . A lista não é especializada. Fonte da lista .

Tomas Lazaro
fonte
Então você não pode invocá forall-lo. Eu também pensei que este poderia não ser o código mais eficiente (mais porque uma grande coleção estrita é criada para grandes em nvez de apenas usar uma visualização), mas certamente é curto + elegante, e fiquei surpreso com o quão bem ele funcionou apesar de usar um muito estilo funcional.
0__
Você está certo, pensei que 'para todos' estava lá. Ainda assim, deve haver uma grande melhoria em relação a List e não seria tão ruim ter essas 2 chamadas.
Tomas Lazaro
2
é de fato mais rápido, com def sexyPrimes(n: Int) = (11 to n).map(i => (i-6, i)).filter({ case (i, j) => isPrime(i) && isPrime(j) })ele é cerca de 60% mais rápido aqui, então deve bater o código C :)
0__
Hmm, eu só consigo um aumento de desempenho de 4 ou 5%
Luigi Plinge
1
Acho collectsubstancialmente mais lento. Mais rápido é se você fizer o filtro primeiro e depois mapear. withFilteré um pouco mais rápido porque não cria coleções intermediárias. (11 to n) withFilter (i => isPrime(i - 6) && isPrime(i)) map (i => (i - 6, i))
Luigi Plinge
4

Este é o código para a versão Go (golang.org):

package main

import (
    "fmt"
)


func main(){
    findprimes(10*1000)
}

func isprime(x int) bool {
    for i := 2; i < x; i++ {
        if x%i == 0 {
            return false
        }
    }
    return true
}

func findprimes(m int){
    for i := 11; i < m; i++ {
        if isprime(i) && isprime(i-6) {
            fmt.Printf("%d %d\n", i-6, i)
        }
    }
}

Funcionou tão rápido quanto a versão C.

Usando um Asus u81a Intel Core 2 Duo T6500 2.1 GHz, cache L2 de 2 MB, FSB de 800 MHz. 4 GB de RAM

A versão 100k: C: 2.723s Go: 2.743s

Com 1000000 (1 milhão em vez de 100 K): C: 3m35.458s Go: 3m36.259s

Mas acho que seria justo usar os recursos de multithreading integrados do Go e comparar essa versão com a versão C normal (sem multithreading), só porque é quase muito fácil fazer multithreading com Go.

Atualização: fiz uma versão paralela usando Goroutines no Go:

package main

import (
  "fmt"
  "runtime"
)

func main(){
    runtime.GOMAXPROCS(4)
    printer := make(chan string)
    printer2 := make(chan string)
    printer3 := make(chan string)
    printer4 := make(chan string)
    finished := make(chan int)

    var buffer, buffer2, buffer3 string

    running := 4
    go findprimes(11, 30000, printer, finished)
    go findprimes(30001, 60000, printer2, finished)
    go findprimes(60001, 85000, printer3, finished)
    go findprimes(85001, 100000, printer4, finished)

    for {
      select {
        case i := <-printer:
          // batch of sexy primes received from printer channel 1, print them
          fmt.Printf(i)
        case i := <-printer2:
          // sexy prime list received from channel, store it
          buffer = i
        case i := <-printer3:
          // sexy prime list received from channel, store it
          buffer2 = i
        case i := <-printer4:
          // sexy prime list received from channel, store it
          buffer3 = i
        case <-finished:
          running--
          if running == 0 {
              // all goroutines ended
              // dump buffer to stdout
              fmt.Printf(buffer)
              fmt.Printf(buffer2)
              fmt.Printf(buffer3)
              return
          }
      }
    }
}

func isprime(x int) bool {
    for i := 2; i < x; i++ {
        if x%i == 0 {
            return false
        }
    }
    return true
}

func findprimes(from int, to int, printer chan string, finished chan int){
    str := ""
    for i := from; i <= to; i++ {
        if isprime(i) && isprime(i-6) {
            str = str + fmt.Sprintf("%d %d\n", i-6, i)
      }
    }
    printer <- str
    //fmt.Printf("Finished %d to %d\n", from, to)
    finished <- 1
}

A versão paralelizada utilizou em média 2,743 segundos, exatamente o mesmo tempo que a versão regular utilizou.

A versão paralelizada foi concluída em 1.706 segundos. Ele usava menos de 1,5 Mb de RAM.

Uma coisa estranha: meu dual core kubuntu 64bit nunca atingiu o pico em ambos os núcleos. Parecia que Go estava usando apenas um núcleo. Corrigido com uma chamada pararuntime.GOMAXPROCS(4)

Atualização: Executei a versão paralelizada até 1M de números. Um dos núcleos da Minha CPU estava 100% o tempo todo, enquanto o outro não era usado (ímpar). Demorou um minuto inteiro a mais do que as versões C e Go regulares. :(

Com 1000000 (1 milhão em vez de 100 K):

C: 3m35.458s Go: 3m36.259s Go using goroutines:3m27.137s2m16.125s

A versão 100k:

C: 2.723s Go: 2.743s Go using goroutines: 1.706s

Sebastián Grignoli
fonte
Quantos núcleos você usou btw?
om-nom-nom
2
Eu tenho um Asus u81a Intel Core 2 Duo T6500 2.1 GHz, cache L2 de 2 MB, FSB de 800 MHz. 4 GB de RAM
Sebastián Grignoli
Você realmente compilou a versão C com otimizações habilitadas? O compilador Go padrão não é embutido e geralmente sofrerá um impacto maciço de desempenho em relação ao C otimizado nesses tipos de comparações. Adicione -O3ou melhor.
Matt Joiner
Acabei de fazer, não antes, e a versão 100K levou o mesmo tempo com ou sem -O3
Sebastián Grignoli
A mesma coisa para a versão 1M. Talvez essas operações em particular (estamos testando um subconjunto muito pequeno) sejam bem otimizadas por padrão.
Sebastián Grignoli
4

Só por diversão, aqui está uma versão paralela de Ruby.

require 'benchmark'

num = ARGV[0].to_i

def is_prime?(n)
  (2...n).all?{|m| n%m != 0 }
end

def sexy_primes_default(x)
    (9..x).map do |i|
        [i-6, i]
    end.select do |j|
        j.all?{|j| is_prime? j}
    end
end

def sexy_primes_threads(x)
    partition = (9..x).map do |i|
        [i-6, i]
    end.group_by do |x|
        x[0].to_s[-1]
    end
    threads = Array.new
    partition.each_key do |k|
       threads << Thread.new do
            partition[k].select do |j|
                j.all?{|j| is_prime? j}
            end
        end
    end
    threads.each {|t| t.join}
    threads.map{|t| t.value}.reject{|x| x.empty?}
end

puts "Running up to num #{num}"

Benchmark.bm(10) do |x|
    x.report("default") {a = sexy_primes_default(num)}
    x.report("threads") {a = sexy_primes_threads(num)}
end

No meu MacBook Air Core i5 de 1,8 GHz, os resultados de desempenho são:

# Ruby 1.9.3
$ ./sexyprimes.rb 100000
Running up to num 100000
                 user     system      total        real
default     68.840000   0.060000  68.900000 ( 68.922703)
threads     71.730000   0.090000  71.820000 ( 71.847346)

# JRuby 1.6.7.2 on JVM 1.7.0_05
$ jruby --1.9 --server sexyprimes.rb 100000
Running up to num 100000
                user     system      total        real
default    56.709000   0.000000  56.709000 ( 56.708000)
threads    36.396000   0.000000  36.396000 ( 36.396000)

# JRuby 1.7.0.preview1 on JVM 1.7.0_05
$ jruby --server sexyprimes.rb 100000
Running up to num 100000
             user     system      total        real
default     52.640000   0.270000  52.910000 ( 51.393000)
threads    105.700000   0.290000 105.990000 ( 30.298000)

Parece que o JIT da JVM está dando ao Ruby um bom aumento de desempenho no caso padrão, enquanto o multithreading verdadeiro ajuda o JRuby a executar 50% mais rápido no caso de encadeamento. O que é mais interessante é que o JRuby 1.7 melhora a pontuação do JRuby 1.6 em 17%!

Georgios Gousios
fonte
3

Com base na resposta de x4u , escrevi uma versão de scala usando recursão e a aprimorei indo apenas para sqrt em vez de x / 2 para a função de verificação principal. Obtenho ~ 250ms para 100k e ~ 600ms para 1M. Eu fui em frente e fui para 10 milhões em ~ 6s.

import scala.annotation.tailrec

var count = 0;
def print(i:Int) = {
  println((i - 6) + " " + i)
  count += 1
}

@tailrec def isPrime(n:Int, i:Int = 3):Boolean = {
  if(n % i == 0) return false;
  else if(i * i > n) return true;
  else isPrime(n = n, i = i + 2)
}      

@tailrec def findPrimes(max:Int, bitMask:Int = 3, i:Int = 11):Unit = {
  if (isPrime(i)) {
    if((bitMask & 1) != 0) print(i)
    if(i + 2 < max) findPrimes(max = max, bitMask = (bitMask | (1 << 3)) >> 1, i = i + 2)
  } else if(i + 2 < max) {
    findPrimes(max = max, bitMask = bitMask >> 1, i = i + 2)
  }
}

val a = System.currentTimeMillis()
findPrimes(max=10000000)
println(count)
val b = System.currentTimeMillis()
println((b - a).toString + " mils")

Também voltei e escrevi uma versão do CoffeeScript (V8 JavaScript), que obtém ~ 15ms para 100k, 250ms para 1M e 6s para 10M, usando um contador (ignorando E / S). Se eu ligar a saída, leva ~ 150ms para 100k, 1s para 1M e 12s para 10M. Não foi possível usar recursão de cauda aqui, infelizmente, então tive que convertê-la de volta em loops.

count = 0;
print = (i) ->
  console.log("#{i - 6} #{i}")
  count += 1
  return

isPrime = (n) ->
  i = 3
  while i * i < n
    if n % i == 0
      return false
    i += 2
  return true

findPrimes = (max) ->
  bitMask = 3
  for i in [11..max] by 2
    prime = isPrime(i)
    if prime
      if (bitMask & 1) != 0
        print(i)
      bitMask |= (1 << 3)
    bitMask >>= 1
  return

a = new Date()
findPrimes(1000000)
console.log(count)
b = new Date()
console.log((b - a) + " ms")
Eve Freeman
fonte
2

A resposta à sua pergunta nº 1 é que sim, a JVM é incrivelmente rápida e sim a digitação estática ajuda.

A JVM deve ser mais rápida do que C a longo prazo, possivelmente ainda mais rápida do que a linguagem assembly "Normal" - Claro, você sempre pode otimizar manualmente o assembly para vencer qualquer coisa, fazendo o perfil de tempo de execução manual e criando uma versão separada para cada CPU, você apenas tem que ser incrivelmente bom e qualificado.

As razões para a velocidade do Java são:

A JVM pode analisar seu código enquanto é executado e otimizá-lo manualmente - por exemplo, se você tivesse um método que pudesse ser analisado estaticamente no momento da compilação para ser uma função verdadeira e a JVM percebesse que você costumava chamá-lo com a mesma parâmetros, ele PODERIA realmente eliminar a chamada completamente e apenas injetar os resultados da última chamada (não tenho certeza se o Java realmente faz isso exatamente, mas ele faz muitas coisas assim).

Devido à tipagem estática, a JVM pode saber muito sobre o seu código em tempo de compilação, o que permite que ela pré-otimize várias coisas. Também permite que o compilador otimize cada classe individualmente, sem conhecimento de como outra classe está planejando usá-la. Além disso, o Java não tem ponteiros arbitrários para a localização da memória, ele SABE quais valores na memória podem e não podem ser alterados e pode otimizar de acordo.

A alocação de heap é MUITO mais eficiente do que C, a alocação de heap do Java é mais parecida com a alocação de pilha do C em velocidade - ainda mais versátil. Muito tempo foi gasto nos diferentes algroítimos usados ​​aqui, é uma arte - por exemplo, todos os objetos com uma vida útil curta (como as variáveis ​​da pilha de C) são alocados em um local livre "conhecido" (sem busca por um local livre com espaço suficiente) e são todos liberados juntos em uma única etapa (como uma pilha pop).

A JVM pode conhecer peculiaridades sobre a arquitetura de sua CPU e gerar código de máquina especificamente para uma determinada CPU.

A JVM pode acelerar seu código muito depois de você o enviar. Assim como mover um programa para uma nova CPU pode acelerá-lo, movê-lo para uma nova versão da JVM também pode fornecer desempenhos de grande velocidade planejados para CPUs que nem existiam quando você inicialmente compilou seu código, algo c fisicamente não pode fazer sem um recomiple.

A propósito, a maior parte da má reputação para a velocidade do java vem do longo tempo de inicialização para carregar o JVM (algum dia alguém irá construir o JVM no sistema operacional e isso irá embora!) E o fato de que muitos desenvolvedores são realmente ruins em escrever Código GUI (especialmente encadeado) que fazia com que as GUIs Java muitas vezes parassem de responder e apresentassem falhas. Linguagens simples de usar como Java e VB têm suas falhas amplificadas pelo fato de que as capacidades do programador médio tendem a ser menores do que as linguagens mais complicadas.

Bill K
fonte
Dizer que a alocação de heap da JVM é muito mais eficiente do que C não faz sentido, já que a JVM é escrita em C ++.
Daniel C. Sobral
5
A linguagem @ DanielC.Sobral não é tão importante quanto a implementação - o código de implementação "Heap" do Java não é nada como o C. O Java é um sistema substituível de vários estágios altamente otimizável para vários alvos com muitos homens-anos de esforço em pesquisa, incluindo técnicas de ponta que estão sendo desenvolvidas hoje. C usa um heap - uma estrutura de dados simples desenvolvida há muito tempo. O sistema Java é impossível de implementar para C, dado que C permite ponteiros, então ele nunca pode garantir movimentos "seguros" de blocos de memória alocados arbitrariamente sem alterações de linguagem (tornando-o não mais C)
Bill K
A segurança é irrelevante - você não afirmou que era mais seguro , mas sim mais eficiente . Além disso, sua descrição no comentário de como a "pilha" C funciona não tem relação com a realidade.
Daniel C. Sobral
Você deve ter entendido mal o meu significado de "Seguro" - Java é capaz de mover um bloco arbitrário de memória a qualquer momento porque sabe que pode, C é incapaz de otimizar o revestimento de memória porque pode haver um ponteiro que pode fazer referência a ele. Além disso, o heap AC é geralmente implementado como um heap que é uma estrutura de dados. C ++ heaps costumavam ser implementados com estruturas de heap como o C era (daí o nome, "Heap"). Não fiz check-in em C ++ por alguns anos, então isso pode não ser mais verdade, mas ainda é limitado por não ser capaz de reorganize pequenos pedaços de memória alocada do usuário à vontade.
Bill K