Comparing lists

[Ron Adam]

Re: Comparing lists

Christian Stapfer wrote:[color=blue]
> "Ron Adam" <rrr@ronadam.co m> wrote in message
> news:jYv4f.1520 52$xl6.59875@to rnado.tampabay. rr.com...
>[color=green]
>>Christian Stapfer wrote:
>>[color=darkred]
>>>"Ron Adam" <rrr@ronadam.co m> wrote in message
>>>news:cTp4f.1 6180$ae.11317@t ornado.tampabay .rr.com...
>>>
>>>
>>>>Christian Stapfer wrote:
>>>>
>>>>
>>>>
>>>>>This discussion begins to sound like the recurring
>>>>>argument s one hears between theoretical and
>>>>>experiment al physicists. Experimentalist s tend
>>>>>to overrate the importance of experimental data
>>>>>(setting up a useful experiment, how to interpret
>>>>>the experimental data one then gathers, and whether
>>>>>one stands any chance of detecting systematic errors
>>>>>of measurement, all depend on having a good *theory*
>>>>>in the first place). Theoreticians, on the other hand,
>>>>>tend to overrate the importance of the coherence of
>>>>>theories . In truth, *both* are needed: good theories
>>>>>*and* carefully collected experimental data.
>>>>>
>>>>>Regards,
>>>>>Christia n
>>>>
>>>>An interesting parallel can be made concerning management of production
>>>>vs
>>>>managemen t of creativity.
>>>>
>>>>In general, production needs checks and feedback to insure quality, but
>>>>will often come to a stand still if incomplete resources are available.
>>>>
>>>>Where as creativity needs checks to insure production, but in many cases
>>>>can still be productive even with incomplete or questionable resources.
>>>>The quality may very quite a bit in both directions, but in creative
>>>>tasks, that is to be expected.
>>>>
>>>>In many ways programmers are a mixture of these two. I think I and
>>>>Steven
>>>>use a style that is closer to the creative approach. I get the feeling
>>>>your background may be closer to the production style.
>>>
>>>
>>>This diagnosis reminds me of C.G. Jung, the psychologist,
>>>who, after having introduced the concepts of extra- and
>>>introversion , came to the conclusion that Freud was
>>>an extravert whereas Adler an introvert. The point is
>>>that he got it exactly wrong...
>>>
>>> As to the value of complexity theory for creativity
>>>in programming (even though you seem to believe that
>>>a theoretical bent of mind can only serve to stifle
>>>creativity ), the story of the discovery of an efficient
>>>string searching algorithm by D.E.Knuth provides an
>>>interestin g case in point. Knuth based himself on
>>>seemingly quite "uncreative ly theoretical work" (from
>>>*your* point of view) that gave a *better* value for
>>>the computational complexity of string searching
>>>than any of the then known algorithms could provide.
>>>
>>>Regards,
>>>Christian[/color]
>>
>>[color=darkred]
>>>(even though you seem to believe that
>>>
>>>>a theoretical bent of mind can only serve to stifle
>>>>creativit y)[/color]
>>
>>No, that is not at all what I believe. What I believe is, "The insistence
>>of strict conditions can limit creative outcomes."[/color]
>
>
> That's agreed. But going off *blindly*experi menting*
> without trying to relate the outcome of that experimenting
> back to ones theoretical grasp of the work one is doing
> is *not* a good idea. Certainly not in the long run.
> In fact, muddling-trough and avoiding the question
> of suitable theoretical support for one's work is
> perhaps more typical of production environments.
>
>[color=green]
>>The lack of those limits does not prevent one from using any resources
>>(including theoretical ones) if they are available.
>>
>>You seem to be rejecting experimental results in your views.[/color]
>
>
> Not at all. You must have mis-read (or simply not-read)
> my posts in this thread and are simply projecting wildly,
> as psychoanalysts would call it, that is all.[/color]

The term 'rejecting' was the wrong word in this case. But I still get
the impression you don't trust experimental methods.

[color=blue]
> As it appears, not even my most recent post has had
> *any* recognizable effect on your thoroughly
> misapprehending my position.
>
> Regards,
> Christian[/color]

In most cases being able to see things from different view points is
good. So I was offering an additional view point, not trying to
implying your's is less correct.

On a more practical level, Python as a language is a dynamic development
process. So the level of completeness of the documentation, and the
language it self, will vary a bit in some areas compared to others. So
as a programmer, it is often much more productive for me to try
something first and then change it later if it needs it. Of course I
would test it with a suitable range of data that represents the expected
range at some point.

In any case, this view point has already been expressed I think. <shrug>

Cheers,
Ron

[Ognen Duzlevski]

Re: Comparing lists - somewhat OT, but still ...

Steven D'Aprano <steve@removeth iscyber.com.au> wrote:[color=blue]
> On Sun, 16 Oct 2005 15:16:39 +0200, Christian Stapfer wrote:[/color]
[color=blue][color=green]
> > It turned out that the VAX compiler had been
> > clever enough to hoist his simple-minded test
> > code out of the driving loop.[/color][/color]
[color=blue]
> Optimizations have a tendency to make a complete mess of Big O
> calculations, usually for the better. How does this support your
> theory that Big O is a reliable predictor of program speed?[/color]

There are many things that you cannot predict, however if the compiler was sufficiently documented and you had the
knowledge of the abovementioned peculiarity/optimization, you could take it into account. Bear in mind that the example
was given to show a problem with a purely experimental approach - it tends to show a tree and ignore the forest.
Sometimes this tree can be respresentative of a forest but many times it might not be.

The way I understood these notations was in terms of algorithmic behavior and data input sizes. It is generally
expected that certain basic operations will have a certain complexity. If this is not the case on a
particular platform (language, interpreter, cpu etc.) then there are several questions to ask: a) is such a deviation
documented?, b) why is there such a deviation in the first place? For example, if something is generally known to be
O(1) and your particular platform makes it O(n) then you have to ask why that is so. There might be a
perfectly good reason but this should still either be obvious or documented.

IMHO, I would rather first explore the theoretical boundaries to a certain approach before wasting time on coding up
stuff. If it is immediately obvious that such an approach will not yield anything acceptable for my own purposes then
what is the point of squeezing performance out of what will be dead-beat code anyways?

Knowing the tool/language/os in depth is a formidable strength and it is always a pleasure to see someone squeeze time
out of a piece of code solely based on knowing the internals of the compiler and/or runtime environment. However, it is
most usually the case that this person will be squeezing time out of a certain order of performance - no amount of
this kind of optimization will move the code to the next order.

Ognen

[Paul Rubin]

Re: Comparing lists - somewhat OT, but still ...

Ognen Duzlevski <maketo@norge.f reeshell.org> writes:[color=blue][color=green]
> > Optimizations have a tendency to make a complete mess of Big O
> > calculations, usually for the better. How does this support your
> > theory that Big O is a reliable predictor of program speed?[/color]
>
> There are many things that you cannot predict, however if the
> compiler was sufficiently documented and you had the knowledge of
> the abovementioned peculiarity/optimization, you could take it into
> account. Bear in mind that the example was given to show a problem
> with a purely experimental approach - it tends to show a tree and
> ignore the forest. Sometimes this tree can be respresentative of a
> forest but many times it might not be.[/color]

Consider the claim that earlier in the thread that adding to a hash
table is approximately O(1):

