L'interprétation d'un test en C, Clojure, Python, Ruby, Scala et les autres

Voici un rapide Clojure version, en utilisant les mêmes algorithmes de base:

(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]))

Il fonctionne environ 20x plus vite que votre original sur ma machine. Et voici une version qui s'appuie sur les nouveaux réducteurs de la bibliothèque en 1.5 (nécessite 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)))

Cela fonctionne environ 40x plus rapide que celui de votre originaux. Sur ma machine, c'est 100k en 1,5 secondes.

Vous pouvez faire de la Scala beaucoup plus vite en modifiant votre isPrime méthode pour

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

Pas tout à fait aussi concis mais le programme s'exécute à 40% du temps!

Nous couper le superflu Range et anonyme Function des objets, de la Scala compilateur reconnaît la queue-la récursivité et la transforme en un moment, en boucle, que la JVM peut se transformer en un plus ou moins optimal de code machine, de sorte qu'il ne devrait pas être trop loin de la version de C.

Voir aussi: Comment optimiser pour des inclusions et des boucles en Scala?

Jamais l'esprit les critères de référence; le problème m'a intéressé et j'ai fait un rapide réglages. Il utilise la lru_cache décorateur, qui memoizes une fonction; ainsi, lorsque nous appelons is_prime(i-6) essentiellement, nous obtenons que le premier contrôle de la liberté. Ce changement coupes le travail à peu près à la moitié. Aussi, nous pouvons faire la range() appels étape à travers tout le nombres impairs, la réduction du travail à peu près de moitié à nouveau.

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

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

Cela nécessite Python 3.2 ou plus récent pour obtenir lru_cache, mais pourrait fonctionner avec un plus vieux Python si vous installez un Python recette qui fournit lru_cache. Si vous utilisez Python 2.x vous devriez vraiment utiliser xrange() au lieu 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)))

Ci-dessus n'a pris que très peu de temps à modifier. J'ai décidé de prendre une nouvelle étape, et de faire les premiers test seulement essayer de diviseurs premiers, et seulement jusqu'à la racine carrée du nombre d'être testé. Je l'ai fait ne fonctionne que si vous vérifiez les numéros dans l'ordre, de sorte qu'il peut cumuler tous les nombres premiers comme il va; mais ce problème a déjà été cochant les numéros dans l'ordre, donc c'était bon.

Sur mon portable (rien de spécial; processeur est un processeur de 1,5 GHz AMD Turion II "K625"), cette version apporte une réponse à 100 en moins de 8 secondes.

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

Le code ci-dessus est assez facile d'écrire en Python, Ruby, etc. mais serait plus d'une douleur dans C.

Vous ne pouvez pas comparer les chiffres sur cette version à l'encontre de l'un des numéros de l'autre des versions sans avoir à réécrire les autres à utiliser des astuces similaires. Je ne cherche pas à prouver quoi que ce soit ici; j'ai juste pensé que le problème était amusant et j'ai voulu voir ce genre de représentation facile améliorations que j'ai pu glaner.

Je ne pouvais pas résister à faire un peu de la plus évidente des optimisations pour la version C qui a fait le test 100k maintenant prendre 0,3 s sur ma machine (5 fois plus rapide que la version C de la question, à la fois compilé avec 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 );
}

Ici est l'identique de la mise en œuvre 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" );
}
}

Avec Java 1.7.0_04 cela fonctionne presque aussi rapide que le C de la version. Le Client ou le serveur VM ne montre pas beaucoup de différence, sauf que JIT de la formation semble aider le serveur VM un peu (~3%) alors qu'il a presque pas d'effet avec le client VM. La sortie en Java semble être plus lent que dans C. Si la sortie est remplacé par un compteur statique dans les deux versions, la version Java tourne un peu plus vite que la version de C.

Ce sont mes temps pour le 100k exécuter:

• 319ms C compilé avec /Ox et de sortie >NUL:
• 312ms C compilé avec /Ox et statique contre
• 324ms client Java VM avec sortie >NUL:
• 299ms client Java VM avec statique contre

et la 1M run (16386 résultats):

• 24.95 s C compilé avec /Ox et statique contre
• 25.08 s client Java VM avec statique contre
• 24.86 s Java server VM avec statique contre

Alors que ce n'est pas vraiment répondre à vos questions, il montre que de petites modifications peuvent avoir un impact notable sur les performances. Donc, pour être en mesure de vraiment comparer les langues que vous devriez essayer d'éviter tous algorithmique différences autant que possible.

Il donne également un aperçu pourquoi Scala semble plutôt rapide. Il s'exécute sur la machine virtuelle Java, et donc des avantages à partir de ses performances impressionnantes.

Voici le code pour l'Aller (golang.org version:

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

Il a couru aussi vite que la version de C.

À l'aide d'un Asus u81a
Intel Core 2 Duo T6500 2.1 GHz, 2MB L2 cache, 800 mhz FSB.
4 GO DE RAM

Les 100k version: C: 2.723s Go: 2.743s

Avec 1000000 (1M au lieu de 100K): C: 3m35.458s Go: 3m36.259s

Mais je pense qu'il serait juste d'utiliser Go construit dans les capacités de multithreading et de comparer cette version à la version C (sans le multithreading), juste parce que c'est presque trop facile de faire du multithreading avec Go.

Mise à jour: j'ai fait une version parallèle à l'aide de Goroutines en Aller:

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 version parallélisée utilisé en moyenne 2.743 secondes, exactement le même temps que la version normale utilisé.

La version parallélisée achevé en 1.706 secondes. Il a utilisé moins de 1,5 Mo de RAM.

Une chose étrange: Mon dual core kubuntu 64 bits jamais atteint un sommet dans les deux noyaux. Il semblait Aller a l'aide d'une seule base. le Fixe avec un appel à runtime.GOMAXPROCS(4)

Mise à jour: j'ai couru le paralellized version 1M numéros. l'Un de Mes coeurs de CPU est à 100% tout le temps, tandis que l'autre n'était pas utilisé à tous (impair). Il a fallu toute une minute de plus que le C et le régulier d'Aller les versions. 🙁

Avec 1000000 (1M au lieu de 100K):

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

Les 100k version:

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

Basé sur x4u réponse, j'ai écrit un scala version en utilisant la récursivité, et j'ai amélioré par seulement aller à la racine carrée à la place de x/2 pour le premier de la fonction de contrôle. Je reçois ~250ms pour 100k, et ~600ms pour 1M. Je suis allé de l'avant et est allé à 10M de ~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")

Je suis aussi rentré et a écrit un CoffeeScript (JavaScript V8) version, qui obtient ~15ms pour 100k, 250ms pour 1M, et 6 sur 10 m, à l'aide d'un compteur (en ignorant I/O). Si j'allume la sortie il faut ~150ms pour 100k, 1s pour 1M, et 12 pour 10M. Ne pouvait pas utiliser la récursivité tail ici, malheureusement, j'ai donc eu à convertir en boucles.

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")