我发现split-with实际被实现为[(take-while pred coll) (drop-while pred coll)],这意味着它会为每个满足条件的元素应用谓词两次,从而进行大量的冗余工作。
以下代码模拟了一个昂贵的谓词,它耗时800+ ms并打印 0 1 2 3 0 1 2 3
(time
(mapv doall
(let [xs (range 10)
pred #(do (println %) (Thread/sleep 100) (< % 3))]
(split-with pred xs))))
有没有什么原因让它不能更高效地实现,以避免这些冗余评估呢?
这是我尝试的一种实现方法 - 注意,一旦实现 `drops` 的单个元素,`takes` 就会被完全实现,但反之则不然。
(defn split-with*
"Like `split-with` but evaluates `pred` at most once on each element"
[pred coll]
(let [takes (take-while pred coll)
drops (lazy-seq (drop (count takes) coll))]
[takes drops]))
附加背景信息
这将是一个破坏性变更,对于当前代码涉及到谓词的副作用并依赖于它运行两次的情况。
但这从某种程度上讲是一个坏主意 - 例如,以下具有副作用的代码违反了 `split-with` 确实将集合分成两部分的合理假设。
由于惰性,结果还取决于哪个序列首先被实现。
(let [xs (range 10)
counter (atom 1)
pred (fn [x] (< x (swap! counter + 1/2)))]
(split-with pred xs))
;; => [(0 1 2) (7 8 9)]