[Stephen D'Aprano][color=blue]
> And knowing that hash tables are O(1) will not tell you that, will it?
>
> There is only one practical way of telling: do the experiment. Keep
> loading up that hash table until you start getting lots of collisions.[/color]

The complexity of hashing depends intricately on the the data and if
the data is carefully constructed by someone with detailed knowledge
of the hash implementation, it may be as bad as O(n) rather than O(1)
or O(sqrt(n)) or anything like that. Experimentation in the normal
will not discover something like that. You have to actually
understand what's going on. See for example:

http://www.cs.rice.edu/~scrosby/hash/

[Steven D'Aprano]

Re: Comparing lists - somewhat OT, but still ...

On Sun, 16 Oct 2005 20:28:55 +0200, Christian Stapfer wrote:
[color=blue]
> Experiments
> (not just in computer science) are quite
> frequently botched. How do you discover
> botched experiments?[/color]

Normally by comparing them to the results of other experiments, and being
unable to reconcile the results. You may have heard the term "the
experiment was/was not replicable".

How do you discover whether your theory is correct? By comparing it to
itself, or by comparing it to experiment?

Of course you need some theoretical background in order to design your
experiment in the first place, otherwise you have no idea what you are
even looking for. And it is easy to mis-design an experiment, as your
student did, so that it is actually measuring X when you think it is
measuring Y. If you are about to argue against a naive view of the
scientific method where the scientist generates data in a mental vacuum,
don't bother, I understand that.

But fundamentally, calculated Big O values of algorithms on their own are
of virtually zero use in choosing between actual functions. If I tell you
that algorithm X is O(f(N)), what have I told you about it?

Have I told if it is unacceptably slow for some particular data size? No.

Have I told you how much work it will take to implement it? No.

Have I told you how fast my implementation is? No.

Have I told you that it is faster than some other algorithm Y? No.

The only thing I have told you is that in some rough and ready fashion, if
I increase the size of my data N, the amount of work done will increase
very approximately like f(N).

This disconnect between what Big O *actually* means and how you are
recommending we use it makes REAL PRACTICAL DIFFERENCE, and not in a good
way.

Here is a real problem I had to solve some time ago. Without using
regular expressions, I needed to find the position of a target
string in a larger string, but there were multiple targets. I
needed to find the first one.

I ended up using something like:

(untested, and from memory)

def findmany(s, *targets):
minoffset = (len(s)+1, "")
for t in targets:
p = s.find(t)
if p != -1 and p < minoffset[0]:
minoffset = (p, t)
return minoffset[0]

You would look at that, realise that s.find() is O(N) or even O(N**2) -- I
forget which -- and dismiss this as Shlemiel the Painter's algorithm which
is O(N**2) or worse.

http://www.joelonsoftware.com/articles/fog0000000319.html

And you would be right in your theory -- but wrong in your conclusion.
Because then you would do what I did, which is spend hours or days writing
a "more efficient" O(N) searching function in pure Python, which ended up
being 100 times slower searching for a SINGLE target string than my
Shlemiel algorithm was searching for twenty targets. The speed benefit I
got from pushing the character matching from Python to C was so immense
that I couldn't beat it no matter how "efficient" the algorithm was.

If I had bothered to actually profile my original code, I would have
discovered that for any data I cared about, it worked not just acceptably
fast, but blindingly fast. Why would I care that if I had a terrabyte of
data to search for a million targets, it would scale badly? I was
searching text strings of less than a megabyte, for five or six targets.
The Big O analysis I did was completely, 100% correct, and completely,
100% useless. Not just useless in that it didn't help me, but it actually
hindered me, leading me to waste a day's work needlessly looking for a
"better algorithm".



--
Steven.

[Steven D'Aprano]

Re: Comparing lists - somewhat OT, but still ...

On Sun, 16 Oct 2005 14:07:37 -0700, Paul Rubin wrote:
[color=blue]
> The complexity of hashing depends intricately on the the data and if
> the data is carefully constructed by someone with detailed knowledge
> of the hash implementation, it may be as bad as O(n) rather than O(1)
> or O(sqrt(n)) or anything like that. Experimentation in the normal
> will not discover something like that. You have to actually
> understand what's going on. See for example:[/color]


Yes, that is a very good point, and I suppose if a hostile user wanted to
deliberately construct a data set that showed off your algorithm to its
worst behaviour, they might do so. But if you are unlikely to discover
this worst case behaviour by experimentation , you are equally unlikely to
discover it in day to day usage. Most algorithms have "worst case"
behaviour significantly slower than their best case or average case, and
are still perfectly useful.


--
Steven.

[James Dennett]

Re: Comparing lists

Steven D'Aprano wrote:[color=blue]
> On Sat, 15 Oct 2005 18:17:36 +0200, Christian Stapfer wrote:
>
>[color=green][color=darkred]
>>>>I'd prefer a (however) rough characterizatio n
>>>>of computational complexity in terms of Big-Oh
>>>>(or Big-whatever) *anytime* to marketing-type
>>>>characteriz ations like this one...
>>>
>>>Oh how naive.[/color]
>>
>>Why is it that even computer science undergrads
>>are required to learn the basics of Big-Oh and
>>all that?[/color]
>
>
> So that they know how to correctly interpret what Big O notation means,
> instead of misinterpreting it. Big O notation doesn't tell you everything
> you need to know to predict the behaviour of an algorithm. It doesn't even
> tell you most of what you need to know about its behaviour. Only actual
> *measurement* will tell you what you need to know.[/color]

In my experience, I need both knowledge of algorithmic
complexity (in some pragmatic sense) and measurements.
Neither alone is sufficient.

The proponents of algorithmic complexity measures don't
make the mistake of thinking that constants don't matter
for real-world performance, but they also don't make the
mistake of thinking that you can always measure enough
to tell you how your code will perform in all situations
in which it might be used.

Measurement is complicated -- very often, it just shows
you that tuning to match cache sizes is greatly important
to keep the constant factors down. And yes, for small
data sizes often a linear-time algorithm can beat one
whose execution time grows only logarithmically , while
often a logarithmic time is close enough to constant over
the range of interest. How an operation runs on a heavily
loaded system where it shares resources with other tasks
can also be greatly different from what microbenchmarks
might suggest.

If we don't oversimplify, we'll measure some appropriate
performance numbers and combine that with some knowledge
of the effects of caches, algorithmic complexity and other
factors that might matter in given situations. And of
course there will be many situations where programmer time
and simplicity are more important than saving a millisecond,
or even a second, and we won't waste excessive resources in
optimising runtime at the expense of other factors.

-- James

[Paul Rubin]

Re: Comparing lists - somewhat OT, but still ...

Steven D'Aprano <steve@REMOVETH IScyber.com.au> writes:[color=blue]
> But if you are unlikely to discover this worst case behaviour by
> experimentation , you are equally unlikely to discover it in day to
> day usage.[/color]

Yes, that's the whole point. Since you won't discover it by
experimentation and you won't discover it by day to day usage, you may
very well only find out about it when an attacker clobbers you. If
you want to prevent that, you HAVE to discover it by analysis, or at
least do enough analysis to determine that a successful attack won't
cause you a big catastrophe (ok, this is probably the case for most of
the stuff that most of us do).

Sure, there are some applications that are never exposed to hostile
users. That excludes pretty much anything that connects to the
internet or handles data that came from the internet. Any general
purpose development strategy that doesn't take hostile users into
account is of limited usefulness.
[color=blue]
> Most algorithms have "worst case" behaviour significantly slower
> than their best case or average case, and are still perfectly useful.[/color]

Definitely true. However, a lot more of the time than many
implementers seem to think, you have to take the worst case into
account. There's no magic bullet like "experiment s" or "unit tests"
that results in reliable software. You have to stay acutely aware of
what you're doing at every level.

[Alex Martelli]

Re: Comparing lists

Christian Stapfer <nil@dev.nul> wrote:
[color=blue]
> This is why we would like to have a way of (roughly)
> estimating the reasonableness of the outlines of a
> program's design in "armchair fashion" - i.e. without
> having to write any code and/or test harness.[/color]

And we would also like to consume vast amounts of chocolate, while
similarly reclining in comfortable armchairs, without getting all fat
and flabby. Unfortunately, what we would like and what reality affords
are often pretty uncorrelated. No matter how much theoreticians may
love big-O because it's (relatively) easy to compute, it still has two
failings which are often sufficient to rule out its sufficiency for any
"estimate [of] the reasonableness" of anything: [a] as we operate on
finite machines with finite wordsize, we may never be able reach
anywhere even remotely close to the "asymptotic " region where big-O has
some relationship to reality; [b] in many important cases, the
theoretical worst-case is almost impossible to characterize and hardly
ever reached in real life, so big-O is of no earthly use (and much
harder to compute measures such as big-Theta should be used for just
about any practical purpose).

Consider, for example, point [b]. Quicksort's big-O is N squared,
suggesting that quicksort's no better than bubblesort or the like. But
such a characterizatio n is absurd. A very naive Quicksort, picking its
pivot very systematically (e.g., always the first item), may hit its
worst case just as systematically and in cases of practical importance
(e.g., already-sorted data); but it takes just a little extra care (in
the pivot picking and a few side issues) to make the worst-case
occurrences into ones that will not occur in practice except when the
input data has been deliberately designed to damage by a clever and
determined adversary.

Designing based on worst-case occurrences hardly ever makes sense in any
field of engineering, and blind adherence to worst-case assessments can
be an unmitigated disaster, promoting inferior technology just because,
in the WORST imaginable case, the best available technology would fare
no better than the inferior one (even though in 99.99999% of cases the
best technology would perform better, if you're designing based on
worst-case analyses you may not even NOTICE that -- and NEVER, *NEVER*
forget that big-O is nothing BUT "extreme-worst-case" analysis!). Why
bother using prestressed concrete, when, should a large asteroid score a
direct hit, the costly concrete will stand up no better than cheap
bricks, or, for that matter, slightly-damp straw? Why bother doing
(e.g.) random pivot selection in quicksort, when its big-O (i.e.,
worst-case) behavior will remain N-squared, just like naive quicksort,
or, for that matter, bubblesort?


Alex

[Christian Stapfer]

Re: Comparing lists

"Alex Martelli" <aleaxit@yahoo. com> wrote in message
news:1h4knvy.41 r7fw1k4bge7N%al eaxit@yahoo.com ...[color=blue]
> Christian Stapfer <nil@dev.nul> wrote:
>[color=green]
>> This is why we would like to have a way of (roughly)
>> estimating the reasonableness of the outlines of a
>> program's design in "armchair fashion" - i.e. without
>> having to write any code and/or test harness.[/color]
>
> And we would also like to consume vast amounts of chocolate, while
> similarly reclining in comfortable armchairs,[/color]

Maybe some of my inclination towards design
based on suitable *theories* (instead of
self-conditioning through testing) goes back
to the fact that I tend to think about the
design of my programs when no computer happens
to be near at hand to do some such experimenting,
or self-conditioning...
[color=blue]
> without getting all fat and flabby.[/color]

Well, thinking can be hard work. There is no need
to suggest an image of laziness. Thought experiments
are also quite often successful. Hardware engineers
can design very often entire gadgets without doing
a great deal of testing. They usually need to resort
to testing only if they know (or feel?) not to have
a sufficiently clear *theoretical* grasp of the
behavior of some part of their design.
[color=blue]
> Unfortunately, what we would like and what reality affords
> are often pretty uncorrelated. No matter how much theoreticians may
> love big-O because it's (relatively) easy to compute, it still has two
> failings which are often sufficient to rule out its sufficiency for any
> "estimate [of] the reasonableness" of anything: [a] as we operate on
> finite machines with finite wordsize, we may never be able reach
> anywhere even remotely close to the "asymptotic " region where big-O has
> some relationship to reality; [b] in many important cases, the
> theoretical worst-case is almost impossible to characterize and hardly
> ever reached in real life, so big-O is of no earthly use (and much
> harder to compute measures such as big-Theta should be used for just
> about any practical purpose).[/color]

But the fact remains that programmers, somewhat
experienced with the interface a module offers,
have a *rough*idea* of that computational complexity
attaches to what operations of that interface.
And having such a *rough*idea* helps them to
design reasonably performing programs much more
quickly.
Big-Oh and other asymptotic complexity measures
really do have *this* advantage over having
acquired, by way of conditioning experiences,
some such *rough*idea* of computational complexity:
they capture at least some of that "rough idea"
in a somewhat more easily communicable and much
more precise fashion.

Maybe you and Steven prefer to be conditioned,
Pavlov style, by the wonderful experiences that
you get while testing? - This is perhaps really
one of my *worst* psychological handicaps, I must
admit: that I don't *like* to get conditioned
like that, no matter how good it feels, no matter
how effective it might be for "practical" work that
one has to do.
I want to be able to really think *about* what
I am doing. And in order to be able to think about
it one usually needs some information about the
implementation, performance wise, of the language
features and the system modules that one might
want to use. If you happen to know of any *better*
way of offering the requisite information than
asymptotic complexity measures then, of course,
I am very grateful to hear more about it.
[color=blue]
> Consider, for example, point [b]. Quicksort's big-O is N squared,
> suggesting that quicksort's no better than bubblesort or the like. But
> such a characterizatio n is absurd. A very naive Quicksort, picking its
> pivot very systematically (e.g., always the first item), may hit its
> worst case just as systematically and in cases of practical importance
> (e.g., already-sorted data); but it takes just a little extra care (in
> the pivot picking and a few side issues) to make the worst-case
> occurrences into ones that will not occur in practice except when the
> input data has been deliberately designed to damage by a clever and
> determined adversary.
>
> Designing based on worst-case occurrences hardly ever makes
> sense in any field of engineering,[/color]

What's wrong with wanting to have a rough idea
of what might happen in the worst case? I believe
many engineers are actually expected to think
about at least some "worst-case" scenarios.
Think of nuclear reactors, airplanes, or
telephone exchanges (and dont' think of Google
for a change). Don't you expect engineers
and scientists designing, for example, a nuclear
reactor, to think hard about what the worst-case
scenario might be? And how likely it might happen?
(And *no* testing whatsoever in that direction,
please!) Not thinking is, admittedly, a lot easier.

<snip/>
[color=blue]
> Why bother doing
> (e.g.) random pivot selection in quicksort, when its big-O (i.e.,
> worst-case) behavior will remain N-squared, just like naive quicksort,
> or, for that matter, bubblesort?[/color]

Because worst-case is not the only measure of
computational complexity that one might be
interested in. For some applications one may
be able to accept relatively bad worst-case
behavior, if it doesn't happen too often.
This is why for these people we might provide
information about average case behavior (and
then the difference between quicksort and
bubblesort clearly shows).
For others, such worst-case behavior may not
be acceptable. For those other applications,
a good worst-case may be what is required.
This is why this second category of programmers
needs to know about the worst-case. - But I am
certainly belaboring the obvious...

Of course, the programs that have been designed
on the basis of such information can (and ought
to be) tested. Then some surprises (*not* predicted
by theory) might happen: but if they do not happen
too often, theory has done a good job - and so has
the programmer...

Regards,
Christian

[Alex Martelli]

Re: Comparing lists

Christian Stapfer <nil@dev.nul> wrote:
[color=blue]
> "Alex Martelli" <aleaxit@yahoo. com> wrote in message
> news:1h4knvy.41 r7fw1k4bge7N%al eaxit@yahoo.com ...[color=green]
> > Christian Stapfer <nil@dev.nul> wrote:
> >[color=darkred]
> >> This is why we would like to have a way of (roughly)
> >> estimating the reasonableness of the outlines of a
> >> program's design in "armchair fashion" - i.e. without
> >> having to write any code and/or test harness.[/color]
> >
> > And we would also like to consume vast amounts of chocolate, while
> > similarly reclining in comfortable armchairs,[/color]
>
> Maybe some of my inclination towards design
> based on suitable *theories* (instead of
> self-conditioning through testing) goes back
> to the fact that I tend to think about the
> design of my programs when no computer happens
> to be near at hand to do some such experimenting,
> or self-conditioning...[/color]

Oh, I am as prone as anybody I know to do SW architecture and design in
bed when the lights are off and I'm sliding into sleep -- just about the
only case in which no computer is handy, or, rather, in which it's
generally unwise to turn the computer on (since it would interfere with
the sleep thing;-). Back before laptops were really affordable and
usable, I used to have a long bus commute, and did a lot of design with
pen and paper; and whiteboards are a popular group-design tool at
Google, no matter how many laptops or desktops happen to be around --
whiteboards are simply more suitable for "socializat ion" around a draft
design's sketch, than any computer-based tool I've ever seen.

But that's *design*, and most often in pretty early stages, too -- quite
a ways from *coding*. At that stage, one doesn't even generally commit
to a specific programming language or other for the eventual
implementation of the components one's considering! Rough ideas of
*EXPECTED* run-times (big-Theta) for various subcomponents one is
sketching are *MUCH* more interesting and important than "asymptotic
worst-case for amounts of input tending to infinity" (big-O) -- for
example, where I sketch-in (mentally, on paper, or on whiteboard) a
"hash table" subcomponent, I consider the *expected* (Theta) performance
(constant-time lookups), definitely NOT the big-O "linear time" lookups
which just MIGHT occur (if, say, all inputs just happened to hash to the
same value)... otherwise, I'd never use hash tables, right?-)

[color=blue][color=green]
> > without getting all fat and flabby.[/color]
>
> Well, thinking can be hard work. There is no need
> to suggest an image of laziness. Thought experiments
> are also quite often successful. Hardware engineers
> can design very often entire gadgets without doing
> a great deal of testing. They usually need to resort
> to testing only if they know (or feel?) not to have
> a sufficiently clear *theoretical* grasp of the
> behavior of some part of their design.[/color]

Having been a hardware designer (of integrated circuits, for Texas
Instruments, and later briefly for IBM), before switching to software, I
can resolutely deny this assertion: only an utter madman would approve a
large production run of an IC who has not been EXTENSIVELY tested, in
simulations and quite possibly in breadboards and later in limited
pre-production runs. And any larger "gadget" USING ICs would be
similarly crazy to skimp on prototyping, simulation, and other testing
-- because, as every HW engineer KNOWS (SW ones often have to learn the
hard way), the distance between theory and practice, in practice, is
much larger than the distance between practice and theory should be in
theory;-).

[color=blue][color=green]
> > Unfortunately, what we would like and what reality affords
> > are often pretty uncorrelated. No matter how much theoreticians may
> > love big-O because it's (relatively) easy to compute, it still has two
> > failings which are often sufficient to rule out its sufficiency for any
> > "estimate [of] the reasonableness" of anything: [a] as we operate on
> > finite machines with finite wordsize, we may never be able reach
> > anywhere even remotely close to the "asymptotic " region where big-O has
> > some relationship to reality; [b] in many important cases, the
> > theoretical worst-case is almost impossible to characterize and hardly
> > ever reached in real life, so big-O is of no earthly use (and much
> > harder to compute measures such as big-Theta should be used for just
> > about any practical purpose).[/color]
>
> But the fact remains that programmers, somewhat
> experienced with the interface a module offers,
> have a *rough*idea* of that computational complexity
> attaches to what operations of that interface.
> And having such a *rough*idea* helps them to
> design reasonably performing programs much more
> quickly.[/color]

A rough idea helps, particularly a rough idea of EXPECTED performance.
[color=blue]
> Big-Oh and other asymptotic complexity measures
> really do have *this* advantage over having
> acquired, by way of conditioning experiences,
> some such *rough*idea* of computational complexity:[/color]

No: big-O is NOT AT ALL a measure, rough or otherwise, of EXPECTED
performance. It's *WORST-CASE*, by definition; and includes no
indications whatsoever of how close to the asymptote one can actually
get on a given finite-size machine. By both issues, it can be totally
misleading -- and, "it's not what you don't know, that hurts... it's
what you know WHICH IS NOT SO". By its MISLEADING characteristics ,
big-O can be SERIOUSLY DAMAGING to the abilty of "designing on the back
of an envelope" (or in your head, or at a whiteboard).
[color=blue]
> they capture at least some of that "rough idea"
> in a somewhat more easily communicable and much
> more precise fashion.[/color]

Entirely precise, and therefore, in such cases as quicksort and hash
tables (hardly "obscure corner cases" -- CENTRAL PILLARS of many
designs!!!) all that more misleading.

[color=blue]
> Maybe you and Steven prefer to be conditioned,
> Pavlov style, by the wonderful experiences that
> you get while testing? - This is perhaps really
> one of my *worst* psychological handicaps, I must
> admit: that I don't *like* to get conditioned
> like that, no matter how good it feels, no matter
> how effective it might be for "practical" work that
> one has to do.[/color]

I like to be able to reason FIRSTLY on the basis of EXPECTED, NORMAL
behavior, corrected in the first order by reasonable prudence and
caution, in the second order by accurate experimentation , and only in
the third order by considerations of worst-case scenarios -- the latter
normally tempered by estimates of their likelihood... which also
requires a rough understanding of CORRELATION between the causes of such
scenarios, which may be present, both directly or indirectly (assuming
that different components interacting in a system "may just happen" to
hit worst-case scenarios for each of them at once may be demonstrably
wrong in either direction -- and NO big-O analysis will ever help with
this crucial kind of task!).
[color=blue]
> I want to be able to really think *about* what
> I am doing. And in order to be able to think about
> it one usually needs some information about the
> implementation, performance wise, of the language
> features and the system modules that one might
> want to use. If you happen to know of any *better*
> way of offering the requisite information than
> asymptotic complexity measures then, of course,
> I am very grateful to hear more about it.[/color]

If you can't think about a design without knowing such details about one
specific implementation of one specific programming language in which
that design might get implemented, I think this strongly suggests you're
giving insufficient attention to the one crucial skill in a designer's
mental armory: *ABSTRACTION*. There are many ways to cultivate one's
abstraction abilities. One of my favorite pastimes is collecting
different renditions of Bach's "Art of the Fugue", for example: Bach
carefully abstracted away the information about which instrument(s) were
supposed to be playing which voice(s), as well as many other details --
because of this, the Art of the Fugue has the highest abstraction level
among all well-known musical compositions, and each rendition may take a
different concrete reading of it. Learn to listen to them and be able
to tell what they have in common, and where they differ: it's a great
lesson in the understanding of abstraction. But it's probably only
appropriate if you like music, and Baroque in particular; other arts and
discipline may no doubt afford similarly good learning experiences, if
you know where to look for them.

Once you're confident about your abilities of abstraction, I suggest you
continue by the exercise of *characterizati on* (of A FEW
implementations , ideally) which Jon Bentley (the programmer, not the
jazz player) suggests pretty close to the start of his masterpiece
"Writing Efficient Programs" (that great book may be hard to come by
these days, but the "Programmin g Pearls" books are also excellent and
communicate mostly the same messages, quite effectively). Get a sense
for the *EXPECTED* (NOT "asymptotic ", for your inputs will NOT tend to
infinity; NOT "worst-case only", don't be THAT pessimistic) behavior of
some primitive operations - the couple of pages I devote to the subject
in the Nutshell chapter on optimization, profiling and testing may
suffice. Then refine your instinct by taking ONE complicated case, such
as the natural mergesort variant known as the timsort, and delving as
deep into its analysis as you dare -- characterize it as best you can
manage WITHOUT testing, simply by reasoning on its code (Tim's essay,
part of the Python source distribution, will be a helpful addition to a
thorought grounding in Knuth's chapter on sorting, for this purpose)...
then see what a difference it makes, to BE able to experiment!

You'll personally traverse, through such exercises, a curve not too
dissimilar from what the whole of Western thought went through in the
discovery and refinement of the experimental method (to some extent it
can be considered in full bloom in the thoughts and works of Galilei):
not the blind flailing around of pure trial and error (which HAD,
however, proved extremely fruitful in eliciting just about all technical
progress up to that age, and later), much less the ungrounded
elucubration of pure theoreticism (which HAD, mind you, given great
results once in a while, e.g. in Euclid, Nagarjuna, Archimedes...) --
but the powerful, fruitful merging of both strands into the incredibly
productive golden braid which has pulled progress up during the last few
centuries.

[color=blue][color=green]
> > Consider, for example, point [b]. Quicksort's big-O is N squared,
> > suggesting that quicksort's no better than bubblesort or the like. But
> > such a characterizatio n is absurd. A very naive Quicksort, picking its
> > pivot very systematically (e.g., always the first item), may hit its
> > worst case just as systematically and in cases of practical importance
> > (e.g., already-sorted data); but it takes just a little extra care (in
> > the pivot picking and a few side issues) to make the worst-case
> > occurrences into ones that will not occur in practice except when the
> > input data has been deliberately designed to damage by a clever and
> > determined adversary.
> >
> > Designing based on worst-case occurrences hardly ever makes
> > sense in any field of engineering,[/color]
>
> What's wrong with wanting to have a rough idea
> of what might happen in the worst case? I believe
> many engineers are actually expected to think
> about at least some "worst-case" scenarios.[/color]

Not extrapolating to infinity.
[color=blue]
> Think of nuclear reactors, airplanes, or
> telephone exchanges (and dont' think of Google
> for a change). Don't you expect engineers
> and scientists designing, for example, a nuclear
> reactor, to think hard about what the worst-case
> scenario might be? And how likely it might happen?[/color]

A square hit by an asteroid of mass tending to infinity? No, I don't
expect nuclear reactors (nor anything else of human conception) to be
designed in consideration of what such an asteroid hit would do. And
yet, that's *EXACTLY* what would be indicated by your theory of big-O as
a guide to design: consider the absolute worst that could conceivably
happen, with *NO* indications WHATSOEVER of how unlikely it might be
(because for simplicity of computation you take limits for misfortune
tending to infinity!!!), and design for THAT.

If our collective ancestors had taken this attitude, we'd still all be
huddling in deep caves (possibly a better protection against "dinosaurs'
killer" levels of asteroid hits!), shivering in the cold (fire is FAR
too dangerous to survive a worst-case analysis, particularly with
damaging elements all tending to infinity, as your love affair with
big-O based designs would certainly indicate!!!). Animal skins? Forget
it!!! Do a perfectly pessimistic worst-case analysis with suitable
extrapolations to infinity and such skins would no doubt carry germs
enough to exterminate the budding human race (not that extinction might
not be preferable to the utterly miserable "lives" the few humans might
lead if "big-O" had guided their design concerns, mind you!-).

[color=blue]
> (And *no* testing whatsoever in that direction,
> please!) Not thinking is, admittedly, a lot easier.[/color]

I would consider ANYBODY who built a nuclear reactor without AMPLE
testing dangerous enough for all of mankind to shoot on sight. I would
expect HUGE amounts of simulation-based testing, followed and
interspersed by prototypes (smaller and simplified) to validate that the
simulations' tests are indeed perfectly respondent to actual reality.

I haven't seen anybody on this thread advocating "not thinking"; if
you're somehow implying that I'm trying to discourage people from
thinking IN USEFUL AND PRODUCTIVE WAYS, I challenge you to point to
anything I wrote here that could be construed that way.
[color=blue]
>
> <snip/>
>[color=green]
> > Why bother doing
> > (e.g.) random pivot selection in quicksort, when its big-O (i.e.,
> > worst-case) behavior will remain N-squared, just like naive quicksort,
> > or, for that matter, bubblesort?[/color]
>
> Because worst-case is not the only measure of
> computational complexity that one might be
> interested in. For some applications one may
> be able to accept relatively bad worst-case
> behavior, if it doesn't happen too often.[/color]

But big-O, which is what you advocate, gives *NO* indication of how
likely or unlikely it might be, in particular -- a TERRIBLE failing.
[color=blue]
> This is why for these people we might provide
> information about average case behavior (and
> then the difference between quicksort and
> bubblesort clearly shows).[/color]

Of COURSE you might! Who, pray, is stopping you from so doing, except
perhaps your own laziness and the fact that you prefer to pontificate
about the work that OTHERS should (you believe) do for you FOR FREE, IN
ADDITION to the other work they're already so doing, rather than
constructively participating in the collective effort yourself?

You argued for big-O information, and now you're arguing for more
information (that's much harder to provide in mathematically rigorous
form) regarding "averages" (over WHAT distribution of input
permutations? Why would you think that all permutations are equally
likely? In the real world, they're not, but they ARE incredibly hard to
characterize -- you'd better pick a very specific, tiny subfield of
application for sorting, to be able to supply AMPLE experimental support
for your theories... theory without any experimentation to support it
can be worse than worthless, it can be truly DIS-informing!). Very
well, if you're so convinced this information will be precious (worth
more than, say, the optimizations and new components which people might
alternatively produce, investing as they prefer their own time and
efforts), LEAD BY EXAMPLE. Pick ONE relatively simple issue of
performance, and explore it to the level of breadth and depth you
believe "analytical " (as opposed to *experimental*) performance
characterizatio n should go.

If you're willing to DO SOME WORK rather than SPEND YOUR TIME WHINING,
you will either produce some beautiful results whose practical
importance will stun others into following your lead, or find out that,
in the real world, there are more things in heaven and earth etc --
e.g., that behavior of virtual memory implementations SWAMPS any subtle
theoretical effects you thought would matter, for containers big enough
to matter, and well before getting anywhere close to the "asymptote" of
big-O and perhaps even big-Theta.

One way or another, something useful will be achieved, which surely
cannot be said about the present thread.

[color=blue]
> For others, such worst-case behavior may not
> be acceptable. For those other applications,
> a good worst-case may be what is required.
> This is why this second category of programmers
> needs to know about the worst-case. - But I am
> certainly belaboring the obvious...[/color]

You are (perhaps without realizing it) pointing out that the big-O
characterizatio n which you originally demanded is basicaly useless to
everybody (considering that a system has several subcomponents, and the
conditions under which each reaches worst-case are NOT necessarily
uncorrelated but might be positively or negatively correlated!). Except
perhaps theoreticians needing to publish theoretical papers, of
course;-).

[color=blue]
> Of course, the programs that have been designed
> on the basis of such information can (and ought
> to be) tested. Then some surprises (*not* predicted
> by theory) might happen: but if they do not happen
> too often, theory has done a good job - and so has
> the programmer...[/color]

That would follow only if the total amount of work (properly accounting
for the huge amounts needed to collect "theoretica lly" sound
characterizatio ns) was somehow reduced compared to alternative
approaches, based more on sound engineering practice and less on
reminescences of mathematics.

I believe that, out of all the iron suspension bridges designed and
built in the 19th century, ONE is standing -- the Brooklin Bridge.
Others were designed with "sounder theory" and (althought NOT real
"worst case analysis" -- none considered direct asteroid impacts, nor
did any designer "extrapolat e to infinity"!!!-) tried to cover
"reasonable " worst cases as the best theory available to them afforded.
And they all went down in the following decades.

The designer of the Brooklin Bridge followed sound engineering practice:
he designed based on TYPICAL (NOT worst-case) behavior, supported by
small-scale prototypes, THEN, knowing perfectly well that he couldn't be
sure he knew exactly WHAT worst-case he needed to ward about... he
doubled the thickness of all steel ropes and load-bearing beams. So,
HIS bridge is still standing (as is, say, Renzo Piano's airport terminal
building in Japan, where ALL Japanese buildings all around crumbled to
dust in a terrible earthquake... Piano may be an architect rather than
an engineer, but my respect for his craft knows no bounds).

I gather you want nuclear reactors, and programs, designed by the praxis
of all those OTHER suspension bridge designers of the 19th century; I
want them designed by the praxis by which the Brooklin Bridge was
designed. But in this case, you have an excellent chance to prove me
wrong: just put some of your work where your mouth is! And I'll be
quite happy to help, because, even if (as I surmise) the attempt at
theoretical characterizatio n proves pragmatically unsuccessful (in terms
of actual usefulness, and specifically of "bang for the buck"), even
then, if serious work has been put towards it, an empirically important
result is obtained.

I suspect you'll just find half-assed excuses to shirk the work which
your suggestions imply, but for once I'd be happy to be proved wrong...


Alex

[Paul Rubin]

Re: Comparing lists

aleaxit@yahoo.c om (Alex Martelli) writes:[color=blue]
> implementation of the components one's considering! Rough ideas of
> *EXPECTED* run-times (big-Theta) for various subcomponents one is
> sketching are *MUCH* more interesting and important than "asymptotic
> worst-case for amounts of input tending to infinity" (big-O) -- for[/color]

I thought big-Theta meant the intersection of big-O (upper bound on
the worst case) and big-Omega (lower bound on the worst case).
[color=blue]
> example, where I sketch-in (mentally, on paper, or on whiteboard) a
> "hash table" subcomponent, I consider the *expected* (Theta) performance
> (constant-time lookups), definitely NOT the big-O "linear time" lookups
> which just MIGHT occur (if, say, all inputs just happened to hash to the
> same value)... otherwise, I'd never use hash tables, right?-)[/color]

You really have to be careful about choices like that. See:

http://www.cs.rice.edu/~scrosby/hash/

which I also cited last night.

Exercise: suspend disbelief for a moment and imagine that 1) Google
search works by spidering the web and building a giant hash table of
words that it finds in web pages, to use for servicing future queries;
2) The hash function is similiar to the one used in Python dicts and
is either public knowledge or else leaks out of the company somehow;
and 3) (biggest disbelief suspension of them all) I work for
Microsoft. Question: how could I use knowledge of the hash function
to give Google a hard time?

