Interpretar un punto de referencia en C, Clojure, Python, Ruby, Scala y otros
benchmarking (13)
¡No olvides Fortran! (Bromeando en su mayoría, pero esperaría un rendimiento similar a C). Las declaraciones con signos de exclamación son opcionales, pero de buen estilo. ( ! es un personaje de comentario en 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
Renuncia
Sé que los puntos de referencia artificiales son malvados. Pueden mostrar resultados solo para situaciones angostas muy específicas. No supongo que un idioma es mejor que el otro debido a algún banco estúpido. Sin embargo, me pregunto por qué los resultados son muy diferentes. Por favor mira mis preguntas en la parte inferior.
Descripción de referencia de matemáticas
El punto de referencia son los cálculos matemáticos simples para encontrar pares de números primos que difieren por 6 (llamados primos sexys ) Por ejemplo, primos sexys por debajo de 100 serían: (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)
Tabla de resultados
En la tabla: tiempo de cálculo en segundos En ejecución: todos excepto Factor se estaba ejecutando en VirtualBox (Debian host inestable amd64, host de 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] - Tengo miedo de imaginar cuánto tiempo tomará
Listado de códigos
DO:
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);
}
Rubí:
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")
Scala optó por isPrime (la misma idea que en la optimización 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 optimizado 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ón
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")
Factor
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
Preguntas
- ¿Por qué Scala es tan rápido? ¿Es por tipeo estático ? ¿O solo está usando JVM de manera muy eficiente?
-
¿Por qué tanta diferencia entre Ruby y Python?Pensé que estos dos no son algo totalmente diferentes.Tal vez mi código es incorrecto.¡Por favor iluminame!Gracias.UPD Sí, eso fue un error en mi código. Python y Ruby 1.9 son bastante iguales. - Incremento de productividad realmente impresionante entre las versiones de Ruby.
- ¿Puedo optimizar el código de Clojure agregando declaraciones de tipo? ¿Ayudará?
Aquí está el código para la versión 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)
}
}
}
Funcionó tan rápido como la versión C.
Usando un Asus u81a Intel Core 2 Duo T6500 2.1GHz, 2MB L2 caché, 800MHz FSB. 4GB de RAM
La versión de 100k: C: 2.723s Go: 2.743s
Con 1000000 (1M en vez de 100K): C: 3m35.458s Go: 3m36.259s
Pero creo que sería justo utilizar las capacidades de subprocesamiento múltiple integradas de Go y comparar esa versión con la versión C normal (sin multithreading), simplemente porque es casi demasiado fácil hacer subprocesos múltiples con Go.
Actualización: hice una versión paralela usando Goroutines en 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
}
La versión paralelizada usó en promedio 2.743 segundos, exactamente el mismo tiempo que la versión normal utilizada.
La versión paralelizada se completó en 1.706 segundos. Usó menos de 1.5 Mb de RAM.
Una cosa extraña: mi kubuntu de doble núcleo de 64 bits nunca alcanzó su punto máximo en ambos núcleos. Parecía que Go usaba solo un núcleo. Solucionado con una llamada a runtime.GOMAXPROCS(4)
Actualización: ejecuté la versión paralela hasta números de 1M. Uno de mis núcleos de CPU estaba al 100% todo el tiempo, mientras que el otro no se utilizó en absoluto (impar). Tomó un minuto entero más que la C y las versiones normales de Go. :(
Con 1000000 (1M en vez de 100K):
C: 3m35.458s Go: 3m36.259s Go using goroutines: 3m27.137s 2m16.125s
La versión de 100k:
C: 2.723s Go: 2.743s Go using goroutines: 1.706s
Aquí está mi versión de Scala tanto en paralelo como sin paralelo, solo por diversión: (En mi cálculo dual core, la versión paralela toma 335ms mientras que la versión sin paralelo toma 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 acuerdo con la sugerencia de Emil H , he cambiado mi código para evitar los efectos del calentamiento de IO y jvm:
El resultado se muestra en mi cálculo:
Lista (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)
}
}
Aquí hay una versión rápida de Clojure, que usa los mismos 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]))
Funciona aproximadamente 20 veces más rápido que tu original en mi máquina. Y aquí hay una versión que aprovecha la nueva biblioteca de reductores en 1.5 (requiere Java 7 o 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)))
Esto corre aproximadamente 40 veces más rápido que tu original. En mi máquina, eso es 100k en 1.5 segundos.
En Scala prueba usar Tuple2 en lugar de List, debería ir más rápido. Solo elimine la palabra ''Lista'' ya que (x, y) es un Tuple2.
Tuple2 está especializado para Int, Long y Double, lo que significa que no tendrá que boxear / desempaquetar esos tipos de datos en bruto. Fuente Tuple2 . La lista no está especializada. Fuente de la lista
En base a la respuesta de x4u , escribí una versión de scala utilizando recursion, y la mejoré yendo solo al sqrt en lugar de a x / 2 para la función de verificación principal. Obtengo ~ 250ms por 100k, y ~ 600ms por 1M. Seguí adelante y fui a 10M en ~ 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")
También volví y escribí una versión de CoffeeScript (V8 JavaScript), que obtiene ~ 15ms para 100k, 250ms para 1M y 6s para 10M, usando un contador (ignorando I / O). Si enciendo la salida, toma ~ 150ms para 100k, 1s para 1M y 12s para 10M. No pude usar la recursividad de cola aquí, desafortunadamente, así que tuve que convertirla nuevamente en bucles.
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")
La respuesta a su pregunta n. ° 1 es que sí, la JVM es increíblemente rápida y sí la escritura estática ayuda.
La JVM debería ser más rápida que C a largo plazo, posiblemente incluso más rápida que el lenguaje ensamblador "Normal". Por supuesto, siempre puedes optimizar el ensamblaje para superar cualquier cosa haciendo un perfil de tiempo de ejecución manual y creando una versión separada para cada CPU, solo tiene que ser increíblemente bueno y eficiente.
Los motivos de la velocidad de Java son:
La JVM puede analizar su código mientras se ejecuta y optimizarlo a mano, por ejemplo, si tiene un método que podría analizarse estáticamente en tiempo de compilación para ser una función verdadera y la JVM notó que a menudo lo llamaba con el mismo parámetros, PODRÍA eliminar la llamada por completo y solo inyectar los resultados de la última llamada (no estoy seguro si Java realmente hace esto exactamente, pero hace un montón de cosas como esta).
Debido al tipado estático, la JVM puede saber mucho sobre su código en tiempo de compilación, esto le permite preoptimizar un poco de cosas. También le permite al compilador optimizar cada clase individualmente sin saber cómo está planeando usarla otra clase. Also Java doesn''t have arbitrary pointers to memory location, it KNOWS what values in memory may and may not be changed and can optimize accordingly.
Heap allocation is MUCH more efficient than C, Java''s heap allocation is more like C''s stack allocation in speed--yet more versatile. A lot of time has gone into the different algroithims used here, it''s an art--for instance, all the objects with a short lifespan (like C''s stack variables) are allocated to a "known" free location (no searching for a free spot with enough space) and are all freed together in a single step (like a stack pop).
The JVM can know quirks about your CPU architecture and generate machine code specifically for a given CPU.
The JVM can speed your code long after you shipped it. Much like moving a program to a new CPU can speed it up, moving it to a new version of the JVM can also give you huge speed performances taylored to CPUs that didn''t even exist when you initially compiled your code, something c physically cannot do without a recomiple.
By the way, most of the bad rep for java speed comes from the long startup time to load the JVM (Someday someone will build the JVM into the OS and this will go away!) and the fact that many developers are really bad at writing GUI code (especially threaded) which caused Java GUIs to often become unresponsive and glitchy. Simple to use languages like Java and VB have their faults amplified by the fact that the capibilities of the average programmer tends to be lower than more complicated languages.
No importa los puntos de referencia; el problema me interesó y realicé algunos ajustes rápidos. Esto usa el decorador lru_cache , que memoriza una función; así que cuando llamamos a is_prime(i-6) básicamente obtenemos esa verificación principal gratis. Este cambio reduce el trabajo aproximadamente a la mitad. Además, podemos hacer que las llamadas de range() pasen solo por los números impares, cortando el trabajo aproximadamente a la mitad otra vez.
http://en.wikipedia.org/wiki/Memoization
http://docs.python.org/dev/library/functools.html
Esto requiere que Python 3.2 o posterior obtenga lru_cache , pero podría funcionar con un Python anterior si instala una receta de Python que proporcione lru_cache . Si está utilizando Python 2.x, realmente debería usar xrange() lugar 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)))
Lo anterior tomó muy poco tiempo para editar. Decidí dar un paso más y hacer que los primos solo prueben los divisores primos, y solo hasta la raíz cuadrada del número que se está probando. La forma en que lo hice solo funciona si revisas los números en orden, para que pueda acumular todos los números primos a medida que avanzan; pero este problema ya estaba controlando los números en orden, así que estaba bien.
En mi computadora portátil (nada especial, el procesador es un AMD Turion II "K625" de 1.5 GHz), esta versión produjo una respuesta de 100K en 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)))
El código anterior es bastante fácil de escribir en Python, Ruby, etc. pero sería más doloroso para C.
No puede comparar los números en esta versión con los números de las otras versiones sin reescribir los otros para usar trucos similares. No estoy tratando de probar nada aquí; Simplemente pensé que el problema era divertido y quería ver qué tipo de mejoras de rendimiento fácil podía obtener.
No pude resistirme a hacer algunas de las optimizaciones más obvias para la versión C que hicieron que la prueba 100k ahora tome 0.3s en mi máquina (5 veces más rápido que la versión C en la pregunta, ambos compilados con 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 );
}
Aquí está la implementación idéntica en 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" );
}
}
Con Java 1.7.0_04, esto se ejecuta casi exactamente tan rápido como la versión C. Cliente o servidor VM no muestra mucha diferencia, excepto que el entrenamiento JIT parece ayudar un poco al servidor VM (~ 3%) mientras que casi no tiene efecto con la VM del cliente. El resultado en Java parece ser más lento que en C. Si el resultado se reemplaza con un contador estático en ambas versiones, la versión de Java se ejecuta un poco más rápido que la versión C.
Estos son mis tiempos para la carrera de 100k:
- 319ms C compilados con / Ox y salida a> NIL:
- 312ms C compilados con / Ox y contador estático
- 324ms Java cliente VM con salida a> NIL:
- 299ms Java cliente VM con contador estático
y la ejecución de 1M (16386 resultados):
- 24.95s C compilado con / Ox y contador estático
- 25.08s Java cliente VM con contador estático
- 24.86s Java server VM con contador estático
Si bien esto realmente no responde a sus preguntas, muestra que los pequeños ajustes pueden tener un impacto notable en el rendimiento. Entonces, para poder realmente comparar idiomas, debes tratar de evitar todas las diferencias algorítmicas tanto como sea posible.
También da una pista de por qué Scala parece bastante rápido. Se ejecuta en Java VM y, por lo tanto, se beneficia de su impresionante rendimiento.
Puedes hacer que Scala sea mucho más rápido modificando tu método isPrime para
def isPrime(n: Int, i: Int = 2): Boolean =
if (i == n) true
else if (n % i != 0) isPrime(n, i + 1)
else false
No es tan conciso, pero el programa se ejecuta en el 40% del tiempo.
Cortamos los objetos Range superfluo y Function anónima, el compilador de Scala reconoce la recursión de cola y la convierte en un ciclo while, que la JVM puede convertir en un código de máquina más o menos óptimo, por lo que no debería estar demasiado lejos. la versión C
Vea también: ¿Cómo optimizar las comprensiones y bucles en Scala?
Respuestas ásperas
- La tipificación estática de Scala lo está ayudando bastante aquí, esto significa que usa la JVM de manera bastante eficiente sin demasiado esfuerzo extra.
- No estoy exactamente seguro de la diferencia de Ruby / Python, pero sospecho que
(2...n).all?en la funciónis-prime?es probable que esté bastante bien optimizado en Ruby (EDITAR: parece que este es el caso, ver la respuesta de Julian para más detalles ...) - Ruby 1.9.3 está mucho mejor optimizado
- El código de Clojure ciertamente se puede acelerar mucho! Si bien Clojure es dinámico de manera predeterminada, puede usar sugerencias de tipo, matemáticas primitivas, etc. para acercarse a Scala / velocidad de Java pura en muchos casos cuando lo necesite.
La optimización más importante en el código de Clojure sería usar matemáticas primitivas mecanografiadas dentro de 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))))))
Con esta mejora, obtengo que Clojure complete 10k en 0.635 segundos (es decir, el segundo más rápido en su lista, superando a Scala)
PD: tenga en cuenta que tiene código de impresión dentro de su punto de referencia en algunos casos, ¡no es una buena idea, ya que distorsionará los resultados, especialmente si usar una función como print por primera vez causa la inicialización de subsistemas IO o algo así!
Solo por el gusto de hacerlo, aquí hay una versión 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
En mi MacBook Air Core i5 de 1.8GHz, los resultados de rendimiento son:
# 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 el JIT de la JVM le da a Ruby un buen impulso en el rendimiento en el caso predeterminado, mientras que el multihilo verdadero ayuda a JRuby a rendir un 50% más rápido en la caja con rosca. Lo que es más interesante es que JRuby 1.7 mejora el puntaje de JRuby 1.6 en un saludable 17%.
Voy a responder simplemente # 2, ya que es el único que tengo algo remotamente inteligente que decir, pero para tu código Python, estás creando una lista intermedia en is_prime , mientras que estás usando .map en tu all en Ruby que solo está iterando.
Si cambia su is_prime a:
def is_prime(n):
return all((n%j > 0) for j in range(2, n))
están a la par.
Podría optimizar el Python aún más, pero mi Ruby no es lo suficientemente bueno como para saber cuándo le he dado más ventajas (por ejemplo, usar xrange hace que Python gane en mi máquina, pero no recuerdo si el rango de Ruby que utilizó crea un rango completo en la memoria o no).
EDITAR: sin ser demasiado tonto, haciendo que el código de Python se vea así:
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")
que no cambia mucho más, lo pone en 1.5s para mí, y, siendo muy tonto, ejecutarlo con PyPy lo pone en .3s por 10K, y 21s por 100K.