skyknight <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)
> > 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.
skyknight <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.
On Mon, 08 Mar 1999 00:18:25 GMT, skyknight <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)))))))
-- Those who do not understand Unix are condemned to reinvent it, poorly. -- Henry Spencer <http://www.hex.net/~cbbrowne/lsf.html> cbbro...@hex.net - "What have you contributed to free software today?..."
-- 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.Blomb...@mailbox.uq.edu.au
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.
> > 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
Erik Naggum <e...@naggum.no> writes: > * 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 [kulls...@ne.mediaone.net] Don't Fear the Penguin!
* 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?
* Johan Kullstam <kulls...@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 Naggum <e...@naggum.no> writes: > * Johan Kullstam <kulls...@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 [kulls...@ne.mediaone.net] Don't Fear the Penguin!
>>>>> In message <lwzp5n9ibs....@copernico.parades.rm.cnr.it> >>>>> On the subject of "Re: binary search?" >>>>> Sent on 09 Mar 1999 09:29:43 +0100 >>>>> Honorable Marco Antoniotti <marc...@copernico.parades.rm.cnr.it> writes: > >> Hrvoje Niksic <hnik...@srce.hr> 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...
* Johan Kullstam <kulls...@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?
