0

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

该代码有效，但求解 7 元素向量大约需要一秒钟，与 Java 中的类似解决方案相比，这非常糟糕。（已编辑）我已经尝试提供显式类型，但我尝试使用瞬态似乎没有什么不同，但是我在我的解决方案中使用了 subvec 的开放错误 - https://dev.clojure.org/jira /浏览/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])))
4

1 回答 1

0

您的解决方案中有一些可以改进的地方，包括算法和效率方面。主要的改进是在搜索时记住向量中的最小元素及其位置。这允许您不再使用 .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 解决方案重写为数组后，性能几乎相同。

于 2018-08-19T12:59:23.850 回答