Interpréter la référence en C, Clojure, Python, Ruby, Scala et d’autres

Question

Avertissement

Je sais que les indices de référence sont le mal. Ils peuvent afficher uniquement les résultats pour des cas très particuliers étroit de la situation. Je ne suppose pas qu'une langue est mieux que les autres en raison de la certains stupide banc. Cependant je me demande pourquoi les résultats sont si différents. Veuillez voir mes questions au fond.

Math référence description

Indice de référence des calculs mathématiques simples pour trouver des paires de nombres premiers qui diffèrent par 6 (soi-disant sexy nombres premiers) E. g. sexy nombres premiers inférieurs à 100 serait: (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)

Tableau des résultats

Dans le tableau: temps de calcul en secondes En cours d'exécution: tous sauf le Facteur était en cours d'exécution dans VirtualBox (la version unstable de Debian amd64 invité, Windows 7 x64 accueil) PROCESSEUR: 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] - j'ai peur d'imaginer combien de temps ça va prendre

Les exemples de Code

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

Ruby:

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 opimized isPrime (la même idée comme en Clojure optimisation):

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

Python

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

Facteur de

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

Questions

1. Pourquoi Scala est si vite? C'est à cause de typage statique? Ou c'est juste à l'aide de la JVM de manière très efficace?
2. Pourquoi une telle différence entre Ruby et Python? Je pensais que ces deux ne sont pas un peu complètement différent. Peut-être que mon code est faux. Merci de m'éclairer! Merci. UPD Oui, c'était une erreur dans mon code. Python et Ruby 1.9 sont assez égale.
3. Vraiment impressionnant saut de productivité entre les versions Rubis.
4. Puis-je optimiser Clojure code par adjonction de ce type de déclarations? Il va les aider?

Answer 1

Rugueux réponses:

1. Scala est le typage statique est de l'aider un peu ici - ce qui signifie qu'il utilise la JVM assez efficacement sans trop d'effort supplémentaire.
2. Je ne suis pas sûr de savoir exactement sur le Ruby/Python différence, mais je soupçonne qu' (2...n).all? dans la fonction is-prime? est susceptible d'être assez bien optimisé en Ruby (EDIT: on dirait que c'est effectivement le cas, voir Julian réponse pour plus de détails...)
3. Ruby 1.9.3 est juste beaucoup mieux optimisé
4. Clojure code peut certainement être accéléré beaucoup! Tout en Clojure est dynamique par défaut, vous pouvez utiliser le type de conseils, primitif maths etc. pour obtenir près de Scala / Java pur vitesse dans de nombreux cas, lorsque vous en avez besoin.

Le plus important de l'optimisation dans le Clojure code serait d'utiliser tapé primitives mathématiques dans is-prime?, quelque chose comme:

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

Avec cette amélioration, je reçois Clojure remplir 10k en 0.635 secondes (c'est à dire le deuxième plus rapide sur votre liste, en battant la Scala)

P. S. notez que vous avez l'impression de code à l'intérieur de votre point de repère dans certains cas - pas une bonne idée car il va fausser les résultats, en particulier si vous utilisez une fonction comme print , pour la première fois les causes de l'initialisation de IO sous-systèmes ou quelque chose comme ça!

Answer 2

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

Il fonctionne environ 20 x plus rapide que votre original sur ma machine. Et voici une version qui tire parti de la nouvelle bibliothèque de réducteurs à 1.5 (nécessite Java 7 ou JSR 166) :

Cela exécute environ 40 fois plus rapide que votre original. Sur ma machine, c’est 100k en 1,5 secondes.

Answer 3

Je vais répondre simplement #2, car c'est le seul que j'ai quelque chose à distance intelligent à dire, mais pour votre code Python, vous êtes en train de créer un intermédiaire de liste dans is_prime, alors que vous êtes en utilisant .map votre all en Ruby, qui est juste de l'itération.

Si vous changez d' is_prime :

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

ils sont à égalité.

J'ai pu optimiser le Python, mais mon Ruby n'est pas assez bon à savoir quand j'ai donné plus d'un avantage (par exemple, à l'aide de xrange rend Python gagner sur ma machine, mais je ne me souviens pas si la chaîne Ruby vous avez utilisé crée une gamme complète dans la mémoire ou pas).

EDIT: Sans être trop ridicule, rendant le code Python ressembler à:

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

ce qui ne change pas beaucoup plus, il met à 1,5 s pour moi, et, en étant encore plus ridicule, de l'exécution avec PyPy, il met à .3s pour 10K, et de 21 ans pour 100K.

Answer 4

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

  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 avons découpé le superflu Range et anonyme Function 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 C version.

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

Answer 5

Voici ma version de la scala en parallèle et non parallèle, juste pour le plaisir : (dans mon calcul de double cœur, la version parallèle prend 335ms tandis que la version non-parallèle prend 655ms)

EDIT : Selon la suggestion de Emil H, j’ai changé mon code pour éviter les effets de IO et jvm warm-up :

Le résultat montre dans mon calcul :

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