为什么 Clojure 在 clojure.lang.Iterate.first 上花费了这么多时间

Question

我非常喜欢弗兰克·纳尔逊·科尔的故事，他在 1903 年在一个著名的"无言讲座"中证明了 2^67 - 1 的素因数分解。如今，使用以下朴素算法可以很容易地找到因式分解：

(def mersenne67 (dec (expt 2 67)))
(->> (iterate inc 2)
     (filter #(zero? (rem mersenne67 %)))
     (first))

但是，我注意到这个 Clojure 代码花费的时间大约是等效的 Java 或 Kotlin 代码的两倍。(~40 与 ~20 秒在我的机器上(
这是我将其与 Java 进行比较的：

  public static BigInteger mersenne() {
    BigInteger mersenne67 = 
      BigInteger.valueOf(2).pow(67).subtract(BigInteger.ONE);
    return Stream.iterate(BigInteger.valueOf(2), (x -> x.add(BigInteger.ONE)))
      .filter(x -> mersenne67.remainder(x).equals(BigInteger.ZERO))
      .findFirst()
      .get();
  }

在较低级别重写 Clojure 代码没有任何区别：

(def mersenne67 (-> (BigInteger/valueOf 2)
                (.pow (BigInteger/valueOf 67))
                (.subtract BigInteger/ONE)))
(->> (iterate #(.add ^BigInteger % BigInteger/ONE) (BigInteger/valueOf 2))
     (filter #(= BigInteger/ZERO (.remainder ^BigInteger mersenne67 %)))
     (first))

在使用 VisualVM 分析代码后，主要嫌疑人似乎是clojure.lang.Iterate.first()这几乎完全解释了这些功能运行时间的差异。Java的等效java.util.stream.ReferencePipeline.findFirst()运行时间只有一小部分(~22 vs ~2秒(。这就引出了我的问题：Java(和 Kotlin(是如何在这个任务上花费如此少的时间的？

Answer 1

你的问题是你低效地迭代你的iterate。这就是为什么您在分析中看到first顶部的原因。当然，这是clojure的所有核心功能都使用大量不同数据结构的结果。

避免这种情况的最好方法是使用 reduce ，它为对象本身提供了在循环中调用函数的任务。

所以这大约是 2 倍快：

(reduce
      (fn [_ x]
        (when (identical? BigInteger/ZERO (.remainder ^BigInteger mersenne67 x))
          (reduced x)))
      nil
      (iterate #(.add ^BigInteger % BigInteger/ONE) (BigInteger/valueOf 2)))

Answer 2

我提前为挖坟道歉，但我有点担心ClojureMostly的回答。它肯定会及时解决问题，但对我来说它看起来像一个肮脏的黑客：传递匿名归约函数，该函数忽略当前结果 (_( 并在找到第一个因素(归约(后立即完成。

如何使用换能器和转导功能：

(defn first-factor-tr 
  [^BigInteger n] 
  (transduce
    (comp (filter #(identical? BigInteger/ZERO (.remainder ^BigInteger n %))) (take 1))
    conj nil
    (iterate #(.add ^BigInteger % BigInteger/ONE) (BigInteger/valueOf 2))))

过滤掉集合中余数为零的所有值(过滤器...(并取第一个值(取...(。

此解决方案的执行时间与具有 reduce：

(defn first-factor-reduce 
  [^BigInteger n] 
  (reduce
    (fn [_ x]
      (when (identical? BigInteger/ZERO (.remainder ^BigInteger n x))
            (reduced x)))
    nil
    (iterate #(.add ^BigInteger % BigInteger/ONE) (BigInteger/valueOf 2))))
=> (time (first-factor-tr mersenne67))
"Elapsed time: 20896.594178 msecs"
(193707721)
=> (time (first-factor-reduce mersenne67))
"Elapsed time: 20424.323894 msecs"
193707721