2

我有一个函数可以找到图中节点之间的最小距离，用 Ruby 编写。我把它翻译成 Clojure，但在我看来它看起来很糟糕。

数据的表示如下所示：

hash = {:v0 [:v1  :v2  :v3]
        :v1 [:v4  :v5  :v6] 
        :v2 [:v7  :v8  :v9]
        :v3 [:v10 :v11 :v12]
        :v4 [:v13 :v14 :v15]}

Ruby 函数如下所示：

 def distance src, target, hash
    return 0 if src == target
    return nil if hash[src].nil?
    dist = 1

    if hash[src].include? target
        return dist
    else
        arr = hash[src].map {|x| distance x, target, hash}
    end
    arr = arr.delete_if {|x| x.nil?}

    return dist + arr.min if !arr.empty?
    return nil
end

Clojure 函数如下所示：

(use 'clojure.contrib.seq-utils)
(defn distance [src target h] 
  (if (= src target)
    0
    (if (nil? (h src))
      nil
      (if (includes? (h src) target)
        1
        (let [arr (filter #(not= % nil) (map #(distance % target h) (h src)))]
          (if (= (empty? arr) true)
            nil
            (+ 1 (apply min arr))))))))

你能告诉我一种更优雅、更类似于 Clojure 的方式吗？那些嵌套的 if 很糟糕。

4

5 回答 5

3

如果您使用集合而不是向量并使用cond而不是嵌套if的 s，至少对我来说，它看起来更像 Clojure：

(def h {:v0 #{:v1  :v2  :v3}
        :v1 #{:v4  :v5  :v6}
        :v2 #{:v7  :v8  :v9}
        :v3 #{:v10 :v11 :v12}
        :v4 #{:v13 :v14 :v15}})

(defn distance [src target h]
  (cond (= src target) 0
        (nil? (h src))  nil
        (contains? (h src) target)
         :default (let [arr (filter #(not= % nil) (map #(distance % target h) (h src)))]
                   (if (empty? arr)
                     nil
                     (inc (apply min arr))))))

还值得注意的是，clojure.contrib 现在已经过时了。删除它允许此代码在大多数任何版本的 Clojure 上运行。

于 2013-02-12T19:25:00.730 回答
2

注意到filter生成惰性序列可以通过删除if. 此外，contains?也可以省略，但在这种情况下增加可读性是有争议的。

(defn distance [src target h]
  (let [arr (filter #(not= % nil) (map #(distance % target h) (h src)))]
    (cond (= src target)   0
          (nil? (h src))   nil
          ((h src) target) 1
          (empty? arr)     nil
          :else            (+ 1 (apply min arr)))))
于 2013-02-12T19:36:13.843 回答
1

如果你感觉 seq-y：

(defn distance [src target h] 
  (if (= src target)
    0
    (->> src h
      (keep #(distance % target h))
      (map inc)
      (reduce #(if %1 (min %1 %2) %2) nil))))
于 2013-02-13T15:38:56.457 回答
1

无需任何算法更改，您就可以大大缩短代码（内联注释）：

(defn distance [src target h] 
  (if (= src target)
    0
    (when (h src) ; nil is "falsy" so no need to check for it.
                   ; when's else evaluates to nil
      (if (includes? (h src) target)
        1
        (let [arr (keep #(distance % target h) (h src))] ; keep is same as map but drops nils
          (when-not (empty? arr) ; Same as above. Also empty? returns true or false.
            (inc (apply min arr)))))))) ; inc is used to increment by one

这可以进一步缩短：

(let [arr (keep #(distance % target h) (h src))]
  (when-not (empty? arr)
    (inc (apply min arr))))

对此：

(when-let [arr (seq (keep #(distance % target h) (h src)))]
  (inc (apply min arr)))

因为seq返回nil空集合。

正如其他人已经提到的那样，现在使用 Contrib 并不是一个好主意。

于 2013-02-12T20:40:21.707 回答
0

另一个建议。计算所有路线，然后计算最小距离：

(defn routes
  ([src target m]
     (if (= src target)
       [[]]
       (seq (routes src target m []))))
  ([src target m so-far]
     (if-let [near (get m src)]
       (if (contains? near target)
         [(conj so-far target)]
         (mapcat #(routes % target m (conj so-far %)) near)))))

(defn min-distance [src target m]
  (if-let [all-routes (routes src target m)]
    (apply min (map count all-routes))))
于 2013-02-13T00:06:01.780 回答