From: skyknight
Subject: binary search?
Date: 
Message-ID: <36E31DBC.BC03C9E7@iname.com>
given a sorted list of integers,
is it possible to write an efficient binary search using lisp?
(Not binary search tree)

From: Sunil Mishra
Subject: Re: binary search?
Date: 
Message-ID: <efy4snw6b3q.fsf@whizzy.cc.gatech.edu>
skyknight <············@iname.com> writes:

> given a sorted list of integers,
> is it possible to write an efficient binary search using lisp?
> (Not binary search tree)

Yes.

Sunil
From: Hrvoje Niksic
Subject: Re: binary search?
Date: 
Message-ID: <87vhgc6a44.fsf@pc-hrvoje.srce.hr>
skyknight <············@iname.com> writes:

> given a sorted list of integers, is it possible to write an
> efficient binary search using lisp?

No, I don't think so.  Binary search relies on accessing nth element
of a list being an O(1) operation, while in Lisp it requires
traversing the list.

Why don't you use vectors instead?
From: Greg Menke
Subject: Re: binary search?
Date: 
Message-ID: <sobginzk.fsf@erols.com>
Why not just use a sorted array as you might do with most any
other language?

Gregm



> skyknight <············@iname.com> writes:
> 
> > given a sorted list of integers, is it possible to write an
> > efficient binary search using lisp?
> 
> No, I don't think so.  Binary search relies on accessing nth element
> of a list being an O(1) operation, while in Lisp it requires
> traversing the list.
> 
> Why don't you use vectors instead?
From: Simon Blomberg
Subject: Re: binary search?
Date: 
Message-ID: <7c00bl$cul$1@bunyip.cc.uq.edu.au>
Why not use a structure?


--
S. P. Blomberg                      Sitting still, being quiet, writing down 
Dept. of Zoology                    numbers, paying attention...
University of Queensland            Science has it all! - Principal Skinner
St Lucia Qld. 4072 Australia                    ··········@mailbox.uq.edu.au
From: Gareth McCaughan
Subject: Re: binary search?
Date: 
Message-ID: <8690d8cr5t.fsf@g.pet.cam.ac.uk>
Simon Blomberg wrote:

> Why not use a structure?

Because array access might be more efficient; and, more to the
point, because even if you do use a structure you'll be storing
the actual elements in an array of some sort.

Unless, of course, you were proposing

(defstruct five-element-list
  first-element second-element third-element fourth-element fifth-element)

