Генерация временных рядов в Clojure

Question

Это будет вопрос для людей, действительно знакомых с Clojure.
Я хотел написать простую функцию проверки простых чисел в Java и Clojure, а также сравнить время выполнения.
Так вот мой код в Java:

import java.util.LinkedList; 

public class Primes { 
public static void main(String args[]) 
{ 
    long start = System.nanoTime(); 
    getPrimes(10000); 
    long end = System.nanoTime(); 

    System.out.println(((float)(end - start)/1000000) + "ms"); 
} 

private static LinkedList<Integer> getPrimes(int n) 
{ 
    int count = 0; 
    int current = 1; 
    LinkedList<Integer> primes = new LinkedList<Integer>(); 

    while(count <= n) 
    { 
     if(isPrime(current)) 
     { 
      primes.add(current); 
      count++; 
     } 
     current++; 
    } 
    return primes; 
} 

private static boolean isPrime(long n) 
{ 
    if(n <= 0) return false; 
    if(n == 1 || n == 2) return true; 
    if(n % 2 == 0) return false; 
    for(int i=3; i<Math.sqrt(n) + 1; i=i+2) 
    { 
     if(n % i == 0){ 
      return false; 
     } 
    } 
    return true; 
} 
} 

А вот Clojure эквивалент:

(defn prime? [n] 
    (or (= n 2) (not (some #(zero? (rem n %)) (conj (range 3 (inc (Math/sqrt n)) 2) 2))))) 

(defn printPrimes [n] (take n (filter prime? (iterate inc 1)))) 

(defn ExecTime [function & arguments] (let [start (System/nanoTime), return (dorun (apply function arguments)), end (System/nanoTime)] (/ (- end start) 1000000.0))) 

(ExecTime printPrimes 10000) 

В настоящее время существует несколько вещей, которые я не уверен:

1. ли (пусть) и обязательное время начала и окончания ok для измерения времени выполнения в Clojure?
2. По какой-то причине (хотя версии Java и Clojure используют тот же алгоритм), версия Clojure намного медленнее (J: ~ 50 мс, C: ~ 400 мс). Я делаю что-то неправильно?

Простите мое невежество, если я сделал некоторые очевидные ошибки, но я до сих пор нахожусь на стадии обучения с Clojure ...

----- EDIT -----

I оптимизировали его и, в конечном итоге, достигли того же уровня, что и Java. Я описываю это в моем блоге для людей, интересующихся:
http://blog.programmingdan.com/?p=35

Answer 1

Возможно, это касается ленивых секций, как упомянуто выше. Вот мои доказательства ....

;; original prime? function 
(defn prime? [n] 
    (or (= n 2) 
     (not (some #(zero? (rem n %)) 
       (conj (range 3 
           (inc (Math/sqrt n)) 
           2) 
         2))))) 

;; prime? function using recur 
(defn prime?-recur [num] 
    (cond (< num 2) false 
     (= num 2) true 
     (zero? (mod num 2)) false 
     :else (loop [n num 
        i 3] 
       (cond (>= i (inc (Math/sqrt n))) true 
         (zero? (mod n i)) false 
         (< i (inc (Math/sqrt n))) (recur n (+ i 2)))))) 

;; original printPrimes with option for testing both prime? funs 
;; note I changed this to start on 2 since 1 is not prime 
(defn printPrimes [n fn] (take n (filter fn (iterate inc 2)))) 

;; printPrimes using recursion 
(defn printPrimes-recur [num fn] 
    (loop [n num i 2 primes []] 
    (cond (and (fn i) (< (count primes) n)) (recur n (+ i 1) (conj primes i)) 
      (< (count primes) n) (recur n (+ i 1) primes) 
      :else primes))) 

Теперь давайте начнем их. Сначала просто убедитесь, что новый код соответствует вашему исходному коду:

foo> (= (printPrimes 10000 prime?) 
     (printPrimes 10000 prime?-recur) 
     (printPrimes-recur 10000 prime?) 
     (printPrimes-recur 10000 prime?-recur)) 

true 

А теперь несколько раз! (с использованием функции ExecTime)

foo> (println (ExecTime printPrimes 10000 prime?) 
       (ExecTime printPrimes 10000 prime?-recur) 
       (ExecTime printPrimes-recur 10000 prime?) 
       (ExecTime printPrimes-recur 10000 prime?-recur)) 



575.977 166.691 548.363 141.356 
nil 

Таким образом, мы видим изменение простого числа? функция для использования рекурсии делает довольно большую разницу (примерно в 4 раза быстрее), и изменение функции printPrimes для использования рекурсии также имеет значение, но ее просто крошечная разница. Я не уверен, как долго java-версия берет мой компьютер, но вы можете хотя бы видеть из вышеприведенного времени, что версия loop/recur выглядит быстрее, чем исходная версия clojure, использующая seqs.

Примечание: Вы также можете попробовать ввести намеки (http://clojure.org/java_interop#Java%20Interop-Type%20Hints, http://kotka.de/blog/2012/06/Did_you_know_IX.html), чтобы ускорить скорость, но когда я попытался это сделать, это не изменило ситуацию. Это может быть из-за того, что раньше я этого не делал, поэтому я мог делать это ненадлежащим образом.

Answer 2

Этот метод синхронизации это настолько часто, он построен в

user> (time (reduce + (range 1000)))                                  
"Elapsed time: 1.350419 msecs"                                    
499500 

Хотя сделать это достойно с точки зрения сравнительного анализа я рекомендую использовать критериум Hugo Duncans игровая библиотека и reading this post on using it. Что касается того, что код clojure работает быстро, версия clojure тратит большую часть времени на выделение seq-объектов.

Answer 3

Поскольку у вас есть раннее возвращение в Java-коде, я думаю, что эквивалент будет some, а не every. Например:

(defn prime? [n] 
    (or (= n 2) 
     (and (odd? n) 
      (not (some #(= 0 (mod n %)) 
         (range 3 (inc (Math/sqrt n)))))))) 

(time (doall (filter prime? (range 10000)))) 

В моей машине он работает примерно так же, как и ваша версия Java.

КПП: Я не думаю, что 1 считается простым номером.