Clojure中的Heap算法(可以有效实现吗？)

Question

Heap的算法枚举了数组的排列.维基百科关于算法的文章说,罗伯特塞奇威克总结说,算法"当时是计算机生成排列的最有效算法",所以自然会尝试实现它.

该算法是关于在可变数组中进行一系列交换的,所以我在Clojure中实现这个,它的序列是不可变的.我把以下内容放在一起,完全避免了可变性:

(defn swap [a i j]
  (assoc a j (a i) i (a j)))

(defn generate-permutations [v n]
  (if (zero? n)
    ();(println (apply str a));Comment out to time just the code, not the print
    (loop [i 0 a v]
      (if (<= i n)
        (do
          (generate-permutations a (dec n))
          (recur (inc i) (swap a (if (even? n) i 0) n)))))))

(if (not= (count *command-line-args*) 1)
  (do (println "Exactly one argument is required") (System/exit 1))
  (let [word (-> *command-line-args* first vec)]
    (time (generate-permutations word (dec (count word))))))

对于一个11个字符的输入字符串,该算法在7.3秒内运行(在我的计算机上)(平均超过10次运行).

使用字符数组的等效Java程序在0.24秒内运行.

所以我想让Clojure代码更快.我使用了带有类型提示的Java数组.这是我试过的:

(defn generate-permutations [^chars a n]
  (if (zero? n)
    ();(println (apply str a))
    (doseq [i (range 0 (inc n))]
      (generate-permutations a (dec n))
      (let [j (if (even? n) i 0) oldn (aget a n) oldj (aget a j)]
        (aset-char a n oldj) (aset-char a j oldn)))))

(if (not= (count *command-line-args*) 1)
  (do
    (println "Exactly one argument is required")
    (System/exit 1))
  (let [word (-> *command-line-args* first vec char-array)]
    (time (generate-permutations word (dec (count word))))))

好吧,它慢了.现在,11个字符的数组平均为9.1秒(即使是类型提示).

我理解可变数组不是Clojure方式,但有没有办法在这个算法中接近Java的性能？

Answer 1

Clojure 并不完全是为了避免可变状态。Clojure 对于何时应该使用它有非常强烈的意见。

在这种情况下，我强烈建议找到一种使用瞬态重写算法的方法，因为它们专门设计用于通过避免重新分配内存并允许集合在本地可变（只要对集合的引用永远不会）来节省时间。保留创建它的函数。最近，通过使用它们，我成功地将内存密集型操作的时间缩短了近 10 倍。

这篇文章很好地解释了瞬态！

http://hypirion.com/musings/understanding-clojure-transients

此外，您可能希望考虑以允许使用 recur 递归调用generatePermutations 而不是使用整个名称的方式重写循环结构。您可能会获得性能提升，并且对堆栈的负担也会大大减少。

我希望这有帮助。