From: Jeronimo P. <j_...@al...> - 2007-08-01 14:35:06
|
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. J. 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 found. 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 position." (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)) (middle-element (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 vec start (1- middle))) (t (inside-binary-search el vec (1+ middle) end))))))) ;; 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))) |