I woke up this morning having had a dream about how to solve a very large scale data processing problem that a friend of mine was wrestling with, and I wrote the following program:
It seems to run very fast.
(defn step-function [x] (cond (< x 1) 0 (< x 2) 1 (< x 3) 3 (< x 4) 4 (< x 6) 3 (< x 8) 2 (< x 9) 3 (< x 10) 3 (< x 11) 2 (< x 12) 1 :else 0)) (step-function 6) (def lookup-table {1 1, 2 3, 3 4, 4 3, 6 2, 8 3, 9 3, 10 2, 11 1, 12 0}) (defn lookup-fn [map default] (fn [x] (if-let [ [k v] (last (filter (fn[[k v]] (<= k x)) map )) ] v default))) ((lookup-fn lookup-table 0) 6) (map (lookup-fn lookup-table 0) '(1 7 6 20 -10)) (defn fn-to-map [fn range] "Evaluate fn everywhere in range. Return map of all values to all results." (apply sorted-map (interleave range (map fn range)))) (fn-to-map (lookup-fn lookup-table 0) (range -1 14)) (fn-to-map step-function (range -1 14)) (time (doall (map step-function (range 1000)))) "Elapsed time: 3.054365 msecs" (time (doall (map (lookup-fn lookup-table 0) (range 1000)))) "Elapsed time: 15.657764 msecs" (defn lookup-fn-handwritten [x] (if (< x 6) (if (< x 3) (if (< x 2) (if ( < x 1) 0 1) 3) (if (< x 4) 4 2)) (if (< x 10) (if (< x 9) (if (< x 8) 2 3) 3) (if (< x 11) (if (< x 12) 1 0) 0)))) (fn-to-map lookup-fn-handwritten (range -1 14)) {-1 0, 0 0, 1 1, 2 3, 3 4, 4 2, 5 2, 6 2, 7 2, 8 3, 9 3, 10 1, 11 0, 12 0, 13 0} (time (doall (map lookup-fn-handwritten (range 1000)))) "Elapsed time: 1.442812 msecs" (= (fn-to-map lookup-fn-handwritten (range -1 14)) (fn-to-map (lookup-fn lookup-table 0) (range -1 14))) '(make-lookup-fn {} default) 'default '(make-lookup-fn {10 yo} default) '(fn[x] (if (< x 10) default yo)) '(make-lookup-fn {8 hey 10 yo 12 hi} default) '(fn[x] (if (< x 10) (make-lookup-fn {8 hey} default) (make-lookup-fn {12 hi} yo))) (defn make-lookup-expression [var lookup-map lowdefault] (let [vmap (sort (seq lookup-map)) vmcount (count vmap)] (cond (= vmcount 0) lowdefault (= vmcount 1) (let [[test high] (first vmap)] (list 'if (list '< var test) lowdefault high)) :else (let [pivot (int (/ (count vmap) 2)) [test highdefault] (nth vmap pivot) before-pivot (take pivot vmap) after-pivot (drop (inc pivot) vmap)] (list 'if (list '< var test) (make-lookup-expression var before-pivot lowdefault) (make-lookup-expression var after-pivot highdefault)))))) (make-lookup-expression 'x {1 1, 2 3, 3 4, 4 3, 6 2, 8 3, 9 3, 10 2, 11 1, 12 0} 'default) #_(if (< x 8) (if (< x 3) (if (< x 2) (if (< x 1) default 1) 3) (if (< x 6) (if (< x 4) 4 3) 2)) (if (< x 11) (if (< x 10) (if (< x 9) 3 3) 2) (if (< x 12) 1 0))) (defn make-lookup-fn [lookup-map default] (let [var (gensym)] (list 'fn [var] (make-lookup-expression var lookup-map default)))) (def lookup-fn-automatic (eval (make-lookup-fn {1 1, 2 3, 3 4, 4 3, 6 2, 8 3, 9 3, 10 2, 11 1, 12 0} 0))) (= (fn-to-map lookup-fn-automatic (range -1 14)) (fn-to-map (lookup-fn lookup-table 0) (range -1 14))) (def million (doall (range 1000000))) (time (dorun (map lookup-fn-automatic million))) "Elapsed time: 778.459478 msecs" (time (dorun (map #(* 3 %) million))) "Elapsed time: 474.40039 msecs" (last (let [source (into-array Integer/TYPE (range 1000)) destination (aclone source)] (time (loop [x 0] (if (< x (alength source)) (do (aset destination x (* 3 (aget source x))) (recur (inc x)))))) destination)) "Elapsed time: 168.434663 msecs" (last (let [source (int-array (range 1000)) destination (int-array (aclone source)) length (alength source) zero (int 0) three (int 3)] (time (loop [x zero] (if (< x length) (do (aset destination x (* three (aget source x))) (recur (unchecked-inc x)))))) destination)) "Elapsed time: 1.1944 msecs" 2997 (last (let [source (int-array million) destination (aclone source) length (alength source) zero (int 0) three (int 3)] (time (loop [x zero] (if (< x length) (do (aset destination x (* three (aget source x))) (recur (unchecked-inc x)))))) destination)) "Elapsed time: 45.465962 msecs" 2999997 (time (int-array 1000000)) "Elapsed time: 5.84744 msecs" (defn constant-helper [mp default] (let [constants (sort (set (cons default (apply concat (sort (seq mp)))))) constants-let (apply vector (mapcat #(list (symbol (str "n" %))(list 'int %)) constants)) constant-symbols (map #(symbol (str "n" %)) constants) constants-symbols-map (apply sorted-map (interleave constants constant-symbols))] (list constants-let constants-symbols-map))) (constant-helper {1 1, 2 3, 3 4, 4 3, 6 2, 8 3, 9 3, 10 2, 11 1, 12 0} 255) #_([n0 (int 0) n1 (int 1) n2 (int 2) ............. n12 (int 12) n255 (int 255)] {0 n0, 1 n1, 2 n2, 3 n3, 4 n4, 6 n6, 8 n8, 9 n9, 10 n10, 11 n11, 12 n12, 255 n255}) (clojure.walk/postwalk #(if (integer? %) (get {1 "1", 2 "2"} % %) %) '(+ 1 (* 2 3))) (defn transformed-exprs [mp default] (let [[let-expr cs-map] (constant-helper mp default) if-expr (make-lookup-expression 'x (sort (seq mp)) default) transformed-if-expr (clojure.walk/postwalk #(if (integer? %) (get cs-map % %) %) if-expr)] (list transformed-if-expr let-expr))) (transformed-exprs {1 1, 2 3, 3 4, 4 3, 6 2, 8 3, 9 3, 10 2, 11 1, 12 0} 255) #_(((if (< x n8) ... (if (< x n9) n3 n3) n2) (if (< x n12) n1 n0)) [n0 (int 0) n1 (int 1) ... n12 (int 12) n255 (int 255)]) (let [source (int-array million) destination (aclone source) length (alength source)] (let [n0 (int 0) n1 (int 1) n2 (int 2) n3 (int 3) n4 (int 4) n6 (int 6) n8 (int 8) n9 (int 9) n10 (int 10) n11 (int 11) n12 (int 12) n255 (int 255)] (time (loop [i (int 0)] (if (< i length) (do (aset destination i (let [x (aget source i)] (if (< x n8) (if (< x n3) (if (< x n2) (if (< x n1) n255 n1) n3) (if (< x n6) (if (< x n4) n4 n3) n2)) (if (< x n11) (if (< x n10) (if (< x n9) n3 n3) n2) (if (< x n12) n1 n0))))) (recur (unchecked-inc i))))))) destination) "Elapsed time: 28.387293 msecs" nil (defn generate-array-transformer [mp default] (let [[if-expr let-expr] (transformed-exprs mp default)] `(fn[source#] (let [source# (int-array source#) destination# (aclone source#) length# (int (alength source#))] (time (let ~let-expr (loop [i# (int 0)] (if (< i# length#) (do (aset destination# i# (let [~'x (aget source# i#)] ~if-expr)) (recur (unchecked-inc i#))))))) destination#)))) (generate-array-transformer {1 1, 2 3, 3 4, 4 3, 6 2, 8 3, 9 3, 10 2, 11 1, 12 0} 255) (def never-going-to-work (eval (generate-array-transformer {1 1, 2 3, 3 4, 4 3, 6 2, 8 3, 9 3, 10 2, 11 1, 12 0} 255))) (def million-ints (int-array million)) (take 100 (never-going-to-work million-ints)) "Elapsed time: 11.656722 msecs" (time (never-going-to-work million-ints)) "Elapsed time: 10.887267 msecs" "Elapsed time: 148.408179 msecs" (def never-going-to-work-2 (eval (generate-array-transformer {1 99, 2 33, 3 4, 6 2, 8 3, 9 3, 10 2, 11 1, 12 0, 15 -1, 24 100} 100))) (time (take 100 (never-going-to-work-2 million-ints))) "Elapsed time: 11.455121 msecs" "Elapsed time: 138.169579 msecs" (def ten-million-ints (int-array (apply concat (repeat 400000 (range 25) )))) (time (take 100 (never-going-to-work-2 ten-million-ints))) "Elapsed time: 156.814438 msecs" "Elapsed time: 1437.094696 msecs" (def random-map (apply sorted-map (for [i (range 200)] (rand-int 100)))) (def large-random-step-function (eval (generate-array-transformer random-map 100))) (time (take 100 (large-random-step-function ten-million-ints))) "Elapsed time: 276.477877 msecs" "Elapsed time: 1497.910398 msecs" (def random-map (apply sorted-map (for [i (range 400)] (rand-int 1000)))) (def large-random-step-function (eval (generate-array-transformer random-map 100))) #_ (let [n0 (int 0)] ...)