Algorithms: Why nobody says that
Acid Broker
I see how very often older algorithms are still used just why there aren't
places where to take the newest.
for example, for a simple sorting, there are bubble sort, shell sort, quick
sort and many others
Quick sort should be faster (imho), and please don't say "each algorithm has
its field"
because i proved how that's not true
What i am wondering if there is a place where to see "the best of " about
algorithms.
That would be useful although some notes stating "this algorithm replaces
the older one xxxxx"
Hans-Bernhard Broeker
> for example, for a simple sorting, there are bubble sort, shell
> sort, quick sort and many others Quick sort should be faster (imho),
> and please don't say "each algorithm has its field" because i proved
> how that's not true
You haven't, because it isn't. Quicksort is fastest only in the
average case. That's a truth, and just because you don't want to hear
it won't make it go away.
Every given implementation of quicksort has one particular pattern of
inputs for which its performance will be O(n^2), which is quite
inacceptable. That particular pattern may be hard to find, and it may
hardly ever occur in a given application, but that doesn't mean the
problem is not there.
Other algorithms do outperform quicksort both in this respect
(e.g. Heapsort, which is O(n*log(n)) even in the worst case), and in
others: for very short inputs, it's trivially easy to beat quicksort;
same for known-almost-sorted inputs. And for input that doesn't fit
into RAM, quicksort is plain horrible.
Don Knuth didn't write a whole 600-page volume of TAoCP just about
searching and sorting just for the fun of doing it.
> What i am wondering if there is a place where to see "the best of "
> about algorithms.
No, simply because the thing you're looking for does not exist. The
world is not as simple as you want to believe.
--
Hans-Bernhard Broeker (bro...@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Jerzy Karczmarczuk
> Acid Broker <acidbro^@yahoo.com> wrote:
>
>
>>for example, for a simple sorting, there are bubble sort, shell
>>sort, quick sort and many others Quick sort should be faster (imho),
>>and please don't say "each algorithm has its field" because i proved
>>how that's not true
>
>
> You haven't, because it isn't. Quicksort is fastest only in the
> average case. That's a truth, and just because you don't want to hear
> it won't make it go away.
>
> Every given implementation of quicksort has one particular pattern of
> inputs for which its performance will be O(n^2), which is quite
> inacceptable.
There are other issues.
1. Quicksort typical implementation is well adapted to random-access
arrays, much less to sequential structures, such as lists. Mergesort
wins then (typically).
2. There are contexts where the sorted data has first to be gathered
dynamically (say, a sorted listing of a directory), and the acquisition
takes much more time than the actual sorting. Then, an *incremental*
algorithm (insertion sort, or, better, heapsort) will behave better
than quicksort, if the acquisition and the sorting can proceed in two
threads.
>>What i am wondering if there is a place where to see "the best of "
>>about algorithms.
>
> No, simply because the thing you're looking for does not exist. The
> world is not as simple as you want to believe.
First of all, in all serious cases the *best* algorithm *provably* does not
exist.
Second, in practical programming the brutal machine efficiency is often
less important than human resources, and humans master better - by definition
the stuff which is taught and implemented for years. Even if a new
algorithm does in two seconds what an old one finishes in 10 minutes, this
is not a deal if the debugging of the first one takes three days. And,
mind you, I didn't mention the time necessary to *learn* the new algorithm.
===
Maestro Acid Broker asks "why nobody says that". Actually almost everybody
with some experience knows such things.This is not a criticism of a young
impatient mind, but a delicate suggestion that such questions should be
better formulated in a more modest way.
Jerzy Karczmarczuk
Caen, France
Acid Broker
"Jerzy Karczmarczuk" <kar...@info.unicaen.fr> ha scritto nel messaggio
news:3EEF4212...@info.unicaen.fr...
> There are other issues.
> 1. Quicksort typical implementation is well adapted to random-access
> arrays, much less to sequential structures, such as lists. Mergesort
> wins then (typically).
> 2. There are contexts where the sorted data has first to be gathered
> dynamically (say, a sorted listing of a directory), and the
acquisition
> takes much more time than the actual sorting. Then, an *incremental*
> algorithm (insertion sort, or, better, heapsort) will behave better
> than quicksort, if the acquisition and the sorting can proceed in two
> threads.
hey hey, i gave just an example. ok, you both have few better sorting method
what i am wondering is *why should i practice all before to choose the best
one for my scopes*?
> >>What i am wondering if there is a place where to see "the best of "
> >>about algorithms.
> > No, simply because the thing you're looking for does not exist. The
> > world is not as simple as you want to believe.
> First of all, in all serious cases the *best* algorithm *provably* does
not
> exist.
I don't believe that
> Maestro Acid Broker asks "why nobody says that".
Hmm? are you my brother?
>Actually almost everybody
> with some experience knows such things.This is not a criticism of a young
> impatient mind, but a delicate suggestion that such questions should be
> better formulated in a more modest way.
i think you didn't figure out my question
Stephen H. Westin
> "Jerzy Karczmarczuk" <kar...@info.unicaen.fr> ha scritto nel messaggio
> news:3EEF4212...@info.unicaen.fr...
> > Hans-Bernhard Broeker wrote:
> > > Acid Broker <acidbro^@yahoo.com> wrote:
>
>
> > There are other issues.
> > 1. Quicksort typical implementation is well adapted to random-access
> > arrays, much less to sequential structures, such as lists. Mergesort
> > wins then (typically).
> > 2. There are contexts where the sorted data has first to be gathered
> > dynamically (say, a sorted listing of a directory), and the
> acquisition
> > takes much more time than the actual sorting. Then, an *incremental*
> > algorithm (insertion sort, or, better, heapsort) will behave better
> > than quicksort, if the acquisition and the sorting can proceed in two
> > threads.
>
> hey hey, i gave just an example.
No, you gave an an assertion both that there is a "best" sorting
algorithm and that Quicksort might be it.
> ok, you both have few better sorting method
> what i am wondering is *why should i practice all before to choose the best
> one for my scopes*?
By "practice all" I assume that you mean testing every possible sort
algorithm. That's not what Jerzy was suggesting. He was suggesting
that it's important to know something about your problem and about the
advantages and drawbacks of different algorithms. People go to college
to learn this. It's really not a waste of time.
> > >>What i am wondering if there is a place where to see "the best of "
> > >>about algorithms.
>
> > > No, simply because the thing you're looking for does not exist. The
> > > world is not as simple as you want to believe.
>
> > First of all, in all serious cases the *best* algorithm *provably* does
> not
> > exist.
>
> I don't believe that
Then you're ignorant, and apparently don't want to learn. We thought
you were asking a question, but perhaps you just want a fight.
You asserted something, and Jerzy refuted it with examples. Your
response is "I don't believe that". Why don't you believe it?
<snip>
> >Actually almost everybody
> > with some experience knows such things.This is not a criticism of a young
> > impatient mind, but a delicate suggestion that such questions should be
> > better formulated in a more modest way.
>
> i think you didn't figure out my question
Could that be because you didn't phrase it well?
I think there were several related questions in your original article:
1. Why do people bother with different (older) algorithms to
solve a certain problem? Why not just use the newest one?
2. Why isn't there a Web site somewhere that just tells me which is the
best algorithm for each problem?
3. Why isn't there a Web site somewhere that tells me "algorithm B
replaced algorithm A"?
Jerzy tried to answer those questions. And the answer is, that there
is usually no "best" algorithm to solve a certain class of
problems. There are advantages and drawbacks to any good algorithm,
and to make a good choice, you must understand both the algorithms and
the specifice of your problem.
Imagine demanding to know the "best" automobile. It depends on what
your needs are: some are faster, some more economical, some more
stylish, and some carry more. The "best" one for you won't be "best"
for me.
If both of us have misunderstood your question, please
explain. Perhaps even in your netive language; I have some competence
in German, and I suspect Jerzy is fluent in both French and Polish.
--
-Stephen H. Westin
Any information or opinions in this message are mine: they do not
represent the position of Cornell University or any of its sponsors.
gruhn
And it was smacked down by people who know better.
> you both have few better sorting method
Straw man. Is this because you want to be disingenuous or because you didn't
understand their posts?
> what i am wondering is *why should i practice all before to choose the
best
> one for my scopes*?
Are you a serious programmer? To learn what you obviously don't know.
Are you just a script kiddie? No reason. Use a bubble sort.
> I don't believe that
Ah, science by faith. Even Al Einstein turned out wrong when he chose that
approach.
> i think you didn't figure out my question
"Why can't somebody just tell me the one best answer? I know it exists, in
spite of all evidence to the contrary, because I have belief on my side."
It's right next to the "Make Art" button.
Your question has been figured out. It was stated plainly enough and
addressed on it's face. You asked "is there a place to see 'the best of'
about algorithms?" The answer was "No, as the question assumes a state which
does not exist.
You also asked about the existence of "this algorithm replaces the older one
xxxxx". This was not addressed directly but indirectly through answer to the
previous one. I further add that in asking the question you show that you
don't understand the domain. The trick now is to stop insisting people
answer your incorrect questions and pay attention to the answers. You might
learn something.
Heck, if you learn enough you might design a better algorithm for something.
Or be able to look at two existing ones and chose the best one for your
situation. Wouldn't either of these abilities be better than writing
inefficient code to implement an algorithm somebody else incorrectly tells
you is better than all others?
Just d' FAQs
wrote:
>What i am wondering if there is a place where to see "the best of " about
>algorithms.
There are online repositories of algorithms; some are listed in the
FAQ for this newsgroup, many under one heading.
"Subject 0.07: Where is all the source?"
<http://www.faqs.org/>
No doubt companies competing fiercely have proprietary algorithms as
well, perhaps better than published ones.
The notion that a group of objects as complicated as "algorithms" can
be totally ordered by *any* performance criterion is naive. Not even
as simple a measure as "lines of code" will suffice.
Presumably any time a new algorithm is published it compares itself to
its predecessors (if known), and explains why it is the better choice;
but neither authors nor reviewers know everything published. But there
are deeper obstacles to your wish. (See below for examples.) And while
I agree it would be handy to have a "recommended algorithms" list, the
history of invention shows that a discarded older idea can sometimes
inspire something new and superior.
You mention quicksort, so you may be interested to know what Sedgewick
says about it. His doctoral dissertation under Knuth was the first
ever to analyze the performance of an algorithm in depth, and the one
he chose was quicksort and its variations and neighbors. First, as his
thesis makes quite clear, there is no single "quicksort" (otherwise it
would have been a much shorter thesis). Second, based on his own deep
experience, he recommends implementing Shell's sort unless you really
know what you're doing and can devote the necessary time to tune it.
Quicksort can only *compare* keys, but algorithms like radixsort can
be much faster if you do not have that constraint. Quicksort reorders
equal keys (it is not "stable"), so if you want to sort by, say, first
name then last name, the first names of all "Smiths" will be scrambled
-- probably not what you want.
Many experts read this newsgroup, and frequently their first response
to a request for an algorithm is "What do you want to use it for?". If
you have not yet learned that much, you have much to learn.
I do not blame you for liking quicksort; it is a lovely algorithm. As
Italians say,
Il primo amore non si scorda mai.
(You never forget your first love.)
But also remember
A ogni uccello il suo nido è bello.
(To every bird, his own nest is beautiful.)
(I don't speak Italian, but the header on your post suggests you do.)
Sean Hamilton
| for example, for a simple sorting, there are bubble sort,
| shell sort, quick sort and many others
| Quick sort should be faster (imho), and please don't say
| "each algorithm has its field"
To use your example, quick sort may be faster than most, but speed isn't
everybody's priority. For instance on an embedded system with little or no
extra memory, bubble sort or variations is about the only available option.
Not everything must be the best at something, though.
sh
Robert Penz
> There are lot of algorithms in order to do the same graphical thing
> I see how very often older algorithms are still used just why there aren't
> places where to take the newest.
>
> for example, for a simple sorting, there are bubble sort, shell sort,
> quick sort and many others
> Quick sort should be faster (imho), and please don't say "each algorithm
> has its field"
1. quick sort has a worst case (a bad one)
2. with quick sort you can't say the time it will need to sort something
3. quick sort is not the fastest sorting algo (its fast for a comparing
algo, which can't go below O(n*log n), but there are faster ones. e.g.
Bucket sort oder Radix sort
4. you can't use Quick sort in most Databases, as the table would not fit
into the RAM (you use a better version of the simple Merge Sort (you
replace stuff ;-) .. get a database implementation book )
> because i proved how that's not true
hehe ;-)))
sure sure, yahoo is a good adress for such a claim ;-)
Christer Ericson
aachen.de says...
> [...]
> Every given implementation of quicksort has one particular pattern of
> inputs for which its performance will be O(n^2), which is quite
> inacceptable. That particular pattern may be hard to find, and it may
> hardly ever occur in a given application, but that doesn't mean the
> problem is not there.
That's not quite correct. From an old post of mine:
If the data is partitioned into two equal-size parts at each step,
then quicksort is worst-case O(n log n). Such a split can be done
by using any linear-time median selection algorithm as the
partitioning algorithm, for example the Blum, Floyd, Pratt,
Rivest, and Tarjan one as described in:
Blum M., Floyd, Pratt, Rivest and Tarjan. Time Bounds for Selection.
J Comput Sys Sci 7(4), 1973, 448-461
An improvement, using fewer comparisons is given in:
Dor, Dorit. Uri Zwick. Selecting the median. Proceedings of the
6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 28--37,
1995.
Christer Ericson
Sony Computer Entertainment, Santa Monica
Howie
in German it exists a Algorithm called "angewantes Nichtwissen" freely
translated in "must unknown doing" wich means:
If you will by a car as stephen mentioned. You can´t know if there is
a car that is better for you. At any place on the world, or any
manufactor there will be a car that is better for your desires.
Propably in a few days. But you needs a car now, not in a year or ten
years !
I must decide to get the best car for your knowlege (and cost ;-))
now and by it, even if there is a better one but you don´t know.
This will mean for you:
Just use qsort(or any other algorithm) and be happy that you will not
be bothered with the details of sorting in special cases, or get
the best performance for your app in the last 2%.
Howie
Jerzy Karczmarczuk
>
> I do not blame you for liking quicksort; it is a lovely algorithm. As
> Italians say,
>
> Il primo amore non si scorda mai.
> (You never forget your first love.)
>
> But also remember
>
> A ogni uccello il suo nido è bello.
> (To every bird, his own nest is beautiful.)
But, anyway, the "best algorithm" for anything has something different
to tell you:
"...
Ma Il Mio Mistero E' Chiuso In Me,
Il Nome Mio Nessun Sapra' No, No,
..."
(Probably all of you have heard it one day, unless you hate Italian opera.
That's why, with your permission, I don't translate it...)
Con i migliori auguri di
Jerzy Karczmarczuk
Olaf Delgado
> in German it exists a Algorithm called "angewantes Nichtwissen" freely
> translated in "must unknown doing" wich means:
Not so freely translated: "applied ignorance".
Cheers,
Olaf
PS: Just to prove the point that Germans are excessively pedantic,
it is "angewandtes". At least it was, before the spelling reform. :-)
Just d' FAQs
<kar...@info.unicaen.fr> wrote:
>But, anyway, the "best algorithm" for anything has something different
>to tell you:
>
> "...
> Ma Il Mio Mistero E' Chiuso In Me,
> Il Nome Mio Nessun Sapra' No, No,
> ..."
Nicely put. :D
Stephen H. Westin
> Hi Acid,
>
> in German it exists a Algorithm called "angewantes Nichtwissen" freely
> translated in "must unknown doing"
I would translate "angewandtes Nichtwissen" as "applied ignorance",
myself.
<snip>
BluDiesel
Just d' FAQs wrote:
> "...
> Ma Il Mio Mistero E' Chiuso In Me,
> Il Nome Mio Nessun Sapra' No, No,
> ..."
>
why all uppercase?
Gernot Hoffmann
Because the message is so important or because the singers
in the opera ALWAYS SHOUT.
Best regards --Gernot Hoffmann
?'s and more ?'s
"Just d' FAQs" <nobod...@mac.com> wrote in message
news:ubhuev0l1itco5q65...@4ax.com...
>
> The notion that a group of objects as complicated as "algorithms" can
> be totally ordered by *any* performance criterion is naive. Not even
> as simple a measure as "lines of code" will suffice.
>
Just an an aside, when people benchmark algorithms they fail to talk about
the hidden cost of an algorithm.
To put this question into context, recently I was browsing thru a set of
papers on bit-reversal algorithms for FFT's and the like. Well, people come
up with some pretty neat algorithms, but I think academia is too prone to
doing things at the O(..) level. What about hard numbers? There are hidden
costs to every algorithm and unless you publish "hard" numbers , its just
sand in the eyes.
I know you'll say "Well, he does mention that my algorithm take xyz cycles
on alpha-beta-gamma processor, while your algorithm takes lmn cycles on
alpha-beta-gamma" - so that's "hard numbers"
No, darling, there NOT !! What he conveniently forgets to mention are the
hidden costs -
1. some "neat" algorithms have some very "neat" data structuring
requirements. Who's gonna count the cycles wasted getting the data in a form
your algorithm could process? ( I refrain from mentioning specific
algorithms coz they are definitely OT for this group, but...)
2. Memory - memory !! - well that neat algorithm really screws me on memory.
What use is it if I need an UltraSparc 10 with unholy amounts of RAM. Well,
my DSP plod along with 64KB, and that too is not all available to me.
3. Good cycles on say a pentium do not necessarily translate to good cycles
on say a DSP! So if algorithm A is great on a pentium, that doesnt mean it
will be equally great on a TigerSHARC!. And O(..) is even more illusory than
cycle numbers - coz by definition O(N) could well be (9 9999x N +
1000000...00000 )!!! operations !!
>
> You mention quicksort, so you may be interested to know what Sedgewick
> says about it. His doctoral dissertation under Knuth was the first
> ever to analyze the performance of an algorithm in depth, and the one
> he chose was quicksort and its variations and neighbors. First, as his
> thesis makes quite clear, there is no single "quicksort" (otherwise it
> would have been a much shorter thesis). Second, based on his own deep
> experience, he recommends implementing Shell's sort unless you really
> know what you're doing and can devote the necessary time to tune it.
>
I havent really read this paper by Sedgewick, but my own experience with
reading "papers" on "best" algorithms, is that the whole concept of a "best"
algorithm is a sham. It just doesnt exist. The only real way of saying
"best" is in terms of algorithms with fuzzy results - "this algorithm
identifies faces in picture better that the others" - that may be - but how
do you say that this algorithm is the best algorithm for doing bit-reversal,
when my processor just doesnt have the hardware required by it?
Its pretty cozy on the PC/workstation universe, but get your hands dirty on
an embedded system, and you realize that things just arent that simple. The
ancilliary considerations KILL you !