java - 为什么 Clojure 在 clojure.lang.Iterate.first 上花这么多时间？

Question

我很喜欢关于Frank Nelson Cole的故事，他于 1903 年在著名的“无言讲座”中演示了 2^67 - 1 的质因数分解。如今，可以使用以下朴素算法轻松找到因式分解:

(def mersenne67 (dec (expt 2 67)))

(->> (iterate inc 2)
     (filter #(zero? (rem mersenne67 %)))
     (first))

但是我注意到，此 Clojure 代码所花的时间大约是等效的 Java 或 Kotlin 代码的两倍。 (~40 vs ~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 对~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)))