Karate Chop
June 16, 2015
Thomas gives a simple test suite, which we copy here; it complains on any error but is otherwise silent, on the theory that no news is good news:
(define (test chop)
(assert (chop 3 '#()) -1)
(assert (chop 3 '#(1)) -1)
(assert (chop 3 '#(3)) 0)
(assert (chop 1 '#(1 3 5)) 0)
(assert (chop 3 '#(1 3 5)) 1)
(assert (chop 5 '#(1 3 5)) 2)
(assert (chop 0 '#(1 3 5)) -1)
(assert (chop 2 '#(1 3 5)) -1)
(assert (chop 4 '#(1 3 5)) -1)
(assert (chop 6 '#(1 3 5)) -1)
(assert (chop 1 '#(1 3 5 7)) 0)
(assert (chop 3 '#(1 3 5 7)) 1)
(assert (chop 5 '#(1 3 5 7)) 2)
(assert (chop 7 '#(1 3 5 7)) 3)
(assert (chop 0 '#(1 3 5 7)) -1)
(assert (chop 2 '#(1 3 5 7)) -1)
(assert (chop 4 '#(1 3 5 7)) -1)
(assert (chop 6 '#(1 3 5 7)) -1)
(assert (chop 8 '#(1 3 5 7)) -1))
Here is Thomas’ traditional imperative approach, complete with a while loop, variable assignment, and a return statement built from call-with-current-continuation:
(define (chop1 needle haystack)
(call-with-current-continuation
(lambda (return)
(let ((lo 0) (hi (- (vector-length haystack) 1)))
(while (<= lo hi)
(let ((mid (quotient (+ lo hi) 2)))
(cond ((< needle (vector-ref haystack mid))
(set! hi (- mid 1)))
((< (vector-ref haystack mid) needle)
(set! lo (+ mid 1)))
(else (return mid)))))
(return -1)))))
> (test chop1)
I’m pretty sure this is what Thomas intends when he talks about the recursive approach:
(define (chop2 needle haystack)
(chop2-aux needle haystack 0 (- (vector-length haystack) 1)))
(define (chop2-aux needle haystack lo hi)
(call-with-current-continuation
(lambda (return)
(if (< hi lo) (return -1)
(let ((mid (quotient (+ lo hi) 2)))
(cond ((< needle (vector-ref haystack mid))
(return (chop2-aux needle haystack lo (- mid 1))))
((< (vector-ref haystack mid) needle)
(return (chop2-aux needle haystack (+ mid 1) hi)))
(else (return mid))))))))
> (test chop2)
Thomas talks about a functional style passing array slices around, but I’m not entirely sure what he means. Here is the traditional Scheme version of binary search:
(define (chop3 needle haystack)
(let loop ((lo 0) (hi (- (vector-length haystack) 1)))
(if (< hi lo) -1
(let ((mid (quotient (+ lo hi) 2)))
(cond ((< needle (vector-ref haystack mid))
(loop lo (- mid 1)))
((< (vector-ref haystack mid) needle)
(loop (+ mid 1) hi))
(else mid)))))))
> (test chop3)
Those three versions of binary search all work whether or not the values in the array are distinct, but if they are not distinct, they may return the index of any of the equal items. It’s generally better to return the first such index, which can be done by delaying the test for equality until the end. That means you can never return early with a lucky match, so each search takes log2 comparisons, but it also means there is only one comparison at each step. Here’s the iterative version of that algorithm:
(define (chop4 needle haystack)
(call-with-current-continuation
(lambda (return)
(let ((lo 0) (hi (- (vector-length haystack) 1)))
(while (< lo hi)
(let ((mid (quotient (+ lo hi) 2)))
(if (< (vector-ref haystack mid) needle)
(set! lo (+ mid 1))
(set! hi mid))))
(if (and (= lo hi) (= needle (vector-ref haystack lo)))
(return lo)
(return -1))))))
> (test chop4)
And to complete Thomas’ requirement of five different implementations, here’s a Scheme-ly version of chop4:
(define (chop5 needle haystack)
(let loop ((lo 0) (hi (- (vector-length haystack) 1)))
(if (<= hi lo)
(if (and (= lo hi) (= needle (vector-ref haystack lo))) lo -1)
(let ((mid (quotient (+ lo hi) 2)))
(if (< (vector-ref haystack mid) needle)
(loop (+ mid 1) hi)
(loop lo mid))))))
> (test chop5)
We used the assert and while macros from the Standard Prelude. You can run the program at http://ideone.com/BxXfot.
I don’t give the code for the standard interative, recursive and functional functions. But here is a somewhat different approach. Basically, for each bit in the index, starting at the msb, you decide whether that bit should be set or clear by comparing el with the value at lst[index with the bit set]. four() is an iterative version, five() is a recursive version; nine() is a functional version based on the same idea.
def four(el, lst): index = 0 mask = 1 << len(lst).bit_length() while mask: mask >>= 1 tmp = index | mask if tmp < len(lst) and el >= lst[tmp]: index = tmp return index if lst and el == lst[index] else -1 def five(el, lst): def _five(index, mask): if mask: if index | mask < len(lst) and el >= lst[index | mask]: return _five(index | mask, mask >> 1) else: return _five(index, mask >> 1) else: return index if el == lst[index] else -1 return _five(0, 1 << len(lst).bit_length()) if lst else -1 def nine(el, lst): t = lambda i, b: i|b if i|b < len(lst) and el >= lst[i|b] else i m = 1 << (len(lst).bit_length() - 1) index = reduce(t, [m >> i for i in range(x+2)], 0) return index if el == lst[index] else -1Somehow, I pasted the wrong version of nine(). Here’s the correct version:
def nine(el, lst): t = lambda i, b: i|b if i|b < len(lst) and el >= lst[i|b] else i m = (1 << len(lst).bit_length()) >> 1 index = reduce(t, [m >> i for i in range(m+2)], 0) return index if el == lst[index] else -1@Mike: nice solution, I wish I’d thought of that…