Re: Intro to Programming w/ Machine Language

From: Willem (willem_at_stack.nl)
Date: 02/27/05 

Date: Sun, 27 Feb 2005 11:10:21 +0000 (UTC)

Randall wrote:
) "Randy Howard" <randyhoward@FOOverizonBAR.net> wrote in message
) news:MPG.1c8aef4f4ed697ed98a0d3@news.verizon.net...
)> If n is sufficiently large, the O(n) complexity obviously matters.
)
) You missed the whole point.
) When people use asymptotic performance predictions as an
) excuse to not bother with optimization, the battle is already lost.

You never made that point. You only stated that big-oh complexity
didn't matter. And I never stated anything even remotely like that
you should use big-oh predictions as an excuse, so I don't know where
you got that from.

) The bottom line is that, except for a few well-known algorithms,
) it generally isn't *possible* to substitute an algorithm with better
) asymptotic complexity for the ones found in typical programs.

Not if the algorithms were carefully chosen in the first place.
But you're talking about programmers who are 'sloppy', and I see
no argument why they would not be sloppy in the big-Oh sense.

And even worse: algorithms with a worse big-oh time complexity tend to be
much faster! on a smaller scale. So it could even be that not looking at
big-oh, but looking at speed as such, a programmer could choose the worse
time complexity because he expects the datasets to remain small.

) For example, where's the O(n) or O( n lgn ) algorithm that's
) going to make the browser run so much faster?

You may have seen my example about keeping a sorted list of
directory contents. This is an actual real-world example.
Or, much more prevalent, the choice of datatypes for search lists,
such as hashing, search trees, skip lists, etcetera. Most programmers
will decide what datatype to use based on what they're most familiar with.

) In most real world applications, such algorithms don't exist. Therefore,
) the constant is all you've got to play with.

This is an unfounded assertion, and thinking like this is what brought
the world all those pieces of software that don't scale well.
Why do you think the MS registry is sooo fucking slow ?
Because of a constant factor, or because of big-oh problems ?

) Around this particular newsgroup, it's pretty easy to find
) constants like 5x and 10x. Doesn't happen all the time, mind
) you, but it does happen. Coming up with a factor of two isn't
) all that difficult to do.

Around this newsgroup, you equally easily find factors like lgn as well.
Especially in the datatype department.

) Unless, of course, there is no better algorithm (in an
) asymptotic case). People throw this concept around
) like you can take out one algorithm and easily replace
) it with a faster one when necessary. In practice, most
) programs are already operating at O(n) (or even O(1))
) and they are still too slow.

In practice, there are a lot of programs floating around that use
sub-optimal datatypes and algorithms, in the big-oh sense.
You seem to be assuming that programmers *do* know the optimal algorithms
in the big-oh sense, but *don't* know how to implement them efficiently.
This seems like an odd discrepancy in your thinking.

SaSW, Willem 

-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT