查找嵌套数据结构中第一次出现的路径
Find Path to the First Occurrence in a Nested Data Structure
考虑以下由向量嵌套在树结构中的数字
(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]
但是,我仍然很想知道这里可以优化什么。它对我来说仍然很复杂,而且还不是尾递归。
这是一个选项。这个想法是在遍历列表时保留 "stacktrace" 个索引(r
参数)。每次我们找到满足 p
谓词的项目时,我们 return 即 "stacktrace"。如果找到 none,我们只需 return nil。 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?))
这不是尾递归,但很简单:
(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
,因为在搜索树时还有其他合理的方法来定义"first"。
注意:我是 Clojure 的新手,我什至没有看过 clojure.walk or Specter。可能有更简单的方法。
这里有一个尾递归的方法:
(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
添加一个索引。这里要注意的主要技巧是使用 "failure continuation",由变量 fk
表示。 fk
是传递给 loop
的下一组参数,用于在子树搜索失败后继续搜索,如果搜索在顶层则为 nil。这可以在不违反尾递归的情况下进行回溯。换句话说,在非尾递归版本中,完成递归调用后剩下的工作所需的信息在尾递归版本的 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"
考虑以下由向量嵌套在树结构中的数字
(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]
但是,我仍然很想知道这里可以优化什么。它对我来说仍然很复杂,而且还不是尾递归。
这是一个选项。这个想法是在遍历列表时保留 "stacktrace" 个索引(r
参数)。每次我们找到满足 p
谓词的项目时,我们 return 即 "stacktrace"。如果找到 none,我们只需 return nil。 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?))
这不是尾递归,但很简单:
(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
,因为在搜索树时还有其他合理的方法来定义"first"。
注意:我是 Clojure 的新手,我什至没有看过 clojure.walk or Specter。可能有更简单的方法。
这里有一个尾递归的方法:
(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
添加一个索引。这里要注意的主要技巧是使用 "failure continuation",由变量 fk
表示。 fk
是传递给 loop
的下一组参数,用于在子树搜索失败后继续搜索,如果搜索在顶层则为 nil。这可以在不违反尾递归的情况下进行回溯。换句话说,在非尾递归版本中,完成递归调用后剩下的工作所需的信息在尾递归版本的 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"