从树迭代构造 Trie
Iteratively Construct Trie from a Tree
简介
以下函数迭代遍历由嵌套向量构成的树结构。它根据谓词测试每个叶子。通过真值测试的所有叶子的路径在 Trie structure 中返回。后者以非冗余方式描述所有找到的路径。
(defn get-trie-of-matches [is? tree]
(loop [[tree i path fk] [tree 0 [] nil]
accum {}]
(cond
(>= i (count tree)) ;; end of level / go up
(if (nil? fk) accum (recur fk accum))
(vector? (tree i)) ;; level down
(recur [(tree i) 0 (conj path i) [tree (inc i) path fk]] accum)
(is? (tree i)) ;; match
(let [new-accum (assoc-in accum (conj path i) {})]
(recur [tree (inc i) path fk] new-accum))
:else ;; next on same level
(recur [tree (inc i) path fk] accum))))
有关进一步的说明,请参阅 。
例子
考虑下面的树
(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]])
应用于函数,使用even?
作为谓词:
(get-trie-of-matches even? tree)
=> {2 {3 {0 {}, 1 {}}}, 4 {0 {}}}
结果描述了tree
中偶数的三个路径。即 2-3-0
、2-3-1
和 4-0
.
问题
尽管上述功能有效,但可能有更好的方法在遍历树时构造 Trie。目前哈希映射被淹没。通过 assoc-in 在每场比赛中。该算法逐层相对地遍历树结构,但以全局方式将每条路径附加到 accum
,这不是必需的。此外,由于使用了哈希图,因此此方法才有可能。无论如何,为 Trie 使用顺序数据结构可能会更好,以促进对其的进一步迭代。无法采用上述方法。
问题
如何在上述函数 get-trie-of-matches
中创建 Trie,而不依赖于散列图特定 'global' 'write' 函数?
我建议看一下 clojure 的 walk
api.
它允许您递归地将某些函数应用于嵌套集合。
在这种情况下,您可以使用 postwalk
:
user> (require '[clojure.walk :as w])
user> (w/postwalk-demo [1 3 [4 [6] 7] [[8]]])
Walked: 1
Walked: 3
Walked: 4
Walked: 6
Walked: [6]
Walked: 7
Walked: [4 [6] 7]
Walked: 8
Walked: [8]
Walked: [[8]]
Walked: [1 3 [4 [6] 7] [[8]]]
[1 3 [4 [6] 7] [[8]]]
关键是你可以在每一步替换任何项目:
user> (w/postwalk #(if (coll? %) (reverse %) (inc %))
[1 3 [4 [6] 7] [[8]]])
(((9)) (8 (7) 5) 4 2)
这里我们递增所有数字,并反转所有集合,保持嵌套结构。
现在申请你的任务:
你可以遍历你的树,只保留偶数的索引而不是空集合(例如包含偶数的集合,而不是空集合):
;; helper function
(defn empty-coll? [item]
(and (coll? item) (not (seq item))))
(defn make-trie [pred tree]
(w/postwalk
#(if (coll? %)
(keep-indexed (fn [idx item]
(cond (empty-coll? item) nil
(coll? item) (list idx item)
item idx
:else nil))
%)
(pred %))
tree))
回复:
user> (def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]])
#'user/tree
user> (make-trie even? tree)
((2 ((3 (0 1)))) (4 (0)))
user> (make-trie #(> % 7) tree)
(1 (2 ((3 (2)) 4)) (4 (2 3)))
结构与您的地图相似。事实上,您可以通过对函数进行微小的更改来生成您想要的任何结构,例如您的地图结构:
(defn make-trie-map [pred tree]
(w/postwalk
#(if (coll? %)
(into {}
(keep-indexed (fn [idx item]
(cond (empty-coll? item) nil
(coll? item) {idx item}
item {idx {}}
:else nil))
%))
(pred %))
tree))
user> (make-trie-map even? tree)
{2 {3 {0 {}, 1 {}}}, 4 {0 {}}}
简介
以下函数迭代遍历由嵌套向量构成的树结构。它根据谓词测试每个叶子。通过真值测试的所有叶子的路径在 Trie structure 中返回。后者以非冗余方式描述所有找到的路径。
(defn get-trie-of-matches [is? tree]
(loop [[tree i path fk] [tree 0 [] nil]
accum {}]
(cond
(>= i (count tree)) ;; end of level / go up
(if (nil? fk) accum (recur fk accum))
(vector? (tree i)) ;; level down
(recur [(tree i) 0 (conj path i) [tree (inc i) path fk]] accum)
(is? (tree i)) ;; match
(let [new-accum (assoc-in accum (conj path i) {})]
(recur [tree (inc i) path fk] new-accum))
:else ;; next on same level
(recur [tree (inc i) path fk] accum))))
有关进一步的说明,请参阅
例子
考虑下面的树
(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]])
应用于函数,使用even?
作为谓词:
(get-trie-of-matches even? tree)
=> {2 {3 {0 {}, 1 {}}}, 4 {0 {}}}
结果描述了tree
中偶数的三个路径。即 2-3-0
、2-3-1
和 4-0
.
问题
尽管上述功能有效,但可能有更好的方法在遍历树时构造 Trie。目前哈希映射被淹没。通过 assoc-in 在每场比赛中。该算法逐层相对地遍历树结构,但以全局方式将每条路径附加到 accum
,这不是必需的。此外,由于使用了哈希图,因此此方法才有可能。无论如何,为 Trie 使用顺序数据结构可能会更好,以促进对其的进一步迭代。无法采用上述方法。
问题
如何在上述函数 get-trie-of-matches
中创建 Trie,而不依赖于散列图特定 'global' 'write' 函数?
我建议看一下 clojure 的 walk
api.
它允许您递归地将某些函数应用于嵌套集合。
在这种情况下,您可以使用 postwalk
:
user> (require '[clojure.walk :as w])
user> (w/postwalk-demo [1 3 [4 [6] 7] [[8]]])
Walked: 1
Walked: 3
Walked: 4
Walked: 6
Walked: [6]
Walked: 7
Walked: [4 [6] 7]
Walked: 8
Walked: [8]
Walked: [[8]]
Walked: [1 3 [4 [6] 7] [[8]]]
[1 3 [4 [6] 7] [[8]]]
关键是你可以在每一步替换任何项目:
user> (w/postwalk #(if (coll? %) (reverse %) (inc %))
[1 3 [4 [6] 7] [[8]]])
(((9)) (8 (7) 5) 4 2)
这里我们递增所有数字,并反转所有集合,保持嵌套结构。
现在申请你的任务: 你可以遍历你的树,只保留偶数的索引而不是空集合(例如包含偶数的集合,而不是空集合):
;; helper function
(defn empty-coll? [item]
(and (coll? item) (not (seq item))))
(defn make-trie [pred tree]
(w/postwalk
#(if (coll? %)
(keep-indexed (fn [idx item]
(cond (empty-coll? item) nil
(coll? item) (list idx item)
item idx
:else nil))
%)
(pred %))
tree))
回复:
user> (def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]])
#'user/tree
user> (make-trie even? tree)
((2 ((3 (0 1)))) (4 (0)))
user> (make-trie #(> % 7) tree)
(1 (2 ((3 (2)) 4)) (4 (2 3)))
结构与您的地图相似。事实上,您可以通过对函数进行微小的更改来生成您想要的任何结构,例如您的地图结构:
(defn make-trie-map [pred tree]
(w/postwalk
#(if (coll? %)
(into {}
(keep-indexed (fn [idx item]
(cond (empty-coll? item) nil
(coll? item) {idx item}
item {idx {}}
:else nil))
%))
(pred %))
tree))
user> (make-trie-map even? tree)
{2 {3 {0 {}, 1 {}}}, 4 {0 {}}}