Heap算法可以枚举一个数组的全排列。维基百科关于该算法的文章指出,Robert Sedgewick得出结论认为该算法是“当时生成计算机排列最有效的算法”,因此实现该算法肯定会很有趣。
该算法是通过在可变数组内进行一系列交换来完成的,所以我考虑在Clojure中实现它,因为Clojure的序列是不可变的。我编写了以下代码,完全避免了可变性:
该算法是通过在可变数组内进行一系列交换来完成的,所以我考虑在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在这个算法上的性能呢?
criterium/bench
运行你的初始代码,11个字符的执行时间约为80-82微秒。数组版本将其缩短至59-60微秒。 - MagosSystem.currentTimeMillis
和Clojure的time
宏进行简单的时钟时间测量之间的差异仍然比我预期的要大得多。关于criterium
的技巧很棒,我会去了解一下。 - Ray Toal