懒散地将序列的多个连续项目折叠为单个项目的最佳方法

Question

[注意:标题和文本都经过大量编辑,以便更清楚地表明我不是特别在字符串之后,而是在一般序列之后,以及对它的延迟处理]

使用字符序列/字符串作为示例,假设我想要转换字符串

"\ ta\r \n\t\t\t\r \n \n \n\r \n \n \n \n"

成

"asdf"

更一般地说,我想将序列中的所有连续空格(或任何其他任意项目集合)转换为单个项目,并且懒得.

我已经提出了以下分区 - /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作为示例,但我真正想要的是任何类型的序列上的泛型函数,它会折叠任意数量的连续项,这些项是预定义项集的一部分,由一些单个项预定义项目.我特别感兴趣的是知道是否有更好的partition-by/mapcat替代品,如果可以针对'string'特殊情况进行优化,那就更好了.

更新2:

这是一个完全懒惰的版本 - 上面的一个并不是完全懒惰的,我担心,除了它正在做多余的is-wsp？检查.我概括了参数名称等,所以它看起来不像是一个你可以通过String.whatever()调用轻松替换的东西 - 它是关于任意序列的.

(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 [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 项测试中都表现出色。