|
(ns delete-at.main) |
|
|
|
(defn delete-at [in at] |
|
{:pre [(< -1 at (count in))]} |
|
(->> in |
|
(reduce-kv |
|
(fn [out i x] |
|
(if-not (= at i) |
|
(conj! out x) |
|
out)) |
|
(transient [])) |
|
persistent!)) |
|
|
|
|
|
(ns delete-at.main-test |
|
(:require [clojure.test :refer [deftest is]] |
|
[clojure.test.check.clojure-test :refer [defspec]] |
|
[clojure.test.check.generators :as gen] |
|
[clojure.test.check.properties :as prop] |
|
[delete-at.main :refer [delete-at]])) |
|
|
|
(deftest delete-at-bounds-checking |
|
(is (thrown? AssertionError (delete-at [1 2 3] -1))) |
|
(is (thrown? AssertionError (delete-at [1 2 3] 3))) |
|
(is (thrown? AssertionError (delete-at [] 0)))) |
|
|
|
(defspec delete-at-returns-vector 100 |
|
(prop/for-all [v (gen/not-empty (gen/vector gen/small-integer))] |
|
(let [i (first (shuffle (range (count v))))] |
|
(is (vector? (delete-at v i)))))) |
|
|
|
(defspec delete-at-shrinks-by-one 100 |
|
(prop/for-all [v (gen/not-empty (gen/vector gen/small-integer))] |
|
(let [i (first (shuffle (range (count v))))] |
|
(is (= (dec (count v)) (count (delete-at v i))))))) |
|
|
|
(defspec delete-at-leaves-before-same 100 |
|
(prop/for-all [v (gen/not-empty (gen/vector gen/small-integer))] |
|
(let [i (first (shuffle (range (count v))))] |
|
(is (= (subvec v 0 i) |
|
(subvec (delete-at v i) 0 i)))))) |
|
|
|
(defspec delete-at-leaves-after-same 100 |
|
(prop/for-all [v (gen/not-empty (gen/vector gen/small-integer))] |
|
(let [i (first (shuffle (range (count v))))] |
|
(is (= (subvec v (inc i)) |
|
(subvec (delete-at v i) i)))))) |
|
|
|
|
|
(ns delete-at.bench |
|
(:require [criterium.core :refer [bench]])) |
|
|
|
(defn delete-at1 [v i] |
|
(let [before (subvec v 0 i) |
|
after (subvec v (inc i))] |
|
(vec (concat before after)))) |
|
|
|
(comment |
|
(bench (delete-at1 (vec (range 100)) 50)) |
|
; Evaluation count : 6749280 in 60 samples of 112488 calls. |
|
; Execution time mean : 8.942810 µs |
|
; Execution time std-deviation : 103.880455 ns |
|
; Execution time lower quantile : 8.776337 µs ( 2.5%) |
|
; Execution time upper quantile : 9.233488 µs (97.5%) |
|
; Overhead used : 7.516025 ns |
|
|
|
; Found 9 outliers in 60 samples (15.0000 %) |
|
; low-severe 1 (1.6667 %) |
|
; low-mild 3 (5.0000 %) |
|
; high-mild 2 (3.3333 %) |
|
; high-severe 3 (5.0000 %) |
|
; Variance from outliers : 1.6389 % Variance is slightly inflated by outliers |
|
|
|
(bench (delete-at1 (vec (range 1000000)) 500000))) |
|
; Evaluation count : 420 in 60 samples of 7 calls. |
|
; Execution time mean : 121.407189 ms |
|
; Execution time std-deviation : 13.185735 ms |
|
; Execution time lower quantile : 107.764634 ms ( 2.5%) |
|
; Execution time upper quantile : 152.310228 ms (97.5%) |
|
; Overhead used : 7.516025 ns |
|
; |
|
; Found 4 outliers in 60 samples (6.6667 %) |
|
; low-severe 4 (6.6667 %) |
|
; Variance from outliers : 73.7581 % Variance is severely inflated by outliers |
|
|
|
|
|
(defn delete-at2 [in at] |
|
(->> in |
|
(reduce-kv |
|
(fn [out i x] |
|
(if-not (= at i) |
|
(conj! out x) |
|
out)) |
|
(transient [])) |
|
persistent!)) |
|
|
|
(comment |
|
(bench (delete-at2 (vec (range 100)) 50)) |
|
; Evaluation count : 13176780 in 60 samples of 219613 calls. |
|
; Execution time mean : 4.558529 µs |
|
; Execution time std-deviation : 26.914228 ns |
|
; Execution time lower quantile : 4.520799 µs ( 2.5%) |
|
; Execution time upper quantile : 4.609027 µs (97.5%) |
|
; Overhead used : 7.516025 ns |
|
|
|
; Found 2 outliers in 60 samples (3.3333 %) |
|
; low-severe 1 (1.6667 %) |
|
; low-mild 1 (1.6667 %) |
|
; Variance from outliers : 1.6389 % Variance is slightly inflated by outliers |
|
|
|
(bench (delete-at2 (vec (range 1000000)) 500000))) |
|
; Evaluation count : 1020 in 60 samples of 17 calls. |
|
; Execution time mean : 44.875146 ms |
|
; Execution time std-deviation : 6.756898 ms |
Two solutions:
clojure.core.reducers/fold
which turns out to be pretty slow on my system, but probably would be quite fast on many cores or who knows if adapted for use with a GPU?