(defun binary-search-five-element-list (list element)
  (cond ((= element (five-element-list-third-element list))
         #'five-element-list-third-element)
        ((< element (five-element-list-third-element list))
         (cond ((= element (five-element-list-second-element list))
                #'five-element-list-second-element)
[etc ad nauseam]

:-)

-- 
Gareth McCaughan       Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk  Cambridge University, England.
From: Marco Antoniotti
Subject: Re: binary search?
Date: 
Message-ID: <lwzp5n9ibs.fsf@copernico.parades.rm.cnr.it>
Hrvoje Niksic <·······@srce.hr> writes:

> skyknight <············@iname.com> writes:
> 
> > given a sorted list of integers, is it possible to write an
> > efficient binary search using lisp?
> 
> No, I don't think so.  Binary search relies on accessing nth element
> of a list being an O(1) operation, while in Lisp it requires
> traversing the list.

As KMP has already pointed out, accessing the Nth element in a list is
a O(n) operation in C as well as in Assembly as well as in Eiffel as
well as in Ada as well as in Common Lisp. Not sure about Intercal :)

Therefore, doing a binary search on a list is an "inefficient" thing
regardless of the language one uses.

Cheers

-- 
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it
From: Erik Naggum
Subject: Re: binary search?
Date: 
Message-ID: <3130013677827179@naggum.no>
* Sam Steingold <···@goems.com>
| True in this particular case (list of integers), not quite true in
| general.  If accessing the key (:key) and key comparison (:test) are
| expensive compared to the list traversal, it does make sense to do binary
| search on lists [at least I got a 10% overall speedup out of this on ACL
| and CMUCL].  Please note the usual stuff about premature optimizations.
| It would be wise to use metering.lsp first to make sure this is a
| bottleneck (I did for my case).

  how much would it cost or save to cons up a vector first?  and which
  other valuable features of list make lists win over vectors in the first
  place?

#:Erik
From: Johan Kullstam
Subject: Re: binary search?
Date: 
Message-ID: <m2ww0qp1zj.fsf@sophia.axel.nom>
Erik Naggum <····@naggum.no> writes:

> * Sam Steingold <···@goems.com>
> | True in this particular case (list of integers), not quite true in
> | general.  If accessing the key (:key) and key comparison (:test) are
> | expensive compared to the list traversal, it does make sense to do binary
> | search on lists [at least I got a 10% overall speedup out of this on ACL
> | and CMUCL].  Please note the usual stuff about premature optimizations.
> | It would be wise to use metering.lsp first to make sure this is a
> | bottleneck (I did for my case).
> 
>   how much would it cost or save to cons up a vector first?  and which
>   other valuable features of list make lists win over vectors in the first
>   place?

e.g., if you need to add or remove stuff in the middle, it's easy and
fast using a list structure but somewhat more involved with a vector.

;-)

-- 
                                           J o h a n  K u l l s t a m
                                           [········@ne.mediaone.net]
                                              Don't Fear the Penguin!
From: Erik Naggum
Subject: Re: binary search?
Date: 
Message-ID: <3130021426931539@naggum.no>
* Johan Kullstam <········@ne.mediaone.net>
| e.g., if you need to add or remove stuff in the middle, it's easy and
| fast using a list structure but somewhat more involved with a vector.

  well, I'd argue the exact opposite, just as I'd argue that pushing values
  on vectors will fill-pointers are more efficient than pushing values on
  lists in many cases.

  besides, if you worry about timing in the binary-search-on-lists case,
  you also probably worry enough about it to write functions that are
  efficient destructive operations on vectors-with-fill-pointers.

  in brief, I think Sam's 10% speedup is a case of becoming satisfied with
  an optimization.  often, much more dramatic wins can be obtained by doing
  something _very_ different than just tuning a particular choice.

#:Erik
From: Johan Kullstam
Subject: Re: binary search?
Date: 
Message-ID: <m2r9qxpnx4.fsf@sophia.axel.nom>
Erik Naggum <····@naggum.no> writes:

> * Johan Kullstam <········@ne.mediaone.net>
> | e.g., if you need to add or remove stuff in the middle, it's easy and
> | fast using a list structure but somewhat more involved with a vector.
> 
>   well, I'd argue the exact opposite, just as I'd argue that pushing values
>   on vectors will fill-pointers are more efficient than pushing values on
>   lists in many cases.

how does a fill pointer let you *insert* new items to the *middle* of
a vector?  i was assuming that you would want to maintain the list in
a sorted state in order to apply a binary sort to it.  i suppose you
could fill and then shift everything over with a copy.  or have i
failed to completely grasp the full power of the fill-pointer?

>   besides, if you worry about timing in the binary-search-on-lists case,
>   you also probably worry enough about it to write functions that are
>   efficient destructive operations on vectors-with-fill-pointers.

this was never meant to be serious.  large lists are not about speed
efficiency.  i don't think sam was completeyl serious either.  it's
just a fit of whimsy to see if it were any way possible to justify
binary searching a list.  if compares were horribly expensive in
comparison to the elt, then maybe there would be a point.

>   in brief, I think Sam's 10% speedup is a case of becoming satisfied with
>   an optimization.  often, much more dramatic wins can be obtained by doing
>   something _very_ different than just tuning a particular choice.

yes, of course.  binary trees, hash tables &c.

-- 
                                           J o h a n  K u l l s t a m
                                           [········@ne.mediaone.net]
                                              Don't Fear the Penguin!
From: Erik Naggum
Subject: Re: binary search?
Date: 
Message-ID: <3130078479648733@naggum.no>
* Johan Kullstam <········@ne.mediaone.net>
| how does a fill pointer let you *insert* new items to the *middle* of
| a vector?

  you provided us with a sample argument, not the definitive argument that
  I asked Sam Steingold to provide, and I answered you with another sample
  argument to show that your sample argument was not the definitive
  argument I was looking for.  why do you need to defend yourself?

| i was assuming that you would want to maintain the list in a sorted state
| in order to apply a binary sort to it.

  as you can see, your assumptions spawned your answer, and my assumptions
  spawned mine.  since I didn't ask you, but Sam Steingold, I could frankly
  not care _less_ whether you think your assumptions are better than mine.

| i suppose you could fill and then shift everything over with a copy.  or
| have i failed to completely grasp the full power of the fill-pointer?

  I think there are several things you have failed to grasp, but I can't
  say whether the fill-pointer is among them or not.  however, with this:

| this was never meant to be serious.  ...  i don't think sam was
| completeyl serious either.

  you show that you failed _utterly_ to understand my question to Sam.

| it's just a fit of whimsy to see if it were any way possible to justify
| binary searching a list.

  I didn't know you controlled Sam Steingold and know what he thinks, what
  motivates him, and how he will react.  I still doubt that you do.

  the useless opinions and generally silly responses from Johan Kullstam
  having been noted, I would like to ask Sam to answer the question, as I
  happen to believe that one might sometimes want to use a list instead of
  a vector, depending on a host of circumstances, just as I tried to show
  that one might want to use a vector where the standard idiom is to use a
  list.  I can think of several algorithms that usefully might delay
  representational issues, but no applications of such algorithms.  Sam?

#:Erik
From: Christopher Browne
Subject: Re: binary search?
Date: 
Message-ID: <eluF2.24835$YV6.12402@news2.giganews.com>
On 09 Mar 1999 09:29:49 -0500, Sam Steingold <···@goems.com> wrote:
>>>>> In message <··············@copernico.parades.rm.cnr.it>
>>>>> On the subject of "Re: binary search?"
>>>>> Sent on 09 Mar 1999 09:29:43 +0100
>>>>> Honorable Marco Antoniotti <·······@copernico.parades.rm.cnr.it> writes:
> >> Hrvoje Niksic <·······@srce.hr> writes:
> >> 
> >> > skyknight <············@iname.com> writes:
> >> > 
> >> > > given a sorted list of integers, is it possible to write an
> >> > > efficient binary search using lisp?
> >> > 
> >> > No, I don't think so.  Binary search relies on accessing nth element
> >> > of a list being an O(1) operation, while in Lisp it requires
> >> > traversing the list.
> >> 
> >> As KMP has already pointed out, accessing the Nth element in a list is
> >> a O(n) operation in C as well as in Assembly as well as in Eiffel as
> >> well as in Ada as well as in Common Lisp. Not sure about Intercal :)
> >> 
> >> Therefore, doing a binary search on a list is an "inefficient" thing
> >> regardless of the language one uses.
>
>True in this particular case (list of integers), not quite true in
>general.  If accessing the key (:key) and key comparison (:test) are
>expensive compared to the list traversal, it does make sense to do
>binary search on lists [at least I got a 10% overall speedup out of this
>on ACL and CMUCL].  Please note the usual stuff about premature
>optimizations.  It would be wise to use metering.lsp first to make sure
>this is a bottleneck (I did for my case).

That presumes that key comparison cost amounts proportionate with the
size of the list.  

That's a situation where optimizations have likely been *post*poned too
long... 

-- 
Linux is obsolete
(Andrew Tanenbaum)
········@hex.net- <http://www.ntlug.org/~cbbrowne/lsf.html>
From: Kent M Pitman
Subject: Re: binary search?
Date: 
Message-ID: <sfwg17glna0.fsf@world.std.com>
skyknight <············@iname.com> writes:

> given a sorted list of integers,
> is it possible to write an efficient binary search using lisp?
> (Not binary search tree)

The question sounds odd.  Why does Lisp have anything to do with it?
Would you expect this answer to be different for other languages?
That is, do you believe it's possible to write an efficient binary
search of a sorted list of integers in ANY language?

If by efficient, you mean "can Lisp skip ahead and find elements
farther down the list without going through the preceding pointers?"
the answer sounds like "no" to me (though it would be true for any
language, not just Lisp).  What a list IS is a pointer-based data
structure.  One can't random-access its elements by definition, not by
limitation of Lisp.  As a rule, Lisp has no special ESP nor does it do
things beyond the realm of mathematics or physics.

If by efficient you mean, "can Lisp search a given data structure in a
manner that is algorithmically optimal for the inherent strengths and
weaknesses of that data structure?" the answer is much more likely 
to be "yes", pretty much within the same kinds of bounds that affect
other languages.
From: Christopher B. Browne
Subject: Re: binary search?
Date: 
Message-ID: <slrn7e6gsh.akp.cbbrowne@godel.brownes.org>
On Mon, 08 Mar 1999 00:18:25 GMT, skyknight <············@iname.com>
posted: 
>given a sorted list of integers,
>is it possible to write an efficient binary search using lisp?
>(Not binary search tree)

Are you requiring that answers ignore other data structures as
options?

Searches across lists take O(N) time, *always.* That's part of the way
lists work.

If you were willing to have that be a "sorted *VECTOR* of integers,"
then it would indeed be a useful notion to do a binary search through
that list.

;;;; Do a binary search
(defun
  binary-search-vector (vect value begin end)
  (let ((left (- end begin)))
    (if (zerop left)
	(if (eql value (aref vect begin))
	    value
	  nil)
      (let
	  ((midpoint (round (+ begin (/ left 2)))))
	(let
	    ((midvalue (aref vect midpoint)))
	  (if (< value midvalue)
	      (binary-search-vector vect value begin (- midpoint 1))
	    (if (> value midvalue)
		(binary-search-vector vect value (+ midpoint 1) end)
	      obj)))))))


> (binary-search-vector '#(0 23 25 478 8384 843218) 25 0 6)
T
> (binary-search-vector '#(0 23 25 478 8384 843218) 88 0 6)
NIL        

(This works with CLISP...)

-- 
Those who do not understand Unix are condemned to reinvent it, poorly. 	
-- Henry Spencer          <http://www.hex.net/~cbbrowne/lsf.html>
········@hex.net - "What have you contributed to free software today?..."