All the ways to split a sequence in two based on a predicate

split.clj

(ns clj-seperate-bench.core
  (:gen-class)
  (:require
   [criterium.core :as c]))

;;; Run with:
;;; java -Xmx8G -Xms8G -XX:+UseG1GC -jar target/uberjar/clj-seperate-bench-0.1.0-SNAPSHOT-standalone.jar

;; 54, 60 ms range
;; 54, 34 ms vector
(defn lazy-separate
  "Return a vector of (filter pred coll) (remove pred coll)."
  [pred coll]
  [(filter pred coll)
   (remove pred coll)])

;; 30, 30 ms range
;; 48, 44 ms range
(defn separate
  [pred coll]
  (loop [coll coll
         truthy ()
         falsey ()]
    (if coll
      (let [head (first coll)]
        (if (pred head)
          (recur (next coll) (conj truthy head) falsey)
          (recur (next coll) truthy (conj falsey head))))
      [truthy falsey])))

;; 29, 29 ms range
;; 45, 45 ms vector
(defn vseparate
  [pred coll]
  (loop [coll coll
         truthy (transient [])
         falsey (transient [])]
    (if coll
      (let [head (first coll)]
        (if (pred head)
          (recur (next coll) (conj! truthy head) falsey)
          (recur (next coll) truthy (conj! falsey head))))
      [(persistent! truthy)
       (persistent! falsey)])))

;; 254, 254 ms range
;; 250, 248 ms vector
(defn split [pred coll]
  (reduce
   (fn [[xs ys] x] (if (pred x) (list (cons x xs) ys) (list xs (cons x ys))))
   (list () ())
   coll))

;; 32, 34 ms range
;; 27, 27 ms vector
(defn splitv [pred coll]
  (reduce
   (fn [[xs ys] x] (if (pred x) [(cons x xs) ys] [xs (cons x ys)]))
   [() ()]
   coll))

;; 39, 37 ms range
;; 35, 35 ms vector
(defn splitjv [pred coll]
  (reduce
   (fn [[xs ys] x] (if (pred x) [(conj xs x) ys] [xs (conj ys x)]))
   [() ()]
   coll))

;; 39, 38 ms range
;; 36, 36 ms vector
(defn vsplit [pred coll]
  (let [[xs ys]
        (reduce
         (fn [[xs ys] x]
           (if (pred x)
             [(conj! xs x) ys]
             [xs (conj! ys x)]))
         (transient
          [(transient [])
           (transient [])])
         coll)]
    [(persistent! xs)
     (persistent! ys)]))

(defn criterium-bench
  []
  (let [coll (doall (range 1e6))]
    (println "range::lazy-seperate")
    (c/bench (let [x (lazy-separate odd? coll)]
               (doall (first x)) (doall (second x))))
    (println "range::seperate")
    (c/bench (separate odd? coll))
    (println "range::vseparate")
    (c/bench (vseparate odd? coll))
    (println "range::split")
    (c/bench (split odd? coll))
    (println "range::splitv")
    (c/bench (splitv odd? coll))
    (println "range::splitjv")
    (c/bench (splitjv odd? coll))
    (println "range::vsplit")
    (c/bench (vsplit odd? coll)))
  (let [coll (into [] (range 1e6))]
    (println "vector::lazy-seperate")
    (c/bench (let [x (lazy-separate odd? coll)]
               (doall (first x)) (doall (second x))))
    (println "vector::seperate")
    (c/bench (separate odd? coll))
    (println "vector::vseparate")
    (c/bench (vseparate odd? coll))
    (println "vector::split")
    (c/bench (split odd? coll))
    (println "vector::splitv")
    (c/bench (splitv odd? coll))
    (println "vector::splitjv")
    (c/bench (splitjv odd? coll))
    (println "vector::vsplit")
    (c/bench (vsplit odd? coll))))