Prev: Question from a non-user: Garbage Collection
Next: Loading a file into a running image with Swank
From: William James on 16 Dec 2009 16:12
ccc31807 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.


a = %w(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
35 37 39 41).map{|s| s.to_i}

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

def finder obj, array, first, last
span = last - first
if span.zero?
obj == array[first] ? obj : nil
else
mid = first + (span / 2.0).round
case obj <=> array[mid]
when -1
finder obj, array, first, mid.pred
when 0
obj
when 1
finder obj, array, mid.succ, last
end
end
end


--

From: Rahul Jain on 16 Dec 2009 17:01
ccc31807 <cartercc(a)gmail.com> writes:

> I have noticed this about CL in general and in Graham's book in
> particular

Huh? how is that a sensible phrase? Graham is opposed to CL in general.

--
Rahul Jain
rjain(a)nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Paul Donnelly on 16 Dec 2009 17:06
"William James" <> writes:

> ccc31807 wrote:
>
>> 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.
>
> a = %w(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
> 35 37 39 41).map{|s| s.to_i}
>
> def bin_search obj, array
> len = array.size
> len > 0 and finder( obj, array, 0, len.pred )
> end
>
> def finder obj, array, first, last
> span = last - first
> if span.zero?
> obj == array[first] ? obj : nil
> else
> mid = first + (span / 2.0).round
> case obj <=> array[mid]
> when -1
> finder obj, array, first, mid.pred
> when 0
> obj
> when 1
> finder obj, array, mid.succ, last
> end
> end
> end

I'm glad we can count on you to remind us how much worse things could
be.
From: Alain Picard on 16 Dec 2009 17:45
"William James" <> writes:

>
>
> a = %w(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
> 35 37 39 41).map{|s| s.to_i}
>
> def bin_search obj, array
> len = array.size
> len > 0 and finder( obj, array, 0, len.pred )
> end

[SNIP]

I thought this was comp.lang.lisp. Did I stray into
comp.lang.python by mistake? If so, good, I have quite
a few complaints I'd like to get off my chest...

--ap
From: joswig on 16 Dec 2009 17:46
On 16 Dez., 22:12, "William James" <> wrote:
> ccc31807 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.

Is that Commune Ruby?
http://ruby-std.netlab.jp/

>
> a = %w(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
>        35 37 39 41).map{|s| s.to_i}

wait, in Ruby you can't write a vector of numbers???
Nice!

>
> def bin_search obj, array
>   len = array.size
>   len > 0  and  finder( obj, array, 0, len.pred )
> end
>
> def finder obj, array, first, last
>   span = last - first
>   if span.zero?
>     obj == array[first] ? obj : nil
>   else
>     mid = first + (span / 2.0).round

Wait, you need floating point division and rounding
to get the middle integer index???

>     case obj <=> array[mid]
>       when -1
>         finder obj, array, first, mid.pred
>       when 0
>         obj
>       when 1
>         finder obj, array, mid.succ, last
>     end
>   end
> end



Why so long?


(defun bin-search (obj vec &aux (las (1- (length vec))))
(labels ((finder (s e &aux (r (- e s)) (mid (+ s (truncate r 2))))
(when (<= 0 s e las)
(let ((m (aref vec mid)))
(cond ((= obj m) obj)
((< obj m) (finder s (1- mid)))
(t (finder (1+ mid) e)))))))
(finder 0 las)))


Look, no floating point calculations.

He, and we can write vectors of numbers.

? (bin-search 25 #(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37
39 41))
25

>
> --

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