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し、ネストされたifsの代わりに使用すると、少なくとも私には、もう少し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生成することに気付くと、を削除することでパフォーマンスを犠牲にすることなく、ArthurUlfeldtの回答を少し単純化できます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

アルゴリズムを変更しなくても、コードをかなり短くすることができます（インラインでコメントします）。

(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 に答える
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 に答える
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 に答える