3

对于真正熟悉 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. (let) 和绑定开始和结束时间是否可以测量 Clojure 中的执行时间？
  2. 由于某种原因（即使 Java 和 Clojure 版本使用相同的算法），Clojure 版本要慢得多（J：~50ms，C：~400ms）。难道我做错了什么？

如果我犯了一些明显的错误，请原谅我的无知，但我仍处于 Clojure 的学习阶段......

- - -编辑 - - -

我已经对其进行了优化，最终达到了与 Java 相同的时间。我在我的博客中为感兴趣的人描述了它：
http ://blog.programmingdan.com/?p=35

4

3 回答 3

3

这种计时方法很常见，它内置

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

虽然从基准测试的角度来看，我建议使用 Hugo Duncans 的 Criterium 库并阅读这篇关于使用它的帖子。至于使 clojure 代码快速运行，clojure 版本大部分时间都在分配 seq 对象。

于 2013-03-16T01:58:45.093 回答
2

正如上面提到的答案，也许它正在处理惰性序列。这是我的证据......

;; 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 版本在我的计算机上需要多长时间，但您至少可以从上面的时间看到循环/递归版本似乎比使用 seqs 的原始 clojure 版本更快。

注意：您也可以尝试类型提示（http://clojure.org/java_interop#Java%20Interop-Type%20Hints，http://kotka.de/blog/2012/06/Did_you_know_IX.html）以提高速度，但是当我尝试这样做时，并没有什么不同。那可能是因为我以前没有做过太多这样的事情，所以我可能做的不正确。

于 2013-03-17T17:30:48.920 回答
2

由于您在 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 被认为是质数。

于 2013-03-16T02:44:32.107 回答