At least one well known implementer apparently does intend to quit
using hash tables due to considerations like this:

http://cr.yp.to/critbit.html

[Christian Stapfer]

Re: Comparing lists

"Alex Martelli" <aleaxit@yahoo. com> wrote in message
news:1h4lfof.1j irgzd1rpwucsN%a leaxit@yahoo.co m...[color=blue]
> Christian Stapfer <nil@dev.nul> wrote:
>[color=green]
>> "Alex Martelli" <aleaxit@yahoo. com> wrote in message
>> news:1h4knvy.41 r7fw1k4bge7N%al eaxit@yahoo.com ...[color=darkred]
>> > Christian Stapfer <nil@dev.nul> wrote:
>> >
>> >> This is why we would like to have a way of (roughly)
>> >> estimating the reasonableness of the outlines of a
>> >> program's design in "armchair fashion" - i.e. without
>> >> having to write any code and/or test harness.
>> >
>> > And we would also like to consume vast amounts of chocolate, while
>> > similarly reclining in comfortable armchairs,[/color]
>>
>> Maybe some of my inclination towards design
>> based on suitable *theories* (instead of
>> self-conditioning through testing) goes back
>> to the fact that I tend to think about the
>> design of my programs when no computer happens
>> to be near at hand to do some such experimenting,
>> or self-conditioning...[/color]
>
> Oh, I am as prone as anybody I know to do SW architecture and design in
> bed when the lights are off and I'm sliding into sleep -- just about the
> only case in which no computer is handy, or, rather, in which it's
> generally unwise to turn the computer on (since it would interfere with
> the sleep thing;-). Back before laptops were really affordable and
> usable, I used to have a long bus commute, and did a lot of design with
> pen and paper; and whiteboards are a popular group-design tool at
> Google, no matter how many laptops or desktops happen to be around --
> whiteboards are simply more suitable for "socializat ion" around a draft
> design's sketch, than any computer-based tool I've ever seen.
>
> But that's *design*, and most often in pretty early stages, too -- quite
> a ways from *coding*. At that stage, one doesn't even generally commit
> to a specific programming language or other for the eventual
> implementation of the components one's considering! Rough ideas of
> *EXPECTED* run-times (big-Theta) for various subcomponents one is
> sketching are *MUCH* more interesting and important than "asymptotic
> worst-case for amounts of input tending to infinity" (big-O) -- for
> example, where I sketch-in (mentally, on paper, or on whiteboard) a
> "hash table" subcomponent, I consider the *expected* (Theta) performance
> (constant-time lookups), definitely NOT the big-O "linear time" lookups
> which just MIGHT occur (if, say, all inputs just happened to hash to the
> same value)... otherwise, I'd never use hash tables, right?-)[/color]

