Dave Snowdon wrote:
> ; helper function that splits a collection into halves
> (defn halve [coll]
> (let [len (count coll), hl (- len (/ len 2))]
> [(take hl coll) (drop hl coll)]
> )
> )
>
> ; takes a value and an ordered sequence and returns the index of the value
> or -1
> (defn chop [val coll]
> (letfn [(chop2 [ofst val coll]
> (cond (empty? coll) -1
> (= 1 (count coll)) (if (= val (first coll)) ofst -1)
> :else (let [[fh sh] (halve coll), sel (first sh)]
> (cond (= val sel) (+ ofst (count fh))
> (< val sel) (recur ofst val fh)
> :else (recur (+ ofst (count fh)) val sh)))))]
> (chop2 0 val coll)))
I think the main thing that's confusing here is that you're messing
with offsets and split collections at once. At least is was confusing
to me. :)
I think for binary search (which implies random lookup is ~ O(n)
anyway) it's clearer if you stick to offsets.
A few remarks regarding style:
You don't need letfn; personally I think it's clearer to use either
two separate functions or - in this case - specialize on the
arguments.
If you define assert_equal as a function, you won't get any good
feedback if the assert fails. Use a macro instead.
Here's what I made:
(defn chop
([val coll]
(chop val coll 0 (count coll)))
([val coll left right] ; range to test is left ... right - 1, which
makes the code a bit cleaner
(if (< left right) ; are we still in a valid range?
(let [halve (int (/ (- right left) 2))
index (+ left halve)
found-value (coll index)]
(cond
(= val found-value) index
(> val found-value) (recur val coll (inc index) right)
(< val found-value) (recur val coll left index)))
-1))) ; not found
(defmacro assert_equal
[v1 v2]
`(assert (= ~v1 ~v2)))
Note that all of this is pretty low-level but I think it looks kinda
nice and readable.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
