2

整数のリストがあるとしましょう:1, 2, 5, 13, 6, 5, 7そして、繰り返される最初の数値を見つけて、2 つのインデックスのベクトルを返したいとします。私のサンプルでは、​​5 at[2, 5]です。私がこれまでに行ったことはloopですが、もっとエレガントに、手短にできるでしょうか?

(defn get-cycle
  [xs]
  (loop [[x & xs_rest] xs, indices {}, i 0]
    (if (nil? x)
      [0 i]  ; Sequence is over before we found a duplicate.
      (if-let [x_index (indices x)]
        [x_index i]
        (recur xs_rest (assoc indices x i) (inc i))))))

番号自体を返す必要はありません。インデックスで取得できるためです。次に、常にそこにあるとは限りません。

4

5 に答える 5

6

リスト処理を使用するオプションですが、それほど簡潔ではありません:

(defn get-cycle [xs]
  (first (filter #(number? (first %))
    (reductions
      (fn [[m i] x] (if-let [xat (m x)] [xat i] [(assoc m x i) (inc i)]))
      [(hash-map) 0] xs))))
于 2013-11-10T22:12:17.647 に答える
1

私はあなたが最初だけを求めたことを知っています。これは、ステップごとの割り当てオーバーヘッドがほとんどない、完全に遅延した実装です。

(defn dups
[coll]
(letfn [(loop-fn [idx [elem & rest] cached]
      (if elem
          (if-let [last-idx (cached elem)]
        (cons [last-idx idx]
              (lazy-seq (loop-fn (inc idx) rest (dissoc cached elem))))
        (lazy-seq (loop-fn (inc idx) rest (assoc cached elem idx))))))]
  (loop-fn 0 coll {})))

(first (dups v))
=> [2 5]

編集：ここにいくつかの基準ベンチマークがあります：

受け入れられた答え: 7.819269 µs

この回答(first (dups [12 5 13 6 5 7])): 6.176290 µs

速度: 5.841101 µs

最初の複製: 5.025445 µs

于 2013-11-11T03:33:05.240 に答える
0

実際、loopすべての重複を見つけたい場合を除き、かなり良い選択です。reduce必要でない場合でも、入力シーケンスのフルスキャンが発生するようなものです。

これが私のバージョンですget-cycle：

(defn get-cycle [coll]
  (loop [i 0 seen {} coll coll]
    (when-let [[x & xs] (seq coll)]
      (if-let [j (seen x)]
        [j i]
        (recur (inc i) (assoc seen x i) xs)))))

あなたとの唯一の違いは、重複がない場合にget-cycle私のバージョンが返されることです。nil

于 2013-11-10T22:23:32.917 に答える