Well, Big-Oh, Big-Theta: these both are asymptotic
complexity measures, arent' they. So that's ok
with me.
[color=blue][color=green][color=darkred]
>> > without getting all fat and flabby.[/color]
>>
>> Well, thinking can be hard work. There is no need
>> to suggest an image of laziness. Thought experiments
>> are also quite often successful. Hardware engineers
>> can design very often entire gadgets without doing
>> a great deal of testing. They usually need to resort
>> to testing only if they know (or feel?) not to have
>> a sufficiently clear *theoretical* grasp of the
>> behavior of some part of their design.[/color]
>
> Having been a hardware designer (of integrated circuits, for Texas
> Instruments, and later briefly for IBM), before switching to software, I
> can resolutely deny this assertion: only an utter madman would approve a
> large production run of an IC who has not been EXTENSIVELY tested, in
> simulations and quite possibly in breadboards and later in limited
> pre-production runs.[/color]

Whoa, yet another straw-man attack!
First, remember, I do *not* advocate doing without
testing *altogether*: so here you are just attacking
a straw-man of your own making: that's *not* me.
What I wanted to say here is just that, in my
experience, as a close observer of "average
hardware designers", I believe that their testing
*usually* doesn't turn up major gotchas, and this
can only be because the theory they have about
their hardware will operate, is sufficiently
powerful. - "Usually": which means that exceptions
are possible, of course.
[color=blue]
> And any larger "gadget" USING ICs would be
> similarly crazy to skimp on prototyping, simulation, and other testing
> -- because, as every HW engineer KNOWS (SW ones often have to learn the
> hard way), the distance between theory and practice, in practice, is
> much larger than the distance between practice and theory should be in
> theory;-).
>[color=green][color=darkred]
>> > Unfortunately, what we would like and what reality affords
>> > are often pretty uncorrelated. No matter how much theoreticians may
>> > love big-O because it's (relatively) easy to compute, it still has two
>> > failings which are often sufficient to rule out its sufficiency for any
>> > "estimate [of] the reasonableness" of anything: [a] as we operate on
>> > finite machines with finite wordsize, we may never be able reach
>> > anywhere even remotely close to the "asymptotic " region where big-O has
>> > some relationship to reality; [b] in many important cases, the
>> > theoretical worst-case is almost impossible to characterize and hardly
>> > ever reached in real life, so big-O is of no earthly use (and much
>> > harder to compute measures such as big-Theta should be used for just
>> > about any practical purpose).[/color]
>>
>> But the fact remains that programmers, somewhat
>> experienced with the interface a module offers,
>> have a *rough*idea* of that computational complexity
>> attaches to what operations of that interface.
>> And having such a *rough*idea* helps them to
>> design reasonably performing programs much more
>> quickly.[/color]
>
> A rough idea helps, particularly a rough idea of EXPECTED performance.
>[color=green]
>> Big-Oh and other asymptotic complexity measures
>> really do have *this* advantage over having
>> acquired, by way of conditioning experiences,
>> some such *rough*idea* of computational complexity:[/color]
>
> No: big-O is NOT AT ALL a measure, rough or otherwise, of EXPECTED
> performance.[/color]

