binary search?
Sunil Mishra
> given a sorted list of integers,
> is it possible to write an efficient binary search using lisp?
> (Not binary search tree)
Yes.
Sunil
Greg Menke
Why not just use a sorted array as you might do with most any
other language?
Gregm
> skyknight <skykni...@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?
skyknight
is it possible to write an efficient binary search using lisp?
Hrvoje Niksic
> 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
Kent M Pitman
> 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.
Christopher B. Browne
posted:
>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>
cbbr...@hex.net - "What have you contributed to free software today?..."
Simon Blomberg
--
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 S.Blo...@mailbox.uq.edu.au
Gareth McCaughan
> 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,
gj...@dpmms.cam.ac.uk Cambridge University, England.
Marco Antoniotti
Hrvoje Niksic <hni...@srce.hr> writes:
> skyknight <skykni...@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
Johan Kullstam
> * Sam Steingold <s...@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
[kull...@ne.mediaone.net]
Don't Fear the Penguin!
Erik Naggum
| 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
Erik Naggum
| 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
Johan Kullstam
> * Johan Kullstam <kull...@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.
Christopher Browne
>>>>> In message <lwzp5n9...@copernico.parades.rm.cnr.it>
>>>>> On the subject of "Re: binary search?"
>>>>> Sent on 09 Mar 1999 09:29:43 +0100
>>>>> Honorable Marco Antoniotti <mar...@copernico.parades.rm.cnr.it> writes:
> >> Hrvoje Niksic <hni...@srce.hr> writes:
> >>
> >> > skyknight <skykni...@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.
>
>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)
cbbr...@hex.net- <http://www.ntlug.org/~cbbrowne/lsf.html>
Erik Naggum
| 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