Clojure 从 Java 翻译过来

Question

我开始学习 Clojure，并决定在 HackerRank 上做一些项目是一个很好的方法。我发现我的 Clojure 解决方案非常慢。我假设那是因为我仍在强制性地思考，或者只是对 Clojure 的运作方式了解不够。我为之编写解决方案的最新问题是归零 II。这是我的 Java 代码

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
    private static final int MAX_NUMBER = 1000000;
    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static int[] precompute() {
        int[] values = new int[MAX_NUMBER];

        values[0] = 0;
        values[1] = 1;

        for (int i = 1; i < MAX_NUMBER; i += 1) {
            if ((values[i] == 0) || (values[i] > (values[i - 1] + 1))) {
                values[i] = (values[i - 1] + 1);
            }

            for (int j = 1; j <= i && (i * j) < MAX_NUMBER; j += 1) {
                int mult = i * j;

                if ((values[mult] == 0) || (values[mult] > (values[i] + 1))) {
                    values[mult] = values[i] + 1;
                }
            }
        }

        return values;
    }

    public static void main(String[] args) throws Exception {
        int numQueries = Integer.parseInt(reader.readLine());

        int[] values = Solution.precompute();

        for (int loop = 0; loop < numQueries; loop += 1) {
            int query = Integer.parseInt(reader.readLine());
            System.out.println(values[query]);
        }
    }
}

我的 Clojure 实现是

(def MAX-NUMBER 1000000)

(defn set-i [out i]
(cond
    (= 0 i) (assoc out i 0)
    (= 1 i) (assoc out i 1)
    (or (= 0 (out i))
        (> (out i) (inc (out (dec i)))))
    (assoc out i (inc (out (dec i))))
    :else out))

(defn set-j [out i j]
(let [mult (* i j)]
    (if (or (= 0 (out mult)) (> (out mult) (inc (out i))))
    (assoc out mult (inc (out i)))
    out)))

;--------------------------------------------------
; Precompute the values for all possible inputs
;--------------------------------------------------
(defn precompute []
(loop [i 0 out (vec (repeat MAX-NUMBER 0))]

    (if (< i MAX-NUMBER)
    (recur (inc i) (loop [j 1 new-out (set-i out i)]
                    (if (and (<= j i) (< (* i j) MAX-NUMBER))
                        (recur (inc j) (set-j new-out i j))
                        new-out)))
    out)))

;--------------------------------------------------
; Read the number of queries
;--------------------------------------------------
(def num-queries (Integer/parseInt (read-line)))

;--------------------------------------------------
; Precompute the solutions
;--------------------------------------------------
(def values (precompute))

;--------------------------------------------------
; Read and process each query
;--------------------------------------------------
(loop [iter 0]
(if (< iter num-queries)
    (do
    (println (values (Integer/parseInt (read-line))))
    (recur (inc iter)))))

Java 代码在我的机器上运行大约需要 1/10 秒，而 Clojure 代码需要接近 2 秒。由于是同一台机器，具有相同的 JVM，这意味着我在 Clojure 中做错了。

人们如何尝试翻译此类代码？导致它慢得多的陷阱是什么？

Answer 1

我将对您的代码进行一些转换(这可能会稍微超出您最初的要求)然后解决您更具体的问题。

我知道已经快两年了，但是在遇到你的问题并花了太多时间与HackerRank 及其时间限制，我想我会发布一个答案。是否在 HR 的环境中实现了解决方案，并且时间限制让我们成为更好的 Clojure 程序员？我没有学到答案。但我会分享我学到的东西。

我发现了你的相同算法的一个稍微精简的版本。它仍然有两个循环，但更新只发生一次内部循环，许多条件都在 min 函数中处理。这是我对它的改编:

(defn compute
  "Returns a vector of down-to-zero counts for all numbers from 0 to m."
  [m]
  (loop [i 2 out (vec (range (inc m)))]
    (if (<= i m)
      (recur (inc i)
             (loop [j 1 out out]
               (let [ij (* i j)]
                 (if (and (<= j i) (<= ij m))
                   (recur (inc j) 
                          (assoc out ij (min (out ij)               ;; current value
                                             (inc (out (dec ij)))   ;; steps from value just below
                                             (inc (out i)))))       ;; steps from a factor
                   out))))
      out)))

请注意，我们仍在使用循环/递归(两次)，我们仍在使用向量来保存输出。但有些不同:

1. 我们将 out 初始化为递增整数。这是每个值的最坏情况步数，一次初始化后，我们不必测试值是否等于 0，我们可以跳过索引 0 和 1 并在以下位置开始外循环索引 2。(我们还修复了原始文件中的错误，并确保 out 包含 MAX-NUMBER+1 值。)

2. 所有三个测试都发生在封装原始逻辑的 min 函数中:一个值将是只有当它比它下面的数字或其中一个因素的步数更短时才会更新。

3. 测试现在非常简单，我们不需要将它们分解成单独的函数。

此代码(连同您的原始代码)足够快，可以通过 HR 中的一些 测试用例，但不是全部。这里有一些加快速度的事情:

1. 使用int-array 代替vec。这意味着我们将使用 aset 而不是 assoc 和 aget 而不是调用 out有一个索引。这也意味着 loop/recur 不再是最好的结构(因为我们不再通过围绕一个不可变向量的新版本，但实际上改变了一个 java.util.Array);相反，我们将使用 doseq。

2. 键入提示。仅此一项就产生了巨大的速度差异。测试您的代码时，在顶部包含一个表单 (set! *warn-on-reflection* true) 并且您会看到 Clojure 必须在哪里做额外的工作才能弄清楚它是什么类型处理。

3. 使用自定义 I/O 函数读取输入。 HR 的样板 I/O 代码应该让你专注于解决挑战而不用担心 I/O，但它基本上是垃圾，而且通常是程序超时的罪魁祸首。

下面是一个结合了上述技巧的版本，运行速度足以通过所有测试用例。我已经包含了我的习惯我一直在使用的 I/O 方法来应对我的所有 HR 挑战。使用 doseq 的一个好处是我们可以包含一个:let 和绑定(bind)形式中的 :while 子句，删除了 doseq 正文中的一些缩进。还请注意一些策略性放置的类型提示，它们确实可以加快程序的速度。

(ns down-to-zero-int-array)

(set! *warn-on-reflection* true)

(defn compute
  "Returns a vector of down-to-zero counts for all numbers from 0 to m."
  ^ints [m]
  (let [out ^ints (int-array (inc m) (range (inc m)))]
    (doseq [i (range 2 (inc m)) j (range 1 (inc i)) :let [ij (* i j)] :while (<= ij m)]
      (aset out ij (min (aget out ij)
                        (inc (aget out (dec ij)))
                        (inc (aget out i)))))
    out))

(let [tokens ^java.io.StreamTokenizer 
      (doto (java.io.StreamTokenizer. (java.io.BufferedReader. *in*))
        (.parseNumbers))]
  (defn next-int []
    "Read next integer from input. As fast as `read-line` for a single value, 
     and _much_ faster than `read-line`+`split` for multiple values on same line."
    (.nextToken tokens)
    (int (.-nval tokens))))

(def MAX 1000000)

(let [q (next-int)
      down-to-zero (compute MAX)]
  (doseq [n (repeatedly q next-int)]
    (println (aget down-to-zero n))))