Another straw-man attack. Do you really read
what others write? What I have written?
Big-Oh is not the real bone of contention
at all, nor is worst-case characterizatio ns,
but the "practical usefulness" of any asymptotic
complexity measures whatsoever.
[color=blue]
> It's *WORST-CASE*, by definition; and includes no
> indications whatsoever of how close to the asymptote one can actually
> get on a given finite-size machine. By both issues, it can be totally
> misleading -- and, "it's not what you don't know, that hurts... it's
> what you know WHICH IS NOT SO". By its MISLEADING characteristics ,
> big-O can be SERIOUSLY DAMAGING to the abilty of "designing on the back
> of an envelope" (or in your head, or at a whiteboard).
>[color=green]
>> they capture at least some of that "rough idea"
>> in a somewhat more easily communicable and much
>> more precise fashion.[/color]
>
> Entirely precise, and therefore, in such cases as quicksort and hash
> tables (hardly "obscure corner cases" -- CENTRAL PILLARS of many
> designs!!!) all that more misleading.[/color]

So *what* do we substitute for what little "precision"
asymptotic complexity measures can give us? - Just
mindless testing and having us conditioned to accept
marketing-style characterizatio n of modules as "blazingly
fast", or "blindingly fast", or "not that fast"?
[color=blue][color=green]
>> Maybe you and Steven prefer to be conditioned,
>> Pavlov style, by the wonderful experiences that
>> you get while testing? - This is perhaps really
>> one of my *worst* psychological handicaps, I must
>> admit: that I don't *like* to get conditioned
>> like that, no matter how good it feels, no matter
>> how effective it might be for "practical" work that
>> one has to do.[/color]
>
> I like to be able to reason FIRSTLY on the basis of EXPECTED, NORMAL
> behavior,[/color]

