Prev: Question from a non-user: Garbage Collection
Next: Loading a file into a running image with Swank
From: W. James on 19 Dec 2009 03:18
Thierry Pirot wrote:

> ccc31807 writes:
> > On page 61 of Graham's ANSI Common Lisp, he defines bin-search and
> > finder, which I have copied below.
> >
> > I have struggled with this for days, and still don't understand
> > these definitions completely. This morning, I wrote bin-search-2,
> > which took about ten minutes to write (and about thirty minutes to
> > debug), but I understand it thoroughly -- and I am just the merest
> > beginner, barely a toe in the water.
>
> [...]
>
> > ;;; ---------ch_04.lisp-----------------------
> > (defparameter v (vector 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
> > 33 35 37 39 41))
> >
> > (defun bin-search (obj vec)
> > (format t "bin-search ~a ~a~%" obj vec)
> > (let ((len (length vec)))
> > (and (not (zerop len)))
> > (finder obj vec 0 (- len 1))))
> >
> The parentheses in that copy of bin-search are wrong.
> Is this genuinely Graham's ? I don't own the book to check.
>
> > (defun finder (obj vec start end)
> > (format t "finder obj: ~a, vec: ~a, start: ~a, end: ~a~%" obj vec
> > start end)
> > (format t " ~a~%" (subseq vec start (+ end 1)))
> > (let ((range (- end start)))
> > (if (zerop range) ; outer if test
> > (if (eql obj (aref vec start)) ; inner if test
> > obj ; the return obj
> > nil) ; else return nil
> > (let ((mid (+ start (round (/ range 2))))) ; outer then
> > (let ((obj2 (aref vec mid)))
> > (if (< obj obj2)
> > (finder obj vec start (- mid 1))
> > (if (> obj obj2)
> > (finder obj vec (+ mid 1) end)
> > obj)))))))
> >
> I doubt that such a code might be understandable or correct ;
> indeed it is not : just evaluate (bin-search 0 #(1 2)) and blow the
> stack.
>
> What is the origin of this bug and the way to correct it ?
> The bug is about fiddling with indices and splitting their range.
> Other posts in this thread have emphasised
> the advantage to separate functionalities amongst functions.
> finder is a step in that direction, however it still dangerously
> mixes the job of finding with the job of dichotomy,
> which can be handled in the following quick and dirty protocol
> to deal with ranges --- as conses --- and their splitting.
>
> (defun range (start end) ;end inclusive
> (if (<= start end)
> (cons start end)
> (error "Invalid range ~s ~s. " start end)))
> (defmethod range_of ((v vector))
> (unless (equalp #() v) (range 0 (1- (length v)))))
> (defun range_len (range)
> (if range (1+ (- (cdr range) (car range))) 0))
> (defun range_mid (range)
> (when (and range (< (car range) (cdr range)))
> (+ (car range) (floor (range_len range) 2))))
> (defmethod range_splits (range)
> "The cons of two complementary 'even' subranges of the range
> range. " (let ((mid (range_mid range)))
> (when mid ;is_splittable
> (cons (range (car range) (1- mid))
> (range mid (cdr range))))))
>
> Now, one should wonder about this protocol,
> is it reliable --- anyway it is easy to unit-test ---,
> is it handy --- more than start and end parameters --- to use ?
> Let's see,
>
> (defun bin-search (obj vec)
> (format t "bin-search' ~a ~a~%" obj vec)
> (unless (equalp #() vec)
> (labels ((finder (range)
> (format t "range:~a~%" range)
> (format t " ~a~%" (subseq vec (car range) (1+ (cdr
> range)))) (let ((splits (range_splits range)))
> (if splits
> (if (< obj (aref vec (cadr splits)))
> (finder (car splits))
> (finder (cdr splits)))
> (when (= obj (aref vec (car range))) obj)))))
> (finder (range_of vec)))))
>
> The original finder was rather self contained and used a lot of
> variables, now it involves a lot of functions,
> although it's essentially only range_splits.
> It also performs a slightly different algorithm [1], using no pivot :
> if the range is splittable
> then search in the appropriate split,
> else --- the range stands for a singleton ---
> check if the element of the singleton is the searched obj.
>
> > (defun bin-search-2 (obj vec &optional (start 0))
> > (let*((len (length vec))
> > (mid (floor (/ len 2))))
> > (format t "bin-search-2 obj: ~a, vec: ~a, start ~a, end: ~a, mid:
> > ~a~ %" obj vec start len mid)
> > (cond ((zerop len) nil)
> > ((= obj (svref vec mid)) obj)
> > ((< obj (svref vec mid)) (bin-search-2 obj (subseq vec start
> > mid)))
> > ((> obj (svref vec mid)) (bin-search-2 obj (subseq vec (+
> > mid 1) len))))))
> >
> > ;; I don't know how to set 'start' to 0 by default, other than by
> > making it optional.
> > ;; I would appreciate help with this.
> >
> You simply don't need it, it is always 0.
> So your function can be written like
>
> (defun bin-search (obj vec &key (cmp #'cmp))
> (format t "bin-search''' obj: ~a vec: ~a ~%" obj vec)
> (let* ((len (length vec))
> (mid (floor len 2)))
> (when (/= 0 len)
> (case (funcall cmp obj (aref vec mid))
> (0 obj)
> (-1 (bin-search obj (subseq vec 0 mid)))
> (+1 (bin-search obj (subseq vec (1+ mid))))))))
>
> where I added
>
> (defgeneric cmp (x y)
> (:documentation "+1, 0, -1 according to x being after, with,
> before y. ")) (defmethod cmp ((x integer) (y integer)) (signum (-
> x y)))
> To cope with the problem of the consing of subseq, maybe using
>
> (defun subvec (a_vector start &optional (end (length a_vector)))
> (make-array (- end start)
> :displaced-to a_vector
> :displaced-index-offset start
> :element-type (array-element-type a_vector)))
>
> instead of subseq can help, but I know little about displaced arrays
> and a quick profiling shows only slight differences in Clisp.
> I guess it should be different for bitvectors or vectors or big
> elements. I hope someone will clear this.
>
>
>
> [1] This algorithm exhibits a nice pattern, for processing by
> dichotomy, that can be translated, without further explanations, as
>
> (defun spliterator (rektor f_atom &optional (splitter #'split))
> (labels ((f (x)
> (let ((splits (funcall splitter x)))
> (if splits
> (funcall rektor (f (car splits)) (f (cdr splits)) splits)
> (funcall f_atom x)))))
> #'f))
>
> (defun bin-search (obj vec)
> (unless (equalp #() vec)
> (funcall
> (spliterator
> (lambda (x y splits) (if (< obj (aref vec (cadr splits))) x
> y)) (lambda (x) (when (= obj (aref vec (car x)))
> obj)) 'range_splits)
> (range_of vec))))



v = 1.step(41,2).to_a

def bin_search obj, array
len = array.size
len > 0 and finder( obj, array, 0 ... len )
end

def split_range range
first, last = range.min, range.max
mid = first + ((last - first) / 2.0).round
[(first .. [first,mid.pred].max), mid, ([mid.succ,last].min .. last)]
end

def finder obj, array, range
return (obj == array[range.first] ? obj : nil) if range.one?
left, mid, right = split_range range
case obj <=> array[mid]
when -1
finder obj, array, left
when 0
obj
when 1
finder obj, array, right
end
end


--

From: W. James on 19 Dec 2009 03:46
W. James wrote:

> def bin_search obj, array
> len = array.size
> len > 0 and finder( obj, array, 0 ... len )
> end
>
> def split_range range
> first, last = range.min, range.max
> mid = first + ((last - first) / 2.0).round
> [(first .. [first,mid.pred].max), mid, ([mid.succ,last].min ..
> last)] end

Faster:


def bin_search obj, array
len = array.size
len > 0 and finder( obj, array, 0 .. len.pred )
end

def split_range range
first, last = range.first, range.last
mid = first + ((last - first) / 2.0).round
[(first .. [first,mid.pred].max), mid, ([mid.succ,last].min .. last)]
end

--

From: Paul Donnelly on 19 Dec 2009 19:05
"W. James" <w_a_x_man(a)yahoo.com> writes:

> W. James wrote:
>
>> def bin_search obj, array
>> len = array.size
>> len > 0 and finder( obj, array, 0 ... len )
>> end
>>
>> def split_range range
>> first, last = range.min, range.max
>> mid = first + ((last - first) / 2.0).round
>> [(first .. [first,mid.pred].max), mid, ([mid.succ,last].min ..
>> last)] end
>
> Faster:
>
>
> def bin_search obj, array
> len = array.size
> len > 0 and finder( obj, array, 0 .. len.pred )
> end
>
> def split_range range
> first, last = range.first, range.last
> mid = first + ((last - first) / 2.0).round
> [(first .. [first,mid.pred].max), mid, ([mid.succ,last].min .. last)]
> end

Even faster: not writing it in Ruby?
From: gavino on 20 Dec 2009 22:31
On Dec 16, 7:42 am, ccc31807 <carte...(a)gmail.com> wrote:
> On page 61 of Graham's ANSI Common Lisp, he defines bin-search and
> finder, which I have copied below.
>
> I have struggled with this for days, and still don't understand these
> definitions completely. This morning, I wrote bin-search-2, which took
> about ten minutes to write (and about thirty minutes to debug), but I
> understand it thoroughly -- and I am just the merest beginner, barely
> a toe in the water.
>
> I have noticed this about CL in general and in Graham's book in
> particular -- Lispers seem to go to great lengths to make their code
> obtuse, obscurantist, obscure, and difficult to understand. For
> example, in the example below, Why the nested ifs? Why the nested
> lets? I've been reading Miller and Benson 'Lisp: Style and Design' and
> I simply don't understand why tutorials (like ANSI CL -- which I think
> on the whole is a very good book) want to throw up walls to
> understanding. Seems to me that materials targeted toward beginners
> would be written to be clear and understandable.
>
> CC.
>
> ;;; ---------ch_04.lisp-----------------------
> (defparameter v (vector 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
> 35 37 39 41))
>
> (defun bin-search (obj vec)
>   (format t "bin-search ~a ~a~%" obj vec)
>   (let ((len (length vec)))
>     (and (not (zerop len)))
>          (finder obj vec 0 (- len 1))))
>
> (defun finder (obj vec start end)
>   (format t "finder obj: ~a, vec: ~a, start: ~a, end: ~a~%" obj vec
> start end)
>   (format t "     ~a~%" (subseq vec start (+ end 1)))
>   (let ((range (- end start)))
>     (if (zerop range)                      ; outer if test
>         (if (eql obj (aref vec start))       ; inner if test
>             obj                              ; the return obj
>             nil)                             ; else return nil
>           (let ((mid (+ start (round (/ range 2)))))   ; outer then
>             (let ((obj2 (aref vec mid)))
>               (if (< obj obj2)
>                   (finder obj vec start (- mid 1))
>                   (if (> obj obj2)
>                       (finder obj vec (+ mid 1) end)
>                       obj)))))))
>
> (defun bin-search-2 (obj vec &optional (start 0))
>   (let*((len (length vec))
>         (mid (floor (/ len 2))))
>   (format t "bin-search-2 obj: ~a, vec: ~a, start ~a, end: ~a, mid: ~a~
> %" obj vec start len mid)
>   (cond ((zerop len) nil)
>         ((= obj (svref vec mid)) obj)
>         ((< obj (svref vec mid)) (bin-search-2 obj (subseq vec start
> mid)))
>         ((> obj (svref vec mid)) (bin-search-2 obj (subseq vec (+ mid
> 1) len))))))
>
> ;; I don't know how to set 'start' to 0 by default, other than by
> making it optional.
> ;; I would appreciate help with this.

amen brother I find reading my copy is ansi common lips is liek
drinking a pan galatic gargle blaster!
From: Chris Barts on 27 Dec 2009 07:30
Pascal Costanza <pc(a)p-cos.net> writes:

> On 18/12/2009 03:51, Barry Margolin wrote:
>> In article
>> <404e1698-289b-441e-9d0b-635b432f7781(a)a21g2000yqc.googlegroups.com>,
>> w_a_x_man<w_a_x_man(a)yahoo.com> wrote:
>>
>>> Guy L. Steele, Jr., July 1989:
>>>
>>> I think we may usefully compare the approximate number of pages
>>> in the defining standard or draft standard for several
>>> programming languages:
>>>
>>> Common Lisp 1000 or more
>>> COBOL 810
>>> ATLAS 790
>>> Fortran 77 430
>>> PL/I 420
>>> BASIC 360
>>> ADA 340
>>> Fortran 8x 300
>>> C 220
>>> Pascal 120
>>> DIBOL 90
>>> Scheme 50
>>
>> This is a little unfair, because the Common Lisp base language includes
>> lots of things that would be in libraries in most other languages, e.g.
>> hash tables, sequences, association lists, and portable pathnames. In
>> fact, even types that are basic primitives in Lisp, such as linked
>> lists, imaginary numbers, and symbols, would generally be in libraries
>> in traditional languages.
>
> I think there is a change in perspective now. Younger generations
> nowadays consider that these things should be part of a language, and
> that Common Lisp is actually too small and should have even more.

Which is why we have Clojure (for which there is another little troll in
this very group), which brings all of Java into Lisp without actually
making Lispers write in Java. The fundamental problem with that is it
doesn't bring in any well-designed class libraries along with it.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8
Prev: Question from a non-user: Garbage Collection
Next: Loading a file into a running image with Swank