Clojure:尾递归以获取 trie 的叶子计数

Question

我有一个使用 HashMap 的特里数据结构。我想计算它的叶子，但我的尾递归太慢:我认为我使用了错误的数据结构。请帮忙。

我认为(vec trie)部分很愚蠢，请纠正我!

特里结构定义

(defn add-to-trie [trie x]
  (assoc-in trie x (merge (get-in trie x) {:terminal true})))

所以字典树会是这样的:

(def trie 
  (reduce add-to-trie {} (map #(re-seq #"\S" (.trim %1)) ["x" "y" "abt" "act"])))

{"a" {"c" {"t" {:terminal true}}, 
      "b" {"t" {:terminal true}}},
 "y" {:terminal true},
 "x" {:terminal true}}

递归版本

我解决了一个递归问题:

(defn terminal-count [root] 
  (if (:terminal root) 
    (+ 1 (terminal-count (dissoc root :terminal)))
    (apply + (map terminal-count (vals root)))))

丑陋的尾递归

(defn terminal-count2 [trie] 
  (loop [cnt 0 nodes (vec trie)] 
    (cond 
      (empty? nodes) cnt 
      :else          (let [des (val (last nodes))]
                       (cond 
                         (map? des) (recur cnt (vec (concat (pop nodes) des)))
                         :else      (recur (inc cnt) (pop nodes)))))))

我发现在 13 万个 8~16 个字符串上，第二个比第一个慢 30 倍。我必须使用错误的数据结构(我认为将 trie 转换为 vec 很难看)或者做了愚蠢的事情。

PS。使用向量作为队列是不好的做法，这是我问题的关键点吗？

Answer 1

事实上，我们可以假设持久数据结构不能为这种计算提供最佳性能。

我可以建议改用 transients ，简而言之，它们是 Clojure 集合的可变实现。这将导致如下结果:

(defn terminal-count-transient [trie] 
  (loop [cnt 0,nodes (transient (vec trie))] 
    (cond (t-empty? nodes) cnt 
          :else (let [des (val (t-last nodes))
                      remaining-nodes (pop! nodes)] 
                  (cond 
                    (map? des) (recur cnt, (reduce conj! remaining-nodes des)) 
                    :else (recur (inc cnt) remaining-nodes))))))

我为 transient 向量定义了 2 个辅助函数 t-last 和 t-empty?(并非 Clojure 集合的所有读取接口(interface)都已扩展到 transient 尚未):

(defn t-empty? [t-vec]
  (= (count t-vec) 0))

(defn t-last [t-vec]
  (t-vec (dec (count t-vec))))

我不能假装这是最佳的，但在我的机器上，它的性能比您上面定义的递归版本好两倍。

我能想到的其他选择是:

• 利用懒惰。 (根据我的尝试，您可以轻松地得到比递归版本“仅”慢两倍的东西)。例如，您可以定义一个返回叶子的惰性序列的函数，然后对其进行计数。
• 使用常规的可变 Java 队列，例如 java.util.ArrayDeque。使用起来可能比较重，但速度相当快。