Wählen Sie Elemente aus einer verschachtelten Struktur, die eine Bedingung in Clojure

Question

Ich entdeckte vor kurzem die Specter-Bibliothek, die Datenstruktur Navigation und Transformation Funktionen bietet und in Clojure geschrieben ist.

Die Implementierung einiger APIs als Lernübung schien eine gute Idee zu sein. Specter implementiert eine API eine Funktion und eine verschachtelte Struktur als Argument und gibt einen Vektor von Elementen aus der verschachtelten Struktur nehmen, die die Funktion wie unten erfüllt:

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

Unten ist mein Versuch, eine Funktion bei der Umsetzung mit ähnlichen 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]

ich versucht habe, die Umsetzung select-walker unter Verwendung von list comprehension, looping und unter Verwendung von cons und conj. In allen diesen Fällen der Rückgabewert war eine verschachtelte Liste anstelle eines flachen Vektors von Elementen.

Doch meine Implementierung scheint nicht wie idiomatische Clojure und hat eine geringe Zeit und Raum Komplexität.

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

Beachten Sie, dass meine Implementierung ist etwa 12-mal langsamer als Spectre-Implementierung.

Ich habe drei Fragen zur Umsetzung von select-walker.

1. Ist eine tail-rekursive Implementierung von select-walker möglich?
2. Kann select-walker in idiomatischer Clojure geschrieben werden?
3. Alle Hinweise zu machen select-walker führen schneller?

Answer 1

1. gibt es mindestens zwei Möglichkeiten, die es Schwanz rekursiv zu machen. Erstens ist ein Daten in der Schleife wie folgt zu verarbeiten:

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

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

   (einfache select-Walker arbeitet etwa 200 ms für mich)

   die zweite (langsamer aber, und besser geeignet für den schwierigeren Aufgaben) verwenden 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" 
   

   dieses ist wirklich langsam, da der Reißverschluss auf komplexere Strukturen wirkt. Es ist eine große Macht, die unnötigen Aufwand für diese einfache Aufgabe bringt.

2. die idiomatische Ansatz ich denke, ist tree-seq zu verwenden:

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

   es unglaublich schnell ist, da es eine faule Folge von Ergebnissen führt. In der Tat sollen Sie ihre Daten für den fairen Test realisieren:

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

   noch etwas über diese Variante zu bemerken, ist, dass es nicht Schwanz rekursiv ist, so ist es bei wirklich tief verschachtelten Strukturen scheitern würde (vielleicht i‘ Ich irre mich, aber ich denke, es ist ein paar tausend Ebenen der Verschachtelung), immer noch ist es für die meisten Fälle geeignet.