从嵌套结构中选择与Clojure中的条件匹配的元素

Question

我最近发现了Specter库，它提供了数据结构导航和转换功能，并使用Clojure编写。

实施一些API作为学习练习似乎是一个好主意。幽灵实现的API拍摄功能和嵌套结构作为参数，并返回满足该功能如下面从嵌套结构元素的向量：

(select (walker number?) [1 :a {:b 2}]) =>[1 2]

下面是我在实现的功能的尝试与类似的API：

(defn select-walker [afn ds] 
    (vec (if (and (coll? ds) (not-empty ds)) 
     (concat (select-walker afn (first ds)) 
       (select-walker afn (rest ds))) 
     (if (afn ds) [ds])))) 

(select-walker number? [1 :a {:b 2}]) =>[1 2]

我试图实现select-walker，使用list comprehension,looping，并使用cons和conj。在所有这些情况下，返回值是一个嵌套列表，而不是元素的平面向量。

然而，我的实现似乎不像惯用的Clojure，并且时间和空间复杂性很差。

(time (dotimes [_ 1000] (select (walker number?) (range 100)))) 
"Elapsed time: 19.445396 msecs" 

(time (dotimes [_ 1000] (select-walker number? (range 100)))) 
"Elapsed time: 237.000334 msecs" 

请注意，我的实施比Spectre的实施慢大约12倍。

我对实施select-walker有三个问题。

1. 是否可以使用尾递归实现select-walker？
2. 可以select-walker写成更习惯Clojure？
3. 任何提示使select-walker执行得更快？

Answer 1

1. 至少有两种可能性，使之尾递归。第一个是循环来处理数据是这样的：

   (defn select-walker-rec [afn ds] 
       (loop [res [] ds ds] 
       (cond (empty? ds) res 
         (coll? (first ds)) (recur res 
               (doall (concat (first ds) 
                   (rest ds)))) 
         (afn (first ds)) (recur (conj res (first ds)) (rest ds)) 
         :else (recur res (rest ds))))) 
   

   在REPL：

   user> (select-walker-rec number? [1 :a {:b 2}]) 
   [1 2] 
   
   user> user> (time (dotimes [_ 1000] (select-walker-rec number? (range 100)))) 
   "Elapsed time: 19.428887 msecs" 
   

   （简单的选择 - 沃克作品200ms左右对我来说）

   第二个（较慢不过，更适合更困难的任务）是使用zippers：

   (require '[clojure.zip :as z]) 
   
   (defn select-walker-z [afn ds] 
       (loop [res [] curr (z/zipper coll? seq nil ds)] 
       (cond (z/end? curr) res 
         (z/branch? curr) (recur res (z/next curr)) 
         (afn (z/node curr)) (recur (conj res (z/node curr)) 
               (z/next curr)) 
         :else (recur res (z/next curr))))) 
   
   user> (time (dotimes [_ 1000] (select-walker-z number? (range 100)))) 
   "Elapsed time: 219.015153 msecs" 
   

   这一个真的很慢，因为拉链在更复杂的结构上运行。这很棒的力量为这个简单的任务带来了不必要的开销。

2. 最惯用的方法，我想，就是用tree-seq：

   (defn select-walker-t [afn ds] 
       (filter #(and (not (coll? %)) (afn %)) 
         (tree-seq coll? seq ds))) 
   
   user> (time (dotimes [_ 1000] (select-walker-t number? (range 100)))) 
   "Elapsed time: 1.320209 msecs" 
   

   这是令人难以置信的快速的，因为它产生的结果的一个懒惰的序列。事实上，你应该认识到它的数据对考试公平：

   user> (time (dotimes [_ 1000] (doall (select-walker-t number? (range 100))))) 
   "Elapsed time: 53.641014 msecs" 
   

   一两件事要注意这个变种，就是它不是尾递归，所以它会在真正的深度嵌套结构的情况下，失败（也许我我错了，但我想这是关于几千层嵌套），但它仍然适用于大多数情况。