在Clojure中实现Heap算法（是否可以高效实现）？

Question

Heap算法可以枚举一个数组的全排列。维基百科关于该算法的文章指出，Robert Sedgewick得出结论认为该算法是“当时生成计算机排列最有效的算法”，因此实现该算法肯定会很有趣。

该算法是通过在可变数组内进行一系列交换来完成的，所以我考虑在Clojure中实现它，因为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在这个算法上的性能呢？

- Ray Toal

---

你在比较中考虑了JVM预热/JIT吗？对我来说，通过criterium/bench运行你的初始代码，11个字符的执行时间约为80-82微秒。数组版本将其缩短至59-60微秒。 - Magos

这当然是很好的建议，非常感谢。不过这里的热身比我预期的要多一些，因为使用Java的System.currentTimeMillis和Clojure的time宏进行简单的时钟时间测量之间的差异仍然比我预期的要大得多。关于criterium的技巧很棒，我会去了解一下。 - Ray Toal

当你应该使用这种方式时，如果你使用CamelBack，我的眼睛会烧起来。 - fernandohur

真是太抱歉了。已经修改好了。希望您的眼睛能恢复。顺便说一下，谢谢您的提醒。我自己也常常在语言规范方面变得过于追求细节。 - Ray Toal

这是一个非常有趣的话题。我尝试了您的代码，并尝试进行调整，但并没有太多改进。在我尝试进行优化时，实际上是尝试优化算法，因此可以将算法归类为“面向函数实现”和“面向命令式实现”的两种类型，这是合理的。 - 象嘉道

Answer 1

Clojure 并不完全是关于避免可变状态的。而是 Clojure 对其何时使用有非常强烈的观点。

在这种情况下，我强烈建议您找到一种使用 transients 重写算法的方法，因为它们专门设计用于通过避免重新分配内存并允许集合在本地可变，只要对集合的引用永远不离开创建它的函数。最近，我成功地将一个严重消耗内存的操作时间减少了近10倍，使用了它们。

这篇文章很好地解释了 transients！

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

此外，您可能想要重新编写您的循环结构，以便允许您使用recur来递归调用generatePermutations，而不是使用整个名称。这样做可以提高性能，并且会减少堆栈负担。

希望这可以帮助到您。

- sleepysilverdoor