查找路徑中嵌套數據結構

Question

考慮向量嵌套在一個樹結構

(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]]) 

我的目標是找到的路徑，可以通過找到的第一個偶數下面的數字中第一次出現遍歷樹：在上面的示例，這將是4，從根到該節點的路徑將是[2 3 0]

(def result [2 3 0]) 

我得到了一些困難寫壽存檔此功能。但是，下面的函數找到的第一個偶數，而不是它的路徑：

(defn find-even [x] 
    (if (vector? x) 
    (some #(when-let [subresult (find-even %)] 
      (when (even? subresult) 
       subresult)) x) 
    x)) 

(find-even tree) ;; 4 

我將不得不爲了接收路徑的結果呢？

---

編輯

我想出了一個辦法做到這一點。這是一個功能，至少 - 工作：

(defn find-even-path [x] 
    (letfn [(traverse [x] 
      (if (vector? x) 
       (some (fn [[i v]] (when-let [subresult (traverse v)] 
            (when (even? (:value subresult)) 
            (update subresult :path conj i)))) 
        (map-indexed vector x)) 
       {:path '() 
       :value x}))] 
    (when-let [result (traverse x)] 
     (vec (:path result))))) 

(find-even-path tree) ;; [2 3 0] 

但是，我仍然很好奇聽到什麼可以在這裏優化。它仍然看起來相當複雜，而且還不是尾遞歸。

Answer 1

這裏有一個辦法做到這一點尾遞歸：

(defn tailrec-depth-first-path [is? tree] 
    (loop [[tree i path fk] [tree 0 [] nil]] 
    (cond 
     (>= i (count tree)) 
     (if (nil? fk) nil (recur fk)) 
     (vector? (tree i)) 
     (recur [(tree i) 0 (conj path i) [tree (inc i) path fk]]) 
     (is? (tree i)) 
     (conj path i) 
     :else 
     (recur [tree (inc i) path fk])))) 

(tailrec-depth-first-path even? [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]]) 
=> [2 3 0] 

功能在每次進一步下降而那棵樹時增添了一個指數path。這裏要說明的主要技巧是使用「失敗延續」，由變量fk表示。 fk是下一組參數，傳遞給loop以在子樹搜索失敗後繼續搜索，如果搜索位於頂層，則爲零。這可以在不違反尾遞歸的情況下進行回溯。換句話說，在遞歸調用後剩餘工作所需的非尾尾遞歸版本信息將在尾遞歸版本fk中累積。

---

快速測試對我2009年的MacBook Air（1.86 GHz的Core 2 Duo處理器）表明，尾遞歸版本是最快的，到目前爲止公佈的答案：

(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]]) 

(time (dotimes [_ 100000] (find-even-path tree))) 
"Elapsed time: 1153.137475 msecs" 

(time (dotimes [_ 100000] (first (findt tree even? [])))) 
"Elapsed time: 1413.502082 msecs" 

(time (dotimes [_ 100000] (depth-first-path even? tree))) 
"Elapsed time: 690.56115 msecs" 

(time (dotimes [_ 100000] (tailrec-depth-first-path even? tree))) 
"Elapsed time: 524.332278 msecs" 

Answer 2

這是一個選項。這個想法是在遍歷列表時保持索引的「堆棧跟蹤」（參數r）。每次我們找到一個滿足謂詞的項目時，我們都會返回「堆棧跟蹤」。如果沒有找到，我們只返回零。 mapcat會連接所有的非空（非空）列出了到一個結果列表：

(defn findt [t p r] 
    (mapcat (fn[i c] 
      (if (coll? c) 
       (findt c p (cons i r)) 
       (when (p c) [(reverse (cons i r))]))) (range) t)) 

它仍然不是尾遞歸，但它可以找到的所有路徑（懶洋洋地，由於使用的mapcat）：

(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]]) 

(findt tree even? []) 
=> ((2 3 0) (2 3 1) (4 0)) 

而且我們可以測試它：

(->> (findt tree odd? []) 
(map #(get-in tree %)) 
(every? odd?)) 

Answer 3

這不是尾遞歸，但它是直截了當：

(defn depth-first-path 
([is? tree] 
    (depth-first-path is? tree [])) 
([is? tree path-so-far] 
    (cond 
    (vector? tree) 
     (some identity (map #(depth-first-path is? %1 (conj path-so-far %2)) 
          tree 
          (range))) 
    (is? tree) 
     path-so-far 
    :else 
     nil))) 

(depth-first-path even? [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]]) 
=> [2 3 0] 

我把它叫做depth-first-path因爲有其他合理的方法來定義「第一」搜索一棵樹的時候。

注意：我是Clojure的新手，我甚至沒有看過clojure.walk或Specter。可能有一種更簡單的方法。