·········@yahoo.com wrote:
> thanks for the reply
>
> Still not sure why
>
> (defmacro while (test &rest body)
> `(do () ((not ,test)) ,@body))
>
> (defun binarySearch (a x)
> (let ((low 0)
> (high (- (length a) 1)))
> (while (<= low high)
> (let ((mid (truncate (+ low high) 2)))
> (let ((obj (aref a mid)))
> (if (< obj x)
> (setf low (+ mid 1)))
> (if (> obj x)
> (setf high (- mid 1)) mid))) -1)))
>
> is not working
It's somewhat easier to see when we indent the the last line in a more
idiomatic way. See comments in the sourcecode below:
(defmacro while (test &rest body)
;; Important to note that WHILE will evaluate to nil unless
;; we use a RETURN or RETURN-FROM statement.
`(do () ((not ,test)) ,@body))
(defun binary-search (a x)
(let ((low 0)
(high (- (length a) 1)))
(while (<= low high)
(let ((mid (truncate (+ low high) 2)))
;; Let's stick in a debugging statement.
(format t "~&[~S,~S] ~S" low high mid)
(let ((obj (aref a mid)))
(if (< obj x)
(setf low (+ mid 1)))
(if (> obj x)
(setf high (- mid 1))
;; Issue: the following MID is evaluated even
;; when (< obj x).
;;
;; Further, there will be an infinite loop here
;; if (= obj x), as there is neither a return
;; statement, nor do we update LOW or HIGH.
mid)))
;; This is at the end of WHILE form... and this WHILE
;; is going to evalulate to nil unless there's a return
;; statement of some sort.
;;
;; And again, returning NIL instead of -1 is more idiomatic.
-1)))
Tayssir
Hi,
Marco Antoniotti <·······@cs.nyu.edu> writes:
[deletia]
>
> Nice, but memory hungry. Check the definition of SUBSEQ.
>
> (defun binary-search (vector item
> &optional (start 0) (end (length vector))
> (test #'<))
> (let* ((l (length vector))
> (mid (round l 2))
> (obj (aref vector mid)))
> (cond ((zerop l) (values nil nil))
> ((funcall test obj item)
> (binary-search vector item mid))
> ((funcall (complement test) obj item)
> (binary-search vector item 0 mid))
> (t (values obj t))
> )))
Nice, but not sufficiently tested ;) The T clause will never be
reached, since (COMPLEMENT TEST) is, well, the complement of TEST.
This should work (lightly tested):
(defun binary-search (vector item &key (test #'<) (start 0) (end (length vector)))
(labels ((search1 (start end)
(when (< start end)
(let* ((mid-index (+ start (floor (- end start) 2)))
(mid-item (aref vector mid-index)))
(cond ((funcall test item mid-item)
(search1 start mid-index))
((funcall test mid-item item)
(search1 (1+ mid-index) end))
(t
(values item t)))))))
(search1 start end)))
A qsort-style "comparator" might be more appropriate for cases where
funcalling TEST twice would be prohibitive:
(defun comparator (test)
"Returns a function that adapts TEST to serve as a comparator.
That is, when passed two arguments A and B, it returns -1
when (TEST A B) is true, +1 when (TEST B A) is true, and 0
otherwise."
(lambda (a b)
(cond ((funcall test a b) -1)
((funcall test b a) +1)
(t 0))))
(defun binary-search (vector item &key (comparator (comparator #'<)) (start 0) (end (length vector)))
(labels ((search1 (start end)
(when (> end start)
(let* ((mid-index (+ start (floor (- end start) 2)))
(mid-item (aref vector mid-index))
(code (funcall comparator item mid-item)))
(cond ((minusp code)
(search1 start mid-index))
((plusp code)
(search1 (1+ mid-index) end))
(t
(values item t)))))))
(search1 start end)))
Cheers,
Damien.
--
http://foobox.net/~dash/
Life is like a tin of sardines. We're, all of us, looking for the key.
-- Beyond the Fringe
·········@yahoo.com wrote:
> I am trying to convert the following C++ code to lisp
>
> template <class Comparable>
> int binarySearch( const vector<Comparable> & a, const
> Comparable & x )
> {
> /* 1*/ int low = 0, high = a.size( ) - 1;
> /* 2*/ while( low <= high )
> {
> /* 3*/ int mid = ( low + high ) / 2;
> /* 4*/ if( a[ mid ] < x )
Note that this code will use bool Comparable::operator <(Comparable &)
or the non-member one bool operator < (Comparable &, Comparable &).
The Lisp solutions fail to capture this because they use the
non-generic < function.
Could that be important? Sure. Consider:
vector<string> haystack;
string needle = "foo";
// ...
int found = binarySearch(haystack, needle);
This works with the binarySearch template function in C++, but the Lisp
"conversions" presented so far won't handle strings!
Moreover, the C++ template will statically generate the code, and then
the particular overload of the < function will also be statically
chosen.
There is no dispatch overhead for calling the < function (unless the
template parameter Comparable for a given expansion happens to be a
base class in which the < operator is a virtual function).
If you want to capture these nuances, you have to make it a macro:
(defmacro def-binary-search(func-name element-type predicate-func) ...)
Then instantiate it over vectors of objects of type FOO, using a
function LESS-THAN to compare two FOO instances, and giving the name
SEARCH-FOO-VECTOR to the resulting function:
(def-binary-search search-foo-vector foo less-than)
Or to do numbers:
(def-binary-search search-num-vector number <)
Strings:
(def-binary-search search-string-vector string string<)
Here you can use STRING-LESSP for a case-insensitive comparison.
Kaz Kylheku wrote:
> Note that this code will use bool Comparable::operator <(Comparable &)
> or the non-member one bool operator < (Comparable &, Comparable &).
>
> The Lisp solutions fail to capture this because they use the
> non-generic < function.
>
> Could that be important? Sure. Consider:
>
> vector<string> haystack;
> string needle = "foo";
>
> // ...
>
> int found = binarySearch(haystack, needle);
>
> This works with the binarySearch template function in C++, but the Lisp
> "conversions" presented so far won't handle strings!
>
> Moreover, the C++ template will statically generate the code, and then
> the particular overload of the < function will also be statically
> chosen.
>
> If you want to capture these nuances, you have to make it a macro:
>
> (defmacro def-binary-search(func-name element-type predicate-func) ...)
Or if you don't want to be quite that faithful, you (the orig poster)
can just pass in a LESS-THAN predicate every time you do the search.
(binary-search #("aaa" "bbb" "ccc" "ddd") "ccc" #'string<)
"Tayssir John Gabbour" <···········@yahoo.com> wrote in message
····························@g43g2000cwa.googlegroups.com...
> Kaz Kylheku wrote:
>>
>> (defmacro def-binary-search(func-name element-type predicate-func) ...)
>
> Or if you don't want to be quite that faithful, you (the orig poster)
> can just pass in a LESS-THAN predicate every time you do the search.
>
> (binary-search #("aaa" "bbb" "ccc" "ddd") "ccc" #'string<)
Or a combination of MEMBER and SORT
(defun binary-search (item array predicate &key key) ...)
or declare a struct or class that carries the array and the sort predicate
--
Geoff
Tayssir John Gabbour wrote:
> Or if you don't want to be quite that faithful, you (the orig poster)
> can just pass in a LESS-THAN predicate every time you do the search.
>
> (binary-search #("aaa" "bbb" "ccc" "ddd") "ccc" #'string<)
Would it make more sense to support Lispy :test and :key arguments?
Perhaps not, because the condition that the vector be sorted means you
are relatively restricted in the ordering that can be specified.
·········@yahoo.com writes:
> The code below doesn't work. (low doesn't change) Any way to fix this
> problem?
> ;;;
> (defmacro while (test &rest body)
> `(do () ((not ,test)) ,@body))
Use &body for bodies: editors will deliver better indentation.
> (defun binarySearch (a x)
camelCase is frowned upon around here. Use binary-search
> (let ((low 0)
> (high (- (length a) 1)))
> (while (<= low high)
> (let ((mid (truncate (+ low high) 2)))
> (let ((obj (aref a mid)))
> (if (< obj x)
> (setf low (+ mid 1)))
> (if (> obj x)
> (setf high (- mid 1)) mid))) -1)))
>
You could use COND instead of these two IF.
Improve your debugging skills. Read Chapter 25 of CLHS.
low is indeed updated.
[7]> (trace truncate)
** - Continuable Error
TRACE(TRUNCATE): #<PACKAGE COMMON-LISP> is locked
If you continue (by typing 'continue'): Ignore the lock and proceed
The following restarts are also available:
ABORT :R1 ABORT
Break 1 [8]> continue
WARNING: TRACE: redefining function TRUNCATE in top-level, was defined in C
;; Tracing function TRUNCATE.
(TRUNCATE)
[9]> (binarysearch #(1 2 3 4 5 6 7 8) 7)
1. Trace: (TRUNCATE '7 '2)
1. Trace: TRUNCATE ==> 3, 1
1. Trace: (TRUNCATE '11 '2)
1. Trace: TRUNCATE ==> 5, 1
1. Trace: (TRUNCATE '13 '2)
1. Trace: TRUNCATE ==> 6, 1
1. Trace: (TRUNCATE '13 '2)
1. Trace: TRUNCATE ==> 6, 1
1. Trace: (TRUNCATE '13 '2)
1. Trace: TRUNCATE ==> 6, 1
The binary search can not end if you you start with a high less than
the length of the sequence. Add some assertions if you don't see why.
Note that Graham uses ROUND, not TRUNCATE.
--
__Pascal Bourguignon__ http://www.informatimago.com/
-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCS d? s++:++ a+ C+++ UL++++ P--- L+++ E+++ W++ N+++ o-- K- w---
O- M++ V PS PE++ Y++ PGP t+ 5+ X++ R !tv b+++ DI++++ D++
G e+++ h+ r-- z?
------END GEEK CODE BLOCK------