Najlepszy sposób na leniwe zwijanie wielu przylegających elementów sekwencji do pojedynczego elementu

Question

[Uwaga: Tytuł i tekst były mocno edytowane, aby było bardziej zrozumiałe, że nie jestem szczególnie po ciągach, ale po ogólnych sekwencjach i leniwym przetwarzaniu sama]

Korzystanie sekwencje znaków/ciągi jako przykład, że chcę zamienić ciąg jak

„\ ta \ r           s \ td \ t \ r \ n                   f \ r \ n”

do

"asdf"

W kategoriach bardziej ogólnych, chce się wyłączyć wszystkie sąsiadujące ze sobą odstępy (lub innego arbitray zestaw przedmiotów) w sekwencji w pojedynczy przedmiot, i to leniwie.

Wpadłem na następujący zestaw partition-by/mapcat combo, ale zastanawiam się, czy istnieją łatwiejsze lub w inny sposób lepsze sposoby (czytelność, wydajność, cokolwiek), aby osiągnąć to samo.

(defn is-wsp? 
    [c] 
    (if (#{\space \tab \newline \return} c) true)) 

(defn collapse-wsp 
    [coll] 
    (mapcat 
    (fn [[first-elem :as s]] 
    (if (is-wsp? first-elem) [\space] s)) 
    (partition-by is-wsp? coll))) 

w akcji:

=> (apply str (collapse-wsp "\t a\r   s\td \t \r \n   f \r\n")) 
" a s d f " 

aktualizacji: użyłem strun/sekwencje znaków/WSP, jako przykład, ale to, co rzeczywiście chcesz to ogólna funkcja na sekwencjach dowolnego typu, które zwija dowolne liczby sąsiednich elementów, które są częścią wstępnie zdefiniowanego zestawu elementów, za pomocą jakiegoś pojedynczego predefiniowanego elementu. Szczególnie interesuje mnie, czy istnieją lepsze alternatywy dla partition-by/mapcat, nie tak bardzo, jeśli można to zoptymalizować dla specjalnego przypadku 'string'.

Aktualizacja 2:

Oto całkowicie leniwy wersja - ten powyżej, nie jest w pełni leniwy, obawiam się, oprócz tego, że robi się zbędne IS-WSP? czeki. Uogólniłem nazwy parametrów itp., Więc nie tylko wygląda to na coś, co można łatwo zastąpić wywołaniem String.whatever() - chodzi o arbitralne sekwencje.

(defn lazy-collapse 
    ([coll is-collapsable-item? collapsed-item-representation] (lazy-collapse coll is-collapsable-item? collapsed-item-representation false)) 
    ([coll is-collapsable-item? collapsed-item-representation in-collapsable-segment?] 
    (let [step (fn [coll in-collapsable-segment?] 
       (when-let [item (first coll)] 
       (if (is-collapsable-item? item) 
        (if in-collapsable-segment? 
        (recur (rest coll) true) 
        (cons collapsed-item-representation (lazy-collapse (rest coll) is-collapsable-item? collapsed-item-representation true))) 
        (cons item (lazy-collapse (rest coll) is-collapsable-item? collapsed-item-representation false)))))] 
    (lazy-seq (step coll in-collapsable-segment?))))) 

ten jest szybki, w pełni leniwy, ale chciałbym być w stanie wyrazić, że bardziej zwięźle, ponieważ jestem dość leniwy siebie.

Wzorce leniwych collapsers dotychczas: czy kod jest czytelny lub nie jest łatwo ocenić, patrząc na kod, ale żeby zobaczyć ich porównanie pod względem wydajności, tutaj są moje benchmarków.I najpierw sprawdzić, czy funkcja robi to, co ma robić, a potem wypluć jak długo to trwa do

1. utworzyć leniwy nast 1M razy
2. utworzyć leniwy nast i wziąć pierwszy element 1M razy
3. utworzyć leniwy nast i wziąć drugi element 1M razy
4. utworzyć leniwy nast i wziąć ostatni element (czyli w pełni uświadomić sobie leniwe nast) 1M razy

prób od 1 do 3 są przeznaczone do miernika lenistwo co najmniej li trochę. Przeprowadziłem test kilka razy i nie było żadnych znaczących zmian w czasach wykonania.

user=> (map 
    (fn [collapse] 
    (println (class collapse) (str "|" (apply str (collapse test-str is-wsp? \space)) "|")) 
    (time (dotimes [_ 1000000] (collapse test-str is-wsp? \space))) 
    (time (dotimes [_ 1000000] (first (collapse test-str is-wsp? \space)))) 
    (time (dotimes [_ 1000000] (second (collapse test-str is-wsp? \space)))) 
    (time (dotimes [_ 1000000] (last (collapse test-str is-wsp? \space))))) 
    [collapse-overthink collapse-smith collapse-normand lazy-collapse]) 

user$collapse_overthink | a s d f | 
"Elapsed time: 153.490591 msecs" 
"Elapsed time: 3064.721629 msecs" 
"Elapsed time: 4337.932487 msecs" 
"Elapsed time: 24797.222682 msecs" 

user$collapse_smith | a s d f | 
"Elapsed time: 141.474904 msecs" 
"Elapsed time: 812.998848 msecs" 
"Elapsed time: 2112.331739 msecs" 
"Elapsed time: 10750.224816 msecs" 

user$collapse_normand | a s d f | 
"Elapsed time: 314.978309 msecs" 
"Elapsed time: 1423.779761 msecs" 
"Elapsed time: 1669.660257 msecs" 
"Elapsed time: 8074.759077 msecs" 

user$lazy_collapse | a s d f | 
"Elapsed time: 169.906088 msecs" 
"Elapsed time: 638.030401 msecs" 
"Elapsed time: 1195.445016 msecs" 
"Elapsed time: 6050.945856 msecs" 

Konkluzja tej pory: Najpiękniejszy kod jest najwolniejsza, najbrzydszy kod jest najszybszy. Jestem prawie pewien, że to nie musi tak być ...

Answer 1

W pełni leniwy rozwiązanie, napisane w stylu rekurencyjnego:

(defn collapse [l p v] 
    (cond 
    (nil? (seq l)) 
    nil 
    (p (first l)) 
    (lazy-seq (cons v (collapse (drop-while p l) p v))) 
    :otherwise 
    (lazy-seq (cons (first l) (collapse (rest l) p v))))) 

l lista, p jest orzecznikiem i v jest wartością zastąpić krótsze sekwencje, które pasują do orzecznik z.

Jeśli jesteś po czystej prędkości kosztem czytelności, można to zrobić:

(defn collapse-normand2 
    ([l p v] 
    (lazy-seq (collapse-normand2 (seq l) p v nil))) 
    ([l p v _] 
    (when l 
     (lazy-seq 
     (let [f (first l) 
       r (next l)] 
      (if (p f) 
      (cons v (collapse-normand2 r p v nil nil)) 
      (cons f (collapse-normand2 r p v nil))))))) 
    ([l p v _ _] 
    (when l 
     (lazy-seq 
     (let [f (first l) 
       r (next l)] 
      (if (p f) 
      (collapse-normand2 r p v nil nil) 
      (collapse-normand2 r p v nil))))))) 

Jest prawdopodobnie sposobem, aby to bardziej czytelne. Działa bardzo dobrze na wszystkich 4 testach.

Answer 2

Dlaczego po prostu nie używać funkcji String Javy replaceAll?

user=> (.replaceAll "\t a\r   s\td \t \r \n   f \r\n" "\\s+" " ") 
" a s d f " 

myślę, że to mocno zoptymalizowany dla takich operacji ...

Aktualizacja: zaktualizowana wersja odpowiedzi po wyjaśnienia:

(defn is-blank? [^Character c] (not (nil? (#{\space \tab \newline \return} c)))) 

(defn collapse [coll fun replacement] 
    (first (reduce (fn [[res replaced?] el] 
        (if (fun el) 
        (if replaced? 
         [res replaced?] 
         [(conj res replacement) true]) 
        [(conj res el) false])) 
       [[] false] coll))) 

(def aa-str "\t a\r   s\td \t \r \n   f \r\n") 

user> (apply str (collapse aa-str is-blank? \space)) 
" a s d f " 

Współpracuje również z innymi seqs:

user> (collapse [1 1 2 3 1 1 1 4 5 6 1 1] #(= % 1) 9) 
[9 2 3 9 4 5 6 9] 

Kolejny optymizat wydajności jon może być użyty transjentów zamiast standardowych sekwencji ...

Answer 3

Łańcuchy w clojure są ciągami Java, więc nie można tworzyć leniwie String (co oznacza, że ​​trzeba zużywać wszystkie dane wejściowe, aby zbudować ciąg znaków).

Można utworzyć sekwencję znaków leniwie, choć:

USER> (remove #(Character/isWhitespace %) "\t a\r   s\td \t \r \n   f \r\n") 
(\a \s \d \f) 

można użyć ciąg lub nast jako wejście tutaj, ponieważ usuwać rozmowy nast od jego ostatniego argumentu.

Answer 4

Jest to całkowicie leniwy realizacja czyli nieco czystsze:

<!-- language: lang-clojure --> 
(defn collapse [ss pred replacement] 
    (lazy-seq  
      (if-let [s (seq ss)] 
       (let [[f & rr] s] 
       (if (pred f) 
        (cons replacement (collapse (drop-while pred rr) pred replacement)) 
        (cons f (collapse rr pred replacement))))))) 

Answer 5

Oto mój najszybszym rozwiązaniem do tej pory: (w zasadzie takie same jak M Smitha, ale nie rozpad)

(defn collapse [xs pred rep] 
    (when-let [x (first xs)] 
    (lazy-seq 
     (if (pred x) 
     (cons rep (collapse (drop-while pred (rest xs)) pred rep)) 
     (cons x (collapse (rest xs) pred rep)))))) 

Oto ładniejsze rozwiązanie, ale 3x (!) Wolniejsze: (w rzeczywistości takie samo jak w pierwotnej wersji SuperHorst ...)

(defn collapse [col pred rep] 
    (let [f (fn [[x & more :as xs]] (if (pred x) [rep] xs))] 
    (mapcat f (partition-by #(if (pred %) true) col)))) 

Mini odniesienia (full code) Wydajność:

$ clj collapse.clj 
    SuperHorst: "Elapsed time: 58535.737037 msecs" 
     Overthink: "Elapsed time: 70154.744605 msecs" 
     M Smith: "Elapsed time: 89484.984606 msecs" 
    Eric Normand: "Elapsed time: 83121.309838 msecs" 

przykład:

(def test-str "\t a\r  s\td \t \r \n   f \r\n") 
(def is-ws? #{\space \tab \newline \return}) 

user=> (apply str (collapse test-str is-ws? \space)) 
" a s d f " 

stosowane w innego typu SEQ:

user=> (collapse (range 1 110) #(= 2 (count (str %))) \X) 
(1 2 3 4 5 6 7 8 9 \X 100 101 102 103 104 105 106 107 108 109) 

Jest w pełni leniwa :

user=> (type (collapse test-str is-ws? \space)) 
clojure.lang.LazySeq 
user=> (type (collapse (range 1 110) #(= 2 (count (str %))) \X)) 
clojure.lang.LazySeq 

---

Stara wersja buggy:

(defn collapse-bug [col pred rep] 
    (let [f (fn [x] (if (pred x) rep x))] 
    (map (comp f first) (partition-by f col)))) 

Bug jest to, że zjada sąsiadujące pozycje nie pasujące pred.