Ah. I just realized that I did declare middle to be fixnum. Sorry,need
more sleep (or coffee). :-)
On Wed, Aug 01, 2007 at 11:34:31AM -0300, Jeronimo Pellegrini wrote:
> On Wed, Aug 01, 2007 at 03:59:49PM +0200, Chris Laux wrote:
> > Jeronimo Pellegrini wrote:
> > > I see that when dealing with fixnums only [...]
> > What exactly do you mean by that?
> I wasn't clear -- sorry!
> > > (let ((middle (floor (+ start end) 2)) ...
> > Just from that code fragment, it cannot be inferred that (+ start end)
> > returns a fixnum, so you will have to declare it. Is there more context
> > from which the compiler could learn that?
> So -- I have written this simple binary search function that I tried to
> make as generic as possible, but also as fast as possible. I thought
> that since I did not declare "middle" to be fixnum, and #'+ could return
> a bignum, the compiler would complain. But it didn't.
> Here's the function:
> (defun binary-search (the-element vector &key
> (test= #'eql)
> (test< #'<)
> (get-element #'svref)
> (start 0)
> (end (1- (length vector)))
> (not-found nil))
> "Performs a binary search for an element el on a (sorted) array vec.
> Return values:
> - The index where the element was found
> - Either t (if el was found) or nil (if el was not found) You can
> ask the function to return something else on failure.
> Named parameters:
> - get-element is the function used to retrieve an element of the
> vector. The default is svref (but for strings you'll need aref,
> for example). This should be a FUNCTION, and not a symbol!
> - start and end are the start and end indices within the array. If
> they are not supplied, 0 and the last index will be used.
> - test= and test-before are the tests to be used for equality and for
> determining precedence between elements. These should be FUNCTIONS,
> and not symbols!
> - not-found is the element to be returned when the element is not
> If not-found is set to 't', then, in case of failure, the function
> will return (i NIL), where i is the index where the element
> *should* be (or where it could be inserted).
> So, by default you can test the return inside an
> (if (binary-search) ...), since it returns either NIL or the
> (declare (optimize (speed 3) (safety 0))
> (fixnum start end)
> (vector vector))
> ;; The internal function should be fast, so no key args
> (labels ((inside-binary-search (el vec start end)
> (declare (fixnum start end)
> (function test= test< get-element)
> (vector vec))
> (if (< end start)
> (if (eq not-found 't)
> (values start nil) ; where it *should* be
> (values not-found nil))
> (let* ((middle (floor (+ start end) 2))
> (funcall get-element vec middle)))
> (declare (fixnum middle))
> (cond ((funcall test= el middle-element)
> (values middle t))
> ((funcall test< el middle-element)
> (inside-binary-search el
> (1- middle)))
> (inside-binary-search el
> (1+ middle)
> ;; If we don't test this and compile with (safety 0), the user can
> ;; pass symbols like '<, '= and 'aref instead of functions, like
> ;; #'<, #'= and #'aref -- and that would crash the program without
> ;; giving a reasonable explanation:
> (assert (and (functionp test=)
> (functionp test<)
> (functionp get-element)))
> (inside-binary-search the-element vector start end)))