Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
(ns bar.baz
(:require [vertigo.core :as vc]
[vertigo.structs :as vs]))
;;
;; based off of work by Michał Marczyk
;; http://stackoverflow.com/questions/8949837/binary-search-in-clojure-implementation-performance
;;
(set! *warn-on-reflection* true)
(defn- lowerbound-search
"Finds earliest occurrence of val using provided getter function"
[getfn val size]
(loop [l 0
h (unchecked-dec size)
hint 0]
(if (<= h (unchecked-add l 1))
(cond
(== val (getfn l)) [l hint]
(== val (getfn h)) [h hint]
:else nil)
(let [m (unchecked-add l (bit-shift-right (unchecked-subtract h l) 1))]
(if (< (getfn m) val)
(recur (unchecked-inc m) h m)
(if (and (== (getfn m) val)
(> m hint))
(recur l m m)
(recur l m hint)))))))
(defn- upperbound-search
"Finds latest occurrence of val using provided getter function."
([getfn val size ^long lowerbound]
(loop [l lowerbound
h (unchecked-dec size)]
(if (<= h (unchecked-add l 1))
(cond
(== val (getfn h)) h
(== val (getfn l)) l
:else nil)
(let [m (unchecked-add l (bit-shift-right (unchecked-subtract h l) 1))]
(if (> (getfn m) val)
(recur l m)
(recur m h)))))))
(defn range-search
"Finds earliest and latest occurrence of val in a vertigo typed struct. Data
must be in sorted order. Returns a vector of two elements denoting the index
ranges at which val was found or simply nil if val was not present."
([getfn val size]
(if-let [[earliest hint] (lowerbound-search getfn val size)]
(let [latest (upperbound-search getfn val size hint)]
[earliest, latest])
nil)))
;;;;;;;;;;;;;
(def size 1000)
(vs/def-typed-struct foo
:a (vs/array vs/uint16 size)
:b (vs/array vs/uint16 size))
(letfn [(data [] (sort (take size (repeatedly #(rand-int 100)))))]
(def ^:foo ts (vc/marshal-seq foo [{:a (data) :b (data)}])))
(range-search #(vc/get-in ts [0 :a %]) 0 size)
(range-search #(vc/get-in ts [0 :a %]) 10 size)
(range-search #(vc/get-in ts [0 :a %]) 99 size)
(range-search #(vc/get-in ts [0 :a %]) 100 size)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.