在 Clojure 中调试执行缓慢的函数

Question

我正在尝试实现一种解决方案，用于在clojure中对数组进行排序所需的最小交换。

代码可以工作，但需要大约一秒钟来求解 7 元素向量，与 Java 中的类似解决方案相比，这非常差。(已编辑( 我已经尝试提供显式类型，但似乎没有区别 我尝试使用瞬态，但有一个针对 subvec 的开放错误，我正在我的解决方案中使用 - https://dev.clojure.org/jira/browse/CLJ-787

关于如何优化解决方案的任何指示？

;; Find minimumSwaps required to sort the array. The algorithm, starts by iterating from 0 to n-1. In each iteration, it places the least element in the ith position. 
(defn minimumSwaps [input]
(loop [mv input, i (long 0), swap-count (long 0)]
(if (< i (count input))
(let [min-elem (apply min (drop i mv))]
(if (not= min-elem (mv i))
(recur (swap-arr  mv i min-elem),
(unchecked-inc i),
(unchecked-inc swap-count))
(recur mv,
(unchecked-inc i),
swap-count)))
swap-count)))
(defn swap-arr [vec x min-elem]
(let [y (long (.indexOf vec min-elem))]
(assoc vec x (vec y) y (vec x))))
(time (println (minimumSwaps [7 6 5 4 3 2 1])))

Answer 1

在你的解决方案中，有一些东西可以在算法和效率方面进行改进。主要改进是在搜索时记住向量中的最小元素及其位置。这允许您不再使用 .indexOf 搜索最小元素。

这是我修改后的解决方案，速度快了~4倍：

(defn swap-arr [v x y]
(assoc v x (v y) y (v x)))
(defn find-min-and-position-in-vector [v, ^long start-from]
(let [size (count v)]
(loop [i start-from, min-so-far (long (nth v start-from)), min-pos start-from]
(if (< i size)
(let [x (long (nth v i))]
(if (< x min-so-far)
(recur (inc i) x i)
(recur (inc i) min-so-far min-pos)))
[min-so-far min-pos]))))
(defn minimumSwaps [input]
(loop [mv input, i (long 0), swap-count (long 0)]
(if (< i (count input))
(let [[min-elem min-pos] (find-min-and-position-in-vector mv i)]
(if (not= min-elem (mv i))
(recur (swap-arr mv i min-pos),
(inc i),
(inc swap-count))
(recur mv,
(inc i),
swap-count)))
swap-count)))

若要了解程序中的性能瓶颈在哪里，最好使用 https://github.com/clojure-goes-fast/clj-async-profiler 而不是猜测。

请注意我是如何从您的代码中删除unchecked-*内容。它在这里并不那么重要，而且很容易出错。如果要使用它们来提高性能，请确保使用反编译器检查生成的字节码：https://github.com/clojure-goes-fast/clj-java-decompiler

在java中类似的实现，运行的时间几乎只有一半。

这对Clojure来说实际上是相当不错的，因为你使用不可变的向量，而在Java中你可能使用数组。将 Clojure 解决方案重写为数组后，性能几乎相同。