查找嵌套数据结构中首次出现的路径 [英] 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]）
  

<我在编写一个函数时遇到了一些困难。但是，下面的函数会找到第一个偶数，而不是它的路径：

$ $ $ $ $ $ $ $ $ $ $ $ b（if（vector？x）
（some＃（when-let [subresult（find-even％）]
（when（even？subresult）
subresult））x）
x））

（find-even tree）;; 4

为了接收结果的路径，我需要做些什么？

---

编辑

想出了一个办法。这是一个至少可以工作的函数：

$ $ $ $ $ $ $ $ $ $ $ $ $（$）$（$ find $ even $ path $
letfn [（traverse [x]
（if（vector？x）
（some（fn [[iv]]（when-let [subresult（traverse v）]
（even （）：
（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]

然而，我仍然很想知道这里可以优化什么。它仍然看起来相当复杂，而且还不是尾递归。

解决方案

这是一种以尾递归方式完成它的方法：

 （defn tailrec-depth-first-path [is？tree] 
（loop [[tree i path fk] [树0 [] nil]] 
（cond 
（> = i（count tree））
（if（nil？fk）nil（recur fk））
向量？（树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] 
  

该函数为路径添加一个索引每次它在树下进一步下降。这里要说明的主要技巧是使用失败延续，由变量 fk 表示。 fk 是传递给循环的下一组参数，用于在子树搜索失败后继续搜索，或者如果搜索是在顶层，则为零。这可以在不违反尾递归的情况下进行回溯。换句话说，在递归调用之后剩余的工作需要在非尾递归版本中被使用的信息被累积在尾部的 fk 中我的2009款MacBook Air（1.86 GHz Core 2 Duo）的快速测试表明，对于我的2009 MacBook Air（1.86 GHz Core 2 Duo）递归版本是到目前为止发布的答案中最快的：

 （def tree [7 9 [7 5 3 [4 6 9 ]时间（dotimes [_ 100000]（find-even-path tree）））
已用时间：1153.137475 msecs 
 
（时间（dotimes [_ 100000]（第一个（findt tree even？[]））））
已用时间：1413.502082 msecs
 
 （dotimes [_100000]（深度优先路径偶数树）））
已用时间：690.56115 msecs
 
（时间（dotimes [_100000]第一路甚至是树）））
已用时间：524.332278 msecs
  

Consider the following numbers nested by vectors in a tree-structure

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

My goal is to find the path to the first even number that can be found by traversing the tree: In the upper example this would be 4, the path from the root to this node would be [2 3 0]

(def result [2 3 0])

I got some difficulties writing a function tho archive this. However, the following function finds the first even number, not its path:

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

(find-even tree) ;; 4   

What would I have to do in order to receive the path to the result?

---

EDIT

I figured out a way to do it. Here is a function that - at least - works:

(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]

However, I'd still be curious to hear what could be optimized here. It still looks quite complex to me and is not tail recursive yet.

解决方案

Here's a way to do it tail-recursively:

(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]

The function adds one more index to path each time it descends further down the tree. The main trick of note here is the use of a "failure continuation", represented by the variable fk. fk is the next set of arguments to pass to loop to continue the search after a failed search of a subtree, or nil if the search is at the top level. This enables backtracking without violating tail-recursion. In other words, the information that, in a non-tail-recursive version, would be needed to do the work remaining after the recursive call, is accumulated in fk in the tail-recursive version.

---

A quick test on my 2009 MacBook Air (1.86 GHz Core 2 Duo) suggests that the tail-recursive version is the fastest of the answers posted so far:

(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"

这篇关于查找嵌套数据结构中首次出现的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！