That's ok with me, and fits my position
sufficiently well that there really is
no room for much argument.
[color=blue]
> corrected in the first order by reasonable prudence and
> caution, in the second order by accurate experimentation , and only in
> the third order by considerations of worst-case scenarios -- the latter
> normally tempered by estimates of their likelihood... which also
> requires a rough understanding of CORRELATION between the causes of such
> scenarios, which may be present, both directly or indirectly (assuming
> that different components interacting in a system "may just happen" to
> hit worst-case scenarios for each of them at once may be demonstrably
> wrong in either direction -- and NO big-O analysis will ever help with
> this crucial kind of task!).[/color]

Why on earth are you always jumping on worst-case
analysis and Big-Oh (but think Big-Theta and average-case
just wonderful)? - Steven argued against the "practical
usefulness" of any asymptotic complexity measures whatever.
[color=blue][color=green]
>> I want to be able to really think *about* what
>> I am doing. And in order to be able to think about
>> it one usually needs some information about the
>> implementation, performance wise, of the language
>> features and the system modules that one might
>> want to use. If you happen to know of any *better*
>> way of offering the requisite information than
>> asymptotic complexity measures then, of course,
>> I am very grateful to hear more about it.[/color]
>
> If you can't think about a design without knowing such details about one
> specific implementation of one specific programming language in which
> that design might get implemented, I think this strongly suggests you're
> giving insufficient attention to the one crucial skill in a designer's
> mental armory: *ABSTRACTION*.[/color]

Another straw-man attack.
What, if anything, are asymptotic complexity measures
doing if not abstract-away a great deal of details?
[color=blue]
> There are many ways to cultivate one's
> abstraction abilities. One of my favorite pastimes is collecting
> different renditions of Bach's "Art of the Fugue", for example: Bach
> carefully abstracted away the information about which instrument(s) were
> supposed to be playing which voice(s), as well as many other details --
> because of this, the Art of the Fugue has the highest abstraction level
> among all well-known musical compositions, and each rendition may take a
> different concrete reading of it. Learn to listen to them and be able
> to tell what they have in common, and where they differ: it's a great
> lesson in the understanding of abstraction.[/color]

Ok, we have something in common here: apparently we
both like Bach's polyphonic music.
However, no matter how much I might like Bach, my
preferred way of "learning abstraction abilities"
was studying mathematics.
[color=blue]
> But it's probably only
> appropriate if you like music, and Baroque in particular; other arts and
> discipline may no doubt afford similarly good learning experiences, if
> you know where to look for them.
>
> Once you're confident about your abilities of abstraction, I suggest you
> continue by the exercise of *characterizati on* (of A FEW
> implementations , ideally) which Jon Bentley (the programmer, not the
> jazz player) suggests pretty close to the start of his masterpiece
> "Writing Efficient Programs" (that great book may be hard to come by
> these days, but the "Programmin g Pearls" books are also excellent and
> communicate mostly the same messages, quite effectively). Get a sense
> for the *EXPECTED* (NOT "asymptotic ", for your inputs will NOT tend to
> infinity; NOT "worst-case only", don't be THAT pessimistic) behavior of
> some primitive operations - the couple of pages I devote to the subject
> in the Nutshell chapter on optimization, profiling and testing may
> suffice. Then refine your instinct by taking ONE complicated case, such
> as the natural mergesort variant known as the timsort, and delving as
> deep into its analysis as you dare -- characterize it as best you can
> manage WITHOUT testing, simply by reasoning on its code (Tim's essay,
> part of the Python source distribution, will be a helpful addition to a
> thorought grounding in Knuth's chapter on sorting, for this purpose)...
> then see what a difference it makes, to BE able to experiment![/color]

Your referring to Knuth's work in the context of
this discussion (and referring to him in order
to lecture me) seems a rather strange way
of operating.
[color=blue]
> You'll personally traverse, through such exercises, a curve not too
> dissimilar from what the whole of Western thought went through in the
> discovery and refinement of the experimental method[/color]

Western thought, for me, starts with Greek mathematics
and philosophy, not with Galileos experimentalism . This
is not to say that carefully executed experiments are
not important, far from it.
[color=blue]
> (to some extent it
> can be considered in full bloom in the thoughts and works of Galilei):
> not the blind flailing around of pure trial and error (which HAD,
> however, proved extremely fruitful in eliciting just about all technical
> progress up to that age, and later), much less the ungrounded
> elucubration of pure theoreticism (which HAD, mind you, given great
> results once in a while, e.g. in Euclid, Nagarjuna, Archimedes...) --
> but the powerful, fruitful merging of both strands into the incredibly
> productive golden braid which has pulled progress up during the last few
> centuries.
>
>[color=green][color=darkred]
>> > Consider, for example, point [b]. Quicksort's big-O is N squared,
>> > suggesting that quicksort's no better than bubblesort or the like. But
>> > such a characterizatio n is absurd. A very naive Quicksort, picking its
>> > pivot very systematically (e.g., always the first item), may hit its
>> > worst case just as systematically and in cases of practical importance
>> > (e.g., already-sorted data); but it takes just a little extra care (in
>> > the pivot picking and a few side issues) to make the worst-case
>> > occurrences into ones that will not occur in practice except when the
>> > input data has been deliberately designed to damage by a clever and
>> > determined adversary.
>> >
>> > Designing based on worst-case occurrences hardly ever makes
>> > sense in any field of engineering,[/color]
>>
>> What's wrong with wanting to have a rough idea
>> of what might happen in the worst case? I believe
>> many engineers are actually expected to think
>> about at least some "worst-case" scenarios.[/color]
>
> Not extrapolating to infinity.
>[color=green]
>> Think of nuclear reactors, airplanes, or
>> telephone exchanges (and dont' think of Google
>> for a change). Don't you expect engineers
>> and scientists designing, for example, a nuclear
>> reactor, to think hard about what the worst-case
>> scenario might be? And how likely it might happen?[/color]
>
> A square hit by an asteroid of mass tending to infinity? No, I don't
> expect nuclear reactors (nor anything else of human conception) to be
> designed in consideration of what such an asteroid hit would do. And
> yet, that's *EXACTLY* what would be indicated by your theory of big-O as
> a guide to design: consider the absolute worst that could conceivably
> happen, with *NO* indications WHATSOEVER of how unlikely it might be
> (because for simplicity of computation you take limits for misfortune
> tending to infinity!!!), and design for THAT.
>
> If our collective ancestors had taken this attitude, we'd still all be
> huddling in deep caves (possibly a better protection against "dinosaurs'
> killer" levels of asteroid hits!), shivering in the cold (fire is FAR
> too dangerous to survive a worst-case analysis, particularly with
> damaging elements all tending to infinity, as your love affair with
> big-O based designs would certainly indicate!!!). Animal skins? Forget
> it!!! Do a perfectly pessimistic worst-case analysis with suitable
> extrapolations to infinity and such skins would no doubt carry germs
> enough to exterminate the budding human race (not that extinction might
> not be preferable to the utterly miserable "lives" the few humans might
> lead if "big-O" had guided their design concerns, mind you!-).
>
>[color=green]
>> (And *no* testing whatsoever in that direction,
>> please!) Not thinking is, admittedly, a lot easier.[/color]
>
> I would consider ANYBODY who built a nuclear reactor without AMPLE
> testing dangerous enough for all of mankind to shoot on sight.[/color]

I just argued that the actual worst-case scenario
cannot - and should not - be tested (in the case
of nuclear reactors). And I still hold to *that*
assertion ;-)
[color=blue]
> I would
> expect HUGE amounts of simulation-based testing,[/color]

Hullo! That's interesting: simulation-based testing.
But that's based on theory. Real experimentalism
substitutes experiment for theory, and therefore
action for thought.
[color=blue]
> followed and
> interspersed by prototypes (smaller and simplified)[/color]

Again, here theory is needed: because you have
to use theory to deduce what that scale change
and simplification implies for the real case.
[color=blue]
> to validate that the
> simulations' tests are indeed perfectly respondent to actual reality.
>
> I haven't seen anybody on this thread advocating "not thinking"; if
> you're somehow implying that I'm trying to discourage people from
> thinking IN USEFUL AND PRODUCTIVE WAYS, I challenge you to point to
> anything I wrote here that could be construed that way.[/color]

The point was that executing (hastily slapped together)
tests - and devoutly believing in the output one gets -
is the way to go. This is foregoing some thinking before
acting, is it not?
[color=blue][color=green]
>> <snip/>
>>[color=darkred]
>> > Why bother doing
>> > (e.g.) random pivot selection in quicksort, when its big-O (i.e.,
>> > worst-case) behavior will remain N-squared, just like naive quicksort,
>> > or, for that matter, bubblesort?[/color]
>>
>> Because worst-case is not the only measure of
>> computational complexity that one might be
>> interested in. For some applications one may
>> be able to accept relatively bad worst-case
>> behavior, if it doesn't happen too often.[/color]
>
> But big-O, which is what you advocate,[/color]

No, Big-Oh is just one of the several asymptotic
complexity measures under discussion. By pounding
on big-oh and mistaking it for a synonym for
"worst-case" is just attacking a straw-man (not me).
[color=blue]
> gives *NO* indication of how
> likely or unlikely it might be, in particular -- a TERRIBLE failing.[/color]

Well, one can augment it with information about
the likelihood of its occurrence. Just because
big-oh (or average case, best case or worst
case) doesn't give you *everything* you would
like to known, doesn't mean it's worth nothing.
[color=blue][color=green]
>> This is why for these people we might provide
>> information about average case behavior (and
>> then the difference between quicksort and
>> bubblesort clearly shows).[/color]
>
> Of COURSE you might! Who, pray, is stopping you from so doing, except
> perhaps your own laziness and the fact that you prefer to pontificate
> about the work that OTHERS should (you believe) do for you FOR FREE, IN
> ADDITION to the other work they're already so doing, rather than
> constructively participating in the collective effort yourself?[/color]

I am not pontificating at all (but,
maybe, it is you pontificating here).
I was just suggesting that in order
to have a sufficiently clear idea about
what computational complexity attaches
to what feature of this or that library
module, I would have to read the source
and figure out how it's being done.
But that's not really a very effective
way of operating - not just for me
but for all the many who find themselves
in a similar situation. Note too, that
whoever implements a libary module not
only knows his implementation very well,
but has, by definition, already invested
some amount of thought into the question
of computational complexity of what
his module offers. So why not just write
it down, for a change?
[color=blue]
> You argued for big-O information, and now you're arguing for more
> information (that's much harder to provide in mathematically rigorous
> form) regarding "averages" (over WHAT distribution of input
> permutations? Why would you think that all permutations are equally
> likely? In the real world, they're not, but they ARE incredibly hard to
> characterize -- you'd better pick a very specific, tiny subfield of
> application for sorting, to be able to supply AMPLE experimental support
> for your theories... theory without any experimentation to support it
> can be worse than worthless, it can be truly DIS-informing!). Very
> well, if you're so convinced this information will be precious (worth
> more than, say, the optimizations and new components which people might
> alternatively produce, investing as they prefer their own time and
> efforts), LEAD BY EXAMPLE. Pick ONE relatively simple issue of
> performance, and explore it to the level of breadth and depth you
> believe "analytical " (as opposed to *experimental*) performance
> characterizatio n should go.
>
> If you're willing to DO SOME WORK rather than SPEND YOUR TIME WHINING,[/color]

Ha, ha, another figment of your imagination.
Now I am "whining". Not at all. The very verbosity
of your reaction to my not that long post seems to
indicate that what I had written really did hurt
you - and certainly *not* because it was nonsensical.
Nonsense never hurts anybody - except the one who
is uttering it.
[color=blue]
> you will either produce some beautiful results whose practical
> importance will stun others into following your lead, or find out that,
> in the real world, there are more things in heaven and earth etc --
> e.g., that behavior of virtual memory implementations SWAMPS any subtle
> theoretical effects you thought would matter, for containers big enough
> to matter, and well before getting anywhere close to the "asymptote" of
> big-O and perhaps even big-Theta.
>
> One way or another, something useful will be achieved, which surely
> cannot be said about the present thread.[/color]

Let's limit this to the present post...
[color=blue][color=green]
>> For others, such worst-case behavior may not
>> be acceptable. For those other applications,
>> a good worst-case may be what is required.
>> This is why this second category of programmers
>> needs to know about the worst-case. - But I am
>> certainly belaboring the obvious...[/color]
>
> You are (perhaps without realizing it) pointing out that the big-O
> characterizatio n which you originally demanded is basicaly useless to
> everybody (considering that a system has several subcomponents, and the
> conditions under which each reaches worst-case are NOT necessarily
> uncorrelated but might be positively or negatively correlated!). Except
> perhaps theoreticians needing to publish theoretical papers, of
> course;-).[/color]

... and Computer Science *undergrads* required to
learn about it? For what terrible fools are
you mistaking their profs?
[color=blue][color=green]
>> Of course, the programs that have been designed
>> on the basis of such information can (and ought
>> to be) tested. Then some surprises (*not* predicted
>> by theory) might happen: but if they do not happen
>> too often, theory has done a good job - and so has
>> the programmer...[/color]
>
> That would follow only if the total amount of work (properly accounting
> for the huge amounts needed to collect "theoretica lly" sound
> characterizatio ns)[/color]

Certainly, if every programmer has to figure
out such theoretically sound characterizatio ns
from scratch (by reading and analyzing the
relevant library source code) then it's really
going to be a huge amount of work for a huge
number of people. And that was just my point...
[color=blue]
> was somehow reduced compared to alternative
> approaches, based more on sound engineering practice and less on
> reminescences of mathematics.
>
> I believe that, out of all the iron suspension bridges designed and
> built in the 19th century, ONE is standing -- the Brooklin Bridge.
> Others were designed with "sounder theory" and (althought NOT real
> "worst case analysis" -- none considered direct asteroid impacts, nor
> did any designer "extrapolat e to infinity"!!!-) tried to cover
> "reasonable " worst cases as the best theory available to them afforded.
> And they all went down in the following decades.
>
> The designer of the Brooklin Bridge followed sound engineering practice:
> he designed based on TYPICAL (NOT worst-case) behavior, supported by
> small-scale prototypes, THEN, knowing perfectly well that he couldn't be
> sure he knew exactly WHAT worst-case he needed to ward about... he
> doubled the thickness of all steel ropes and load-bearing beams. So,
> HIS bridge is still standing (as is, say, Renzo Piano's airport terminal
> building in Japan, where ALL Japanese buildings all around crumbled to
> dust in a terrible earthquake... Piano may be an architect rather than
> an engineer, but my respect for his craft knows no bounds).
>
> I gather you want nuclear reactors, and programs, designed by the praxis
> of all those OTHER suspension bridge designers of the 19th century; I
> want them designed by the praxis by which the Brooklin Bridge was
> designed. But in this case, you have an excellent chance to prove me
> wrong: just put some of your work where your mouth is! And I'll be
> quite happy to help, because, even if (as I surmise) the attempt at
> theoretical characterizatio n proves pragmatically unsuccessful (in terms
> of actual usefulness, and specifically of "bang for the buck"), even
> then, if serious work has been put towards it, an empirically important
> result is obtained.
>
> I suspect you'll just find half-assed excuses to shirk the work which
> your suggestions imply, but for once I'd be happy to be proved wrong...
>[/color]

Thank you for your answer. Thank you for the time
you invested to write this down. However, being
not only something of an "armchair programmer"
but also an "armchair psychologist (if not
psychoanalyst)" I cannot help smiling at this
point...

Regards,
Christian