Лучший способ лениво сворачивать несколько смежных элементов последовательности в один элемент

Question

[Примечание: заголовок и текст были сильно отредактированы, чтобы было яснее, что я не особенно после строк, но после общих последовательностей и их ленивой обработки]

Используя последовательность символов / строки в качестве примера, скажем, я хочу превратить строку как

"\ t a \ r s \ td \ t \ r \ n f \ r \ n"

в

"a s d f"

В более общих чертах я хочу превратить все непрерывные пробелы (или любой другой произвольный набор элементов) в последовательности в один элемент, и это лениво.

Я придумал следующую комбинацию partition-by / mapcat , но интересуюсь, есть ли более простые или иные лучшие способы (удобочитаемость, производительность, что угодно) для достижения того же самого.

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

В действии:

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

Обновление : В качестве примера я использовал строки / символьные последовательности / wsp, но на самом деле мне нужна универсальная функция для последовательностей любого типа, которая объединяет произвольное количество смежных элементов, которые являются частью предварительно определенного набора элементов, одним отдельным предопределенным элементом. , Мне особенно интересно узнать, есть ли лучшие альтернативы для секционирования по / mapcat, не так много, если это можно оптимизировать для особого случая 'string'.

Обновление 2 :

Вот полностью ленивая версия - я боюсь, что вышеприведенная не совсем ленивая, кроме того, что она делает избыточный is-wsp? чеки. Я обобщил имена параметров и т. Д., Чтобы это не выглядело просто как то, что вы можете легко заменить вызовом String.whwhat (), - это о произвольных последовательностях.

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

Это быстро, полностью лениво, но я бы хотел выразить это более кратко, так как сам я очень ленив.

Тесты ленивых сборщиков пока что : Легко ли судить о том, читается ли код или нет, посмотрев на код, но для того, чтобы увидеть, как они сравниваются с точки зрения производительности, вот мои критерии. Сначала я проверяю, выполняет ли функция то, что она должна делать, а затем выкладываю, сколько времени потребуется до

1. создать ленивый seq 1M раз
2. создайте ленивый seq и возьмите первый предмет 1M раз
3. создайте ленивый seq и возьмите второй предмет 1M раз
4. создайте ленивый seq и возьмите последний элемент (то есть полностью реализуйте ленивый seq) 1M раз

Тесты с 1 по 3 предназначены для того, чтобы хотя бы немного измерить лень. Я запускал тест пару раз, и не было значительных изменений во времени выполнения.

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"

Итог: лучший код самый медленный, самый уродливый код самый быстрый. Я почти уверен, что так не должно быть ...

Answer 1

Вот мое самое быстрое решение: (в основном то же, что и у М Смита, но без разрушения)

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

Вот более симпатичное решение, но в 3 раза (!) Медленнее: (фактически, то же, что и первоначальная версия 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))))

Вывод мини-теста ( полный код ):

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

Пример:

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

Используется для другого типа 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)

Полностью ленивый:

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

---

Старая версия с ошибками:

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

Ошибка в том, что он ест последовательные предметы, не соответствующие pred.

Answer 2

Это полностью ленивая реализация, которая немного чище:

<!-- 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 3

Почему бы просто не использовать функцию String Java replaceAll?

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

Я думаю, что она сильно оптимизирована для таких операций ...

Обновление : обновленная версия ответа после уточнения:

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

Он также работает с другими последовательностями:

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

Другой оптимизацией производительности может быть использование переходных процессов вместо стандартных последовательностей ...

Answer 4

Полностью ленивое решение, написанное в рекурсивном стиле:

(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 - это список, p - это предикат, а v - это значение для замены подпоследовательностей, которые соответствуют предикату.

Если вы стремитесь к чистой скорости за счет читабельности, вы можете сделать это:

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

Возможно, есть способ сделать это более читабельным. Очень хорошо справляется со всеми 4 тестами.

Answer 5

Строки в clojure являются Java-строками, поэтому вы не можете лениво создавать String (это означает, что вам нужно использовать весь ввод для построения строки).1003 *

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

здесь можно использовать строку или seq в качестве входных данных, поскольку remove вызывает seq для своего последнего аргумента.