Comparing lists

[Christian Stapfer]

Re: Comparing lists

"Steven D'Aprano" <steve@REMOVETH IScyber.com.au> wrote in message
news:pan.2005.1 0.15.12.58.03.2 07379@REMOVETHI Scyber.com.au.. .[color=blue]
> On Sat, 15 Oct 2005 06:31:53 +0200, Christian Stapfer wrote:
>[color=green]
>> "jon" <jon_usenet@cap isco.com> wrote in message
>> news:1129216693 .445956.155490@ g47g2000cwa.goo glegroups.com.. .[color=darkred]
>>>
>>> To take the heat out of the discussion:
>>>
>>> sets are blazingly fast.[/color]
>>
>> I'd prefer a (however) rough characterizatio n
>> of computational complexity in terms of Big-Oh
>> (or Big-whatever) *anytime* to marketing-type
>> characterizatio ns like this one...[/color]
>
> Oh how naive.[/color]

Why is it that even computer science undergrads
are required to learn the basics of Big-Oh and
all that? Are computer scientists really morons,
as Xah Lee suggests? I can't believe it, but
maybe you have a point...
[color=blue]
> The marketing department says: "It's O(N), so it is blindingly fast."[/color]

I might as well interpret "blindingly fast"
as meaning O(1). - Why not?
Surely marketing might also have reasoned like
this: "It's O(1), so its blindingly fast".
But I *want*, nay, I *must* know whether it is
O(N) or O(1). So forget about marketingspeak,
it's a deadly poison for developers. It might
be ok to induce grandiose feelings in childish
users - but developers are grown ups: they must
face reality...
[color=blue]
> Translation: the amount of computation it does is linearly proportional
> to N. The constant of proportionality is 1e10.
>
> The marketing department says: "Our competitor's product is O(N**2), so it
> runs like a three-legged dog."
>
> Translation: the amount of computation it does is linearly proportional to
> N squared. The constant of proportionality is 1e-100.
>
> You do the maths.
>
> Big O notation is practically useless for judging how fast a single
> algorithm will be, or how one algorithm compares to another.[/color]

That's why Knuth liked it so much?
That's why Aho, Hopcroft and Ullman liked it so much?
That's why Gonnet and Baeza-Yates liked it so much?
[color=blue]
> It is only useful for telling you how a single algorithm
> will scale as the input increases.[/color]

And that's really very useful information indeed.
Since, given such information for the basic data types
and operations, as implemented by the language and
its standard libraries, I stand a real chance of
being able to determine the computational complexity
of the *particular*com bination* of data types and
algorithms of my own small utility or of a
critical piece of my wonderful and large application,
on which the future of my company depends, with some
confidence and accuracy.
[color=blue]
> It is very common for sensible programmers to fall back on a "less
> efficient" O(N**2) or even O(2**N) algorithm for small amounts of data, if
> that algorithm runs faster than the "more efficient" O(N) or O(log N)
> algorithm. In fact, that's exactly what the sort() method does in Python:
> for small enough lists, say, under 100 elements, it is quicker to run an
> O(N**2) algorithm (shell sort I believe) than it is to perform the
> complex set up for the merge-sort variant used for larger lists.
>
> As for sets, they are based on dicts, which are effectively hash tables.
> Hash tables are O(1), unless there are collisions,[/color]

Depending on the "load factor" of the hash tables.
So we would want to ask, if we have very large
lists indeed, how much space needs to be invested
to keep the load factor so low that we can say
that the membership test is O(1). Do A-B and A&B
have to walk the entire hash table (which must be
larger than the sets, because of a load factor
< 1)? Also: the conversion of lists to sets needs
the insertion of N elements into those hash tables.
That alone already makes the overall algorithm
*at*least* O(N). So forget about O(log N).
[color=blue]
> in which case the more
> common algorithms degenerate to O(N).[/color]

So here, indeed, we have the kind of reasoning that
one ought to be able to deliver, based on what's in
the Python documentation. Luckily, you have that
kind the knowledge of both, how sets are implemented
and what Big-Oh attaches to the hash table operation
of "look up".
In order to *enable* SUCH reasoning for *everyone*,
starting from the module interface documentation only,
one clearly needs something along the lines that
I was suggesting...
[color=blue]
> So, a very rough and ready estimate
> of the complexity of the algorithm using sets would be somewhere between
> O(1) and O(N) depending on the details of Python's algorithms.
>
> So, let's do an experiment, shall we?
>
> from sets import Set
> import time
>
> def compare_and_sep arate_with_sets (A, B):
> AB = Set(A+B)
> A = Set(A)
> B = Set(B)
> only_A = list(A-B)
> only_B = list(B-A)
> both_AB = list(AB - Set(only_A+only _B))
> return (only_A, only_B, both_AB)
>
> def timeit(f, args, n):
> """Time function f when called with *args. For timing purposes,
> does n calls of f. Returns the average time used per call in seconds.
> """
> loopit = range(n)
> t = time.time()
> for i in loopit:
> results = f(*args)
> t = time.time() - t
> return t/n
>
> def single_test(N):
> print ("N = %-8d" % N),
> A = range(N)
> B = range(N/2, 3*N/2)
> return timeit(compare_ and_separate_wi th_sets, (A, B), 20)
>
> def test_Order():
> # test how compare_and_sep arate_with_sets scales with size
> for i in range(7):
> print single_test(10* *i)
>
>
> Now run the test code:
>
> py> test_Order()
> N = 1 0.0002191066741 94
> N = 10 0.0001351833343 51[/color]

Curious: N=10 takes less time than N=1?
[color=blue]
> N = 100 0.0004811286926 27[/color]

Why do we have such a comparatively large jump
here, from N=100 to N=1000? Did hash tables
overflow during conversion or something like
that?
[color=blue]
> N = 1000 0.0173740386963
> N = 10000 0.103679180145
> N = 100000 0.655336141586
> N = 1000000 8.12827801704[/color]

Doesn't look quite O(n). Not yet...
[color=blue]
> In my humble opinion, that's not bad behaviour.
> It looks O(log N) to me,[/color]

How could that be? *Every* element of A and B must touched,
if only to be copied: that can't make it O(log(N)).
Also, the conversion of lists to sets must be at least
O(N). And N isn't the right measure anyway. It would probably
have to be in terms of |A| and |B|. For example, if |A| is very
small, as compared to |B|, then A-B and A & B can be determined
rather quickly by only considering elements of A.
[color=blue]
> and quite fast too: about 8 seconds to compare and separate two lists of
> one million items each.
>
> The craziest thing is, the amount of time it took to write and test two
> different algorithms was probably 1% of the time it would take to hunt up
> theoretical discussions of what the big O behaviour of the algorithms
> would be.[/color]

You must distinguish questions of principle
and questions of muddling through like this
testing bit you've done. It would take me some
time to even be *sure* how to interpret the
result. I would never want to say "it looks
O(log N) to me", as you do, and leave it at
that. Rather, I might say, as you do, "it
looks O(log N) to me", *but* then try to figure
out, given my knowledge of the implementation
(performance wise, based on information that
is sadly missing in the Python documentation),
*why* that might be. Then, if my experiments says
"it looks like O(log N)" AND if my basic
knowledge of the implementation of set and
list primitives says "it should be O(log N)"
as well, I would venture, with some *confidence*,
to claim: "it actually IS O(log N)"....

You do not compare the convert-it-to-sets-approach
to the single list-walk either. Supposing the OP
had actually sorted lists to begin with, then a
single, simultaneous walk of the lists would be
about as fast as it can get. Very, very likely
*faster* than conversion to sets would be...

Regards,
Christian

[Steven D'Aprano]

Re: Comparing lists

On Sat, 15 Oct 2005 18:17:36 +0200, Christian Stapfer wrote:
[color=blue][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
>>> characterizatio ns like this one...[/color]
>>
>> 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.

Perhaps you should actually sit down and look at the assumptions,
simplifications , short-cuts and trade-offs that computer scientists make
when they estimate an algorithm's Big O behaviour. It might shock you out
of your faith that Big O is the be all and end all of algorithm planning.

For all but the simplest algorithm, it is impractical to actually count
all the operations -- and even if you did, the knowledge wouldn't help
you, because you don't know how long each operation takes to get executed.
That is platform specific.

So you simplify. You pretend that paging never happens. That memory
allocations take zero time. That set up and removal of data structures
take insignificant time. That if there is an N**2 term, it always swamps
an N term. You assume that code performance is independent of the CPUs.
You assume that some operations (e.g. comparisons) take no time, and
others (e.g. moving data) are expensive.

Those assumptions sometimes are wildly wrong. I've been seriously bitten
following text book algorithms written for C and Pascal: they assume that
comparisons are cheap and swapping elements are expensive. But in Python,
swapping elements is cheap and comparisons are expensive, because of all
the heavy object-oriented machinery used. Your classic text book algorithm
is not guaranteed to survive contact with the real world: you have to try
it and see.

Given all the assumptions, it is a wonder that Big O estimates are ever
useful, not that they sometimes are misleading.



[snip][color=blue][color=green]
>> The marketing department says: "It's O(N), so it is blindingly fast."[/color]
>
> I might as well interpret "blindingly fast" as meaning O(1). - Why not?
> Surely marketing might also have reasoned like
> this: "It's O(1), so its blindingly fast". But I *want*, nay, I *must*
> know whether it is O(N) or O(1).[/color]

You might _want_, but you don't _need_ to know which it is, not in every
case. In general, there are many circumstances where it makes no
sense to worry about Big O behaviour. What's your expected data look like?
If your data never gets above N=2, then who cares whether it is O(1)=1,
O(N)=2, O(N**2)=4 or O(2**N)=2? They are all about as fast.

Even bubble sort will sort a three element list fast enough -- and
probably faster than more complicated sorts. Why spend all the time
setting up the machinery for a merge sort for three elements?


[snip]
[color=blue][color=green]
>> Big O notation is practically useless for judging how fast a single
>> algorithm will be, or how one algorithm compares to another.[/color]
>
> That's why Knuth liked it so much?
> That's why Aho, Hopcroft and Ullman liked it so much? That's why Gonnet
> and Baeza-Yates liked it so much?[/color]

Two reasons: it is useful for telling you how a single algorithm will
scale as the input increases, just as I said.

And, unlike more accurate ways of calculating the speed of an algorithm
from first principles, it is actually possible to do Big O calculations.

No doubt the state of the art of algorithm measurements has advanced since
I was an undergraduate, but certain fundamental facts remain: in order to
calculate that Big O, you have to close your eyes to all the realities
of practical code execution, and only consider an idealised calculation.
Even when your calculation gives you constants of proportionality and
other coefficients, Big O notation demands you throw that information away.

But by doing so, you lose valuable information. An O(N**2) algorithm that
scales like 1e-6 * N**2 will be faster than an O(N) algorithm that scales
as 1e6 * N, until N reaches one million million. By tossing away those
coefficients, you wrongly expect the first algorithm to be slower than the
second, and choose the wrong algorithm.


[color=blue][color=green]
>> It is only useful for telling you how a single algorithm will scale as
>> the input increases.[/color]
>
> And that's really very useful information indeed.[/color]

Yes it is. Did I ever say it wasn't?

[color=blue]
> Since, given such
> information for the basic data types and operations, as implemented by
> the language and its standard libraries, I stand a real chance of being
> able to determine the computational complexity of the
> *particular*com bination* of data types and algorithms of my own small
> utility or of a critical piece of my wonderful and large application, on
> which the future of my company depends, with some confidence and
> accuracy.[/color]

Yes, zero is a real chance.


[snip]
[color=blue][color=green]
>> As for sets, they are based on dicts, which are effectively hash
>> tables. Hash tables are O(1), unless there are collisions,[/color]
>
> Depending on the "load factor" of the hash tables. So we would want to
> ask, if we have very large lists indeed, how much space needs to be
> invested to keep the load factor so low that we can say that the
> membership test is O(1).[/color]

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=blue]
> Do A-B and A&B have to walk the entire hash
> table (which must be larger than the sets, because of a load factor <
> 1)? Also: the conversion of lists to sets needs the insertion of N
> elements into those hash tables. That alone already makes the overall
> algorithm *at*least* O(N). So forget about O(log N).[/color]

Yes, inserting N items into a hash table takes at least N inserts. But if
those inserts are fast enough, you won't even notice the time it takes to
do it, compared to the rest of your algorithm. In many algorithms, you
don't even care about the time it takes to put items in your hash table,
because that isn't part of the problem you are trying to solve.

So in real, practical sense, it may be that your algorithm gets dominated
by the O(log N) term even though there is technically an O(N) term in
there. Are Python dicts like that? I have no idea. But I know how to find
out: choose a problem domain I care about ("dicts with less than one
million items") and do the experiment.

[color=blue][color=green]
>> in which case the more
>> common algorithms degenerate to O(N).[/color]
>
> So here, indeed, we have the kind of reasoning that one ought to be able
> to deliver, based on what's in the Python documentation. Luckily, you
> have that kind the knowledge of both, how sets are implemented and what
> Big-Oh attaches to the hash table operation of "look up".
> In order to *enable* SUCH reasoning for *everyone*,
> starting from the module interface documentation only, one clearly needs
> something along the lines that I was suggesting...[/color]

I don't object to having that Big O information available, except
insofar as it can be misleading, but I take issue with your position that
such information is necessary.


[snip]
[color=blue][color=green]
>> Now run the test code:
>>
>> py> test_Order()
>> N = 1 0.0002191066741 94
>> N = 10 0.0001351833343 51[/color]
>
> Curious: N=10 takes less time than N=1?[/color]

Yes, funny how real-world results aren't as clean and neat as they are in
theory. There are those awkward assumptions coming to bite you again. I've
done two additional tests, and get:

N = 1 0.0000850439071 66
N = 10 0.0001066565513 61

N = 1 0.0004979491233 83
N = 10 0.0001240491867 07

Remember, these results are averaged over twenty trials. So why it is
quicker to do work with sets of size 10 than sets of size 1? Big O
notation will never tell you, because it ignores the implementation
details that really make a difference.


[color=blue][color=green]
>> N = 100 0.0004811286926 27[/color]
>
> Why do we have such a comparatively large jump here, from N=100 to
> N=1000? Did hash tables overflow during conversion or something like
> that?[/color]

Who knows? Maybe Python was doing some garbage collection the first time I
run it. I've modified my code to print a scale factor, and here is another
run:

N = 1 0.0011350989341 7
N = 10 0.0001061439514 16 (x 0.093511)
N = 100 0.0026513457298 3 (x 24.978774)
N = 1000 0.0057701587677 (x 2.176313)
N = 10000 0.0551437973976 (x 9.556721)
N = 100000 0.668345856667 (x 12.120055)
N = 1000000 8.6285964489 (x 12.910376)

An increase from N=1 to 1000000 (that's a factor of one million) leads to
an increase in execution time of about 7600.

You will notice that the individual numbers vary significantly from trial
to trial, but the over-all pattern is surprisingly consistent.

[color=blue][color=green]
>> N = 1000 0.0173740386963
>> N = 10000 0.103679180145
>> N = 100000 0.655336141586
>> N = 1000000 8.12827801704[/color]
>
> Doesn't look quite O(n). Not yet...[/color]

No it doesn't.
[color=blue]
>[color=green]
>> In my humble opinion, that's not bad behaviour. It looks O(log N) to
>> me,[/color][/color]

That's a mistake -- it is nowhere near O(log N). My bad. Closer to
O(sqrt N), if anything.

[color=blue]
> How could that be? *Every* element of A and B must touched, if only to
> be copied: that can't make it O(log(N)).[/color]

And, no doubt, if you had *really enormous* lists, oh, I don't know, maybe
a trillion items, you would see that O(N) behaviour. But until then, the
overall performance is dominated by the smaller-order terms with larger
coefficients.

[color=blue]
> Also, the conversion of lists
> to sets must be at least O(N). And N isn't the right measure anyway. It
> would probably have to be in terms of |A| and |B|. For example, if |A|
> is very small, as compared to |B|, then A-B and A & B can be determined
> rather quickly by only considering elements of A.[/color]


Both lists have the same number of elements, so double N.


[snip]
[color=blue]
> You must distinguish questions of principle and questions of muddling
> through like this testing bit you've done.[/color]

Your "question of principle" gives you completely misleading answers.
Remember, you were the one who predicted that lists would have to be
faster than sets. Your prediction failed miserably.

[color=blue]
> It would take me some time to
> even be *sure* how to interpret the result.[/color]

What's to interpret? I know exactly how fast the function will run, on
average, on my hardware. I can even extrapolate to larger sizes of N,
although I would be very careful to not extrapolate too far. (I predict
less than 10 minutes to work on a pair of 10,000,000 element lists, and
less than two hours to work on 100,000,000 element lists.)
[color=blue]
> I would never want to say
> "it looks O(log N) to me", as you do, and leave it at that. Rather, I
> might say, as you do, "it looks O(log N) to me", *but* then try to
> figure out, given my knowledge of the implementation (performance wise,
> based on information that is sadly missing in the Python documentation),
> *why* that might be.[/color]

Fine. You have the source code, knock yourself out.
[color=blue]
> Then, if my experiments says "it looks like O(log
> N)" AND if my basic knowledge of the implementation of set and list
> primitives says "it should be O(log N)" as well, I would venture, with
> some *confidence*, to claim: "it actually IS O(log N)"....
>
> You do not compare the convert-it-to-sets-approach
> to the single list-walk either.[/color]

No I did not, because I didn't have a function to do it. You've got my
source code. Knock yourself out to use it to test any function you like.
[color=blue]
> Supposing the OP had actually sorted
> lists to begin with, then a single, simultaneous walk of the lists would
> be about as fast as it can get. Very, very likely *faster* than
> conversion to sets would be...[/color]

Please let us know how you go with that. It should be really interesting
to see how well your prediction copes with the real world.

(Hint: another of those awkward little implementation details... how much
work is being done in C code, and how much in pure Python? Just something
for you to think about. And remember, an O(N) algorithm in Python will be
faster than an O(N**2) algorithm in C... or is that slower?)



--
Steven.

[Christian Stapfer]

Re: Comparing lists

"Steven D'Aprano" <steve@REMOVETH IScyber.com.au> wrote in message
news:pan.2005.1 0.15.19.22.50.8 64680@REMOVETHI Scyber.com.au.. .[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
>>>> characterizatio ns 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.[/color]

Well, that's right. I couldn't agree more:
it doesn't tell you *everything* but it does
tell you *something*. And that *something*
is good to have.
[color=blue]
> 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]

Well, that's where you err: Testing doesn't
tell you everything *either*. You need *both*:
a reasonable theory *and* experimental data...
If theory and experimental data disagree,
we would want to take a closer look on both,
the theory (which may be mistaken or inadequate)
*and* the experiment (which may be inadequate or
just plain botched as well).
[color=blue]
> Perhaps you should actually sit down and look at the assumptions,
> simplifications , short-cuts and trade-offs that computer scientists make
> when they estimate an algorithm's Big O behaviour. It might shock you out
> of your faith that Big O is the be all and end all of algorithm planning.
>
> For all but the simplest algorithm, it is impractical to actually count
> all the operations -- and even if you did, the knowledge wouldn't help
> you, because you don't know how long each operation takes to get executed.
> That is platform specific.
>
> So you simplify. You pretend that paging never happens. That memory
> allocations take zero time. That set up and removal of data structures
> take insignificant time. That if there is an N**2 term, it always swamps
> an N term. You assume that code performance is independent of the CPUs.
> You assume that some operations (e.g. comparisons) take no time, and
> others (e.g. moving data) are expensive.
>
> Those assumptions sometimes are wildly wrong. I've been seriously bitten
> following text book algorithms written for C and Pascal: they assume that
> comparisons are cheap and swapping elements are expensive. But in Python,
> swapping elements is cheap and comparisons are expensive, because of all
> the heavy object-oriented machinery used. Your classic text book algorithm
> is not guaranteed to survive contact with the real world: you have to try
> it and see.[/color]

Still: the expensiveness of those operations (such
as swapping elements vs. comparisons) will only
affect the constant of proportionality , not the
asymptotic behavior of the algorithm. Sooner or
later the part of your program that has the
worst asymptotic behavior will determine speed
(or memory requirements) of your program.
[color=blue]
> Given all the assumptions, it is a wonder that Big O
> estimates are ever useful, not that they sometimes
> are misleading.
>
> [snip][color=green][color=darkred]
>>> The marketing department says: "It's O(N), so it is blindingly fast."[/color]
>>
>> I might as well interpret "blindingly fast" as meaning O(1). - Why not?
>> Surely marketing might also have reasoned like
>> this: "It's O(1), so its blindingly fast". But I *want*, nay, I *must*
>> know whether it is O(N) or O(1).[/color]
>
> You might _want_, but you don't _need_ to know which it is, not in every
> case. In general, there are many circumstances where it makes no
> sense to worry about Big O behaviour. What's your expected data look like?
> If your data never gets above N=2, then who cares whether it is O(1)=1,
> O(N)=2, O(N**2)=4 or O(2**N)=2? They are all about as fast.
>
> Even bubble sort will sort a three element list fast enough -- and
> probably faster than more complicated sorts. Why spend all the time
> setting up the machinery for a merge sort for three elements?[/color]

Since you have relapsed into a fit of mere polemics,
I assume to have made my point as regards marketing
type characterizatio ns of algorithms ("blazingly
fast") vs. measures, however rough, of asymptotic
complexity measures, like Big-Oh. - Which really
was the root of this sub-thread that went like this:

...>> To take the heat out of the discussion:
... >> sets are blazingly fast.

... > I'd prefer a (however) rough characterizatio n
... > of computational complexity in terms of Big-Oh
... > (or Big-whatever) *anytime* to marketing-type
... > characterizatio ns like this one...
[color=blue]
> [snip]
>[color=green][color=darkred]
>>> Big O notation is practically useless for judging how fast a single[/color][/color][/color]
^^^^^^^^^^^^^^^ ^^^^^^^[color=blue][color=green][color=darkred]
>>> algorithm will be, or how one algorithm compares to another.[/color]
>>
>> That's why Knuth liked it so much?
>> That's why Aho, Hopcroft and Ullman liked it so much? That's why Gonnet
>> and Baeza-Yates liked it so much?[/color]
>
> Two reasons: it is useful for telling you how a single algorithm will
> scale as the input increases, just as I said.[/color]

Curiously, just a few lines before writing this,
you have polemically denied any "practical" use
for Big-Oh notation.
[color=blue]
> And, unlike more accurate ways of calculating the speed of an algorithm
> from first principles, it is actually possible to do Big O calculations.[/color]

Right. It's a compromise: being somewhat precise
- without getting bogged down trying to solve major
combinatorial research problems...
[color=blue]
> No doubt the state of the art of algorithm measurements has advanced since
> I was an undergraduate, but certain fundamental facts remain: in order to
> calculate that Big O, you have to close your eyes to all the realities
> of practical code execution, and only consider an idealised calculation.[/color]

That's right. Nothing stops you from then opening
your eyes and testing some code, of course. *But*
always try to relate what you see there with what
theoretical grasp of the situation you have.
If experimental data and theory *disagree*: try to
fix the experiment and/or the theory.
[color=blue]
> Even when your calculation gives you constants of proportionality and
> other coefficients, Big O notation demands you throw that information
> away.
>
> But by doing so, you lose valuable information. An O(N**2) algorithm that
> scales like 1e-6 * N**2 will be faster than an O(N) algorithm that scales
> as 1e6 * N, until N reaches one million million. By tossing away those
> coefficients, you wrongly expect the first algorithm to be slower than the
> second, and choose the wrong algorithm.
>[color=green][color=darkred]
>>> It is only useful for telling you how a single algorithm will scale as
>>> the input increases.[/color]
>>
>> And that's really very useful information indeed.[/color]
>
> Yes it is. Did I ever say it wasn't?[/color]

Well yes, by the way you attacked Big-Oh notation
as "practicall y useless" (see above) I assumed you
did.
[color=blue][color=green]
>> Since, given such
>> information for the basic data types and operations, as implemented by
>> the language and its standard libraries, I stand a real chance of being
>> able to determine the computational complexity of the
>> *particular*com bination* of data types and algorithms of my own small
>> utility or of a critical piece of my wonderful and large application, on
>> which the future of my company depends, with some confidence and
>> accuracy.[/color]
>
> Yes, zero is a real chance.
>
>
> [snip]
>[color=green][color=darkred]
>>> As for sets, they are based on dicts, which are effectively hash
>>> tables. Hash tables are O(1), unless there are collisions,[/color]
>>
>> Depending on the "load factor" of the hash tables. So we would want to
>> ask, if we have very large lists indeed, how much space needs to be
>> invested to keep the load factor so low that we can say that the
>> membership test is O(1).[/color]
>
> 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=green]
>> Do A-B and A&B have to walk the entire hash
>> table (which must be larger than the sets, because of a load factor <
>> 1)? Also: the conversion of lists to sets needs the insertion of N
>> elements into those hash tables. That alone already makes the overall
>> algorithm *at*least* O(N). So forget about O(log N).[/color]
>
> Yes, inserting N items into a hash table takes at least N inserts. But if
> those inserts are fast enough, you won't even notice the time it takes to
> do it, compared to the rest of your algorithm. In many algorithms, you
> don't even care about the time it takes to put items in your hash table,
> because that isn't part of the problem you are trying to solve.
>
> So in real, practical sense, it may be that your algorithm gets dominated
> by the O(log N) term even though there is technically an O(N) term in
> there. Are Python dicts like that? I have no idea. But I know how to find
> out: choose a problem domain I care about ("dicts with less than one
> million items") and do the experiment.
>
>[color=green][color=darkred]
>>> in which case the more
>>> common algorithms degenerate to O(N).[/color]
>>
>> So here, indeed, we have the kind of reasoning that one ought to be able
>> to deliver, based on what's in the Python documentation. Luckily, you
>> have that kind the knowledge of both, how sets are implemented and what
>> Big-Oh attaches to the hash table operation of "look up".
>> In order to *enable* SUCH reasoning for *everyone*,
>> starting from the module interface documentation only, one clearly needs
>> something along the lines that I was suggesting...[/color]
>
> I don't object to having that Big O information available, except
> insofar as it can be misleading, but I take issue with your position that
> such information is necessary.[/color]

*Blindly* testing, that is, testing *without* being
able to *relate* the outcomes of those tests (even
the *design* of those tests) to some suitably
simplified but not at all completely nonsensical
theory (via Big-Oh notation, for example), is *not*
really good enough.
[color=blue][color=green][color=darkred]
>>> Now run the test code:
>>>
>>> py> test_Order()
>>> N = 1 0.0002191066741 94
>>> N = 10 0.0001351833343 51[/color]
>>
>> Curious: N=10 takes less time than N=1?[/color]
>
> Yes, funny how real-world results aren't as clean and neat as they are in
> theory. There are those awkward assumptions coming to bite you again. I've
> done two additional tests, and get:
>
> N = 1 0.0000850439071 66
> N = 10 0.0001066565513 61
>
> N = 1 0.0004979491233 83
> N = 10 0.0001240491867 07
>
> Remember, these results are averaged over twenty trials. So why it is
> quicker to do work with sets of size 10 than sets of size 1? Big O
> notation will never tell you, because it ignores the implementation
> details that really make a difference.
>
>
>[color=green][color=darkred]
>>> N = 100 0.0004811286926 27[/color]
>>
>> Why do we have such a comparatively large jump here, from N=100 to
>> N=1000? Did hash tables overflow during conversion or something like
>> that?[/color]
>
> Who knows? Maybe Python was doing some garbage collection the first time I
> run it. I've modified my code to print a scale factor, and here is another
> run:
>
> N = 1 0.0011350989341 7
> N = 10 0.0001061439514 16 (x 0.093511)
> N = 100 0.0026513457298 3 (x 24.978774)
> N = 1000 0.0057701587677 (x 2.176313)
> N = 10000 0.0551437973976 (x 9.556721)
> N = 100000 0.668345856667 (x 12.120055)
> N = 1000000 8.6285964489 (x 12.910376)
>
> An increase from N=1 to 1000000 (that's a factor of one million) leads to
> an increase in execution time of about 7600.
>
> You will notice that the individual numbers vary significantly from trial
> to trial, but the over-all pattern is surprisingly consistent.
>
>[color=green][color=darkred]
>>> N = 1000 0.0173740386963
>>> N = 10000 0.103679180145
>>> N = 100000 0.655336141586
>>> N = 1000000 8.12827801704[/color]
>>
>> Doesn't look quite O(n). Not yet...[/color]
>
> No it doesn't.
>[color=green]
>>[color=darkred]
>>> In my humble opinion, that's not bad behaviour. It looks O(log N) to
>>> me,[/color][/color]
>
> That's a mistake -- it is nowhere near O(log N). My bad. Closer to
> O(sqrt N), if anything.
>
>[color=green]
>> How could that be? *Every* element of A and B must touched, if only to
>> be copied: that can't make it O(log(N)).[/color]
>
> And, no doubt, if you had *really enormous* lists, oh, I don't know, maybe
> a trillion items, you would see that O(N) behaviour. But until then, the
> overall performance is dominated by the smaller-order terms with larger
> coefficients.
>
>[color=green]
>> Also, the conversion of lists
>> to sets must be at least O(N). And N isn't the right measure anyway. It
>> would probably have to be in terms of |A| and |B|. For example, if |A|
>> is very small, as compared to |B|, then A-B and A & B can be determined
>> rather quickly by only considering elements of A.[/color]
>
>
> Both lists have the same number of elements, so double N.
>
>
> [snip]
>[color=green]
>> You must distinguish questions of principle and questions of muddling
>> through like this testing bit you've done.[/color]
>
> Your "question of principle" gives you completely misleading answers.
> Remember, you were the one who predicted that lists would have to be
> faster than sets.[/color]

I didn't say they would *have* to be faster
- I was mainly asking for some *reasoned*
argument why (and in what sense) conversion
to sets would be an "efficient" solution
of the OPs problem.
[color=blue]
> Your prediction failed miserably.[/color]

Interestingly, you admit that you did not
really compare the two approaches that
were under discussion. So your experiment
does *not* (yet) prove what you claim it
proves.
[color=blue][color=green]
>> It would take me some time to
>> even be *sure* how to interpret the result.[/color]
>
> What's to interpret? I know exactly how fast the function will run, on
> average, on my hardware. I can even extrapolate to larger sizes of N,
> although I would be very careful to not extrapolate too far. (I predict
> less than 10 minutes to work on a pair of 10,000,000 element lists, and
> less than two hours to work on 100,000,000 element lists.)[/color]

For a starter: You have chosen a very particular type
of element of those lists / sets: integers. So the
complexity of comparisons for the OPs application
might get *seriously* underestimated.
[color=blue]
>[color=green]
>> I would never want to say
>> "it looks O(log N) to me", as you do, and leave it at that. Rather, I
>> might say, as you do, "it looks O(log N) to me", *but* then try to
>> figure out, given my knowledge of the implementation (performance wise,
>> based on information that is sadly missing in the Python documentation),
>> *why* that might be.[/color]
>
> Fine. You have the source code, knock yourself out.[/color]

That's just what I do *not* think to be a particularly
reasonable approach. Instead, I propose stating
some (to the implementer *easily* available)
information about asymptotic behavior of operations
that are exposed by the module interface upfront.
[color=blue][color=green]
>> Then, if my experiments says "it looks like O(log
>> N)" AND if my basic knowledge of the implementation of set and list
>> primitives says "it should be O(log N)" as well, I would venture, with
>> some *confidence*, to claim: "it actually IS O(log N)"....
>>
>> You do not compare the convert-it-to-sets-approach
>> to the single list-walk either.[/color]
>
> No I did not, because I didn't have a function to do it.[/color]

Here we see one of the problems of a purely
experimentalist approach to computational complexity:
you need an implementation (of the algorithm and the
test harness) *before* you can get your wonderfully
decisive experimental data.
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=blue]
> You've got my
> source code. Knock yourself out to use it to test any function you like.
>[color=green]
>> Supposing the OP had actually sorted
>> lists to begin with, then a single, simultaneous walk of the lists would
>> be about as fast as it can get. Very, very likely *faster* than
>> conversion to sets would be...[/color]
>
> Please let us know how you go with that. It should be really interesting
> to see how well your prediction copes with the real world.
>
> (Hint: another of those awkward little implementation details... how much
> work is being done in C code, and how much in pure Python? Just something
> for you to think about. And remember, an O(N) algorithm in Python will be
> faster than an O(N**2) algorithm in C... or is that slower?)[/color]

This discussion begins to sound like the recurring
arguments one hears between theoretical and
experimental 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,
Christian
--
»When asked how he would have reacted if Eddington's
*measurements* had come out differently, Einstein
replied: "Then I would have been sorry for him
- the *theory* is correct."«
- Paul B. Armstrong: 'Conflicting Readings'

[Ron Adam]

Re: Comparing lists

Christian Stapfer wrote:
[color=blue]
> This discussion begins to sound like the recurring
> arguments one hears between theoretical and
> experimental 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,
> Christian[/color]

An interesting parallel can be made concerning management of production
vs management 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.

Both are good and needed for different types of tasks. And I think most
programmers can switch styles to some degree if they need to.

Cheers,
Ron

[Christian Stapfer]

Re: Comparing lists

"Ron Adam" <rrr@ronadam.co m> wrote in message
news:cTp4f.1618 0$ae.11317@torn ado.tampabay.rr .com...[color=blue]
> Christian Stapfer wrote:
>[color=green]
>> This discussion begins to sound like the recurring
>> arguments one hears between theoretical and
>> experimental 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,
>> Christian[/color]
>
> An interesting parallel can be made concerning management of production vs
> management 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.[/color]

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
interesting 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 computuational complexity of string searching
than any of the then known algorithms could provide.

Regards,
Christian
--
»It is no paradox to say that in our most theoretical
moods we may be nearest to our most practical applications.«
- Alfred North Whitehead

[and those "practical applications" will likely be most
"creative" ones..]

[Christian Stapfer]

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

"Ron Adam" <rrr@ronadam.co m> wrote in message
news:cTp4f.1618 0$ae.11317@torn ado.tampabay.rr .com...[color=blue]
> Christian Stapfer wrote:
>[color=green]
>> This discussion begins to sound like the recurring
>> arguments one hears between theoretical and
>> experimental 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,
>> Christian[/color]
>
> An interesting parallel can be made concerning management of production vs
> management 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.
>
> Both are good and needed for different types of tasks. And I think most
> programmers can switch styles to some degree if they need to.[/color]

Come to think of an experience that I shared
with a student who was one of those highly
creative experimentalist s you seem to have
in mind. He had just bought a new PC and
wanted to check how fast its floating point
unit was as compared to our VAX. After
having done his wonderfully creative
experimenting, he was utterly dejected: "Our (old)
VAX is over 10'000 times faster than my new PC",
he told me, almost in despair. Whereupon I,
always the uncreative, dogmatic theoretician,
who does not believe that much in the decisiveness
of the outcome of mere experiments, told him
that this was *impossible*, that he *must* have
made a mistake...

It turned out that the VAX compiler had been
clever enough to hoist his simple-minded test
code out of the driving loop. In fact, our VAX
calculated the body of the loop only *once*
and thus *immediately* announced that it had finished
the whole test - the compiler on this student's
PC, on the other hand, had not been clever enough
for this type of optimization: hence the difference...

I think this is really a cautionary tale for
experimentalist s: don't *believe* in the decisiveness
of the outcomes your experiments, but try to *understand*
them instead (i.e. relate them to your theoretical grasp
of the situation)...

Regards,
Christian

[Fredrik Lundh]

Re: Comparing lists

Christian Stapfer wrote:
[color=blue]
> 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
> interesting 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 computuational complexity of string searching
> than any of the then known algorithms could provide.[/color]

are you talking about KMP? I'm not sure that's really a good example of
how useful "theoretica l work" really is in practice:

- Morris had already implemented the algorithm (in 1968) when Knuth "dis-
covered" it (1971 or later), so the "then known" part of your argument is
obviously bogus. "then known by theoretical computer scientists" might
be correct, though.

- (iirc, Knuth's first version wasn't practical to use; this was fixed by Pratt)

- (and iirc, Boyer-Moore had already been invented when Knuth published the
first paper on KMP (in 1977))

- for use cases where the setup overhead is irrelevant, Boyer-Moore is almost
always faster than KMP. for many such cases, BM is a lot faster.

- for use cases such as Python's "find" method where the setup overhead cannot
be ignored, a brute-force search is almost always faster than KMP.

- for use cases such as Python's "find" method, a hybrid approach is almost
always faster than a brute-force search.

in other words, the "better" computational complexity of KMP has turned out
to be mostly useless, in practice.

</F>

[Steven D'Aprano]

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

On Sun, 16 Oct 2005 15:16:39 +0200, Christian Stapfer wrote:
[color=blue]
> Come to think of an experience that I shared
> with a student who was one of those highly
> creative experimentalist s you seem to have
> in mind. He had just bought a new PC and
> wanted to check how fast its floating point
> unit was as compared to our VAX. After
> having done his wonderfully creative
> experimenting, he was utterly dejected: "Our (old)
> VAX is over 10'000 times faster than my new PC",
> he told me, almost in despair.[/color]

Which it was. It finished executing his code in almost 1/10,000th of the
time his PC could do.
[color=blue]
> Whereupon I,
> always the uncreative, dogmatic theoretician,
> who does not believe that much in the decisiveness
> of the outcome of mere experiments, told him
> that this was *impossible*, that he *must* have
> made a mistake...[/color]

It wasn't a mistake and it did happen. The VAX finished the calculation
10,000 times faster than his PC. You have a strange concept of "impossible ".

[color=blue]
> It turned out that the VAX compiler had been
> clever enough to hoist his simple-minded test
> code out of the driving loop.[/color]

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?

For the record, the VAX 9000 can have up to four vector processors each
running at up to 125 MFLOPS each, or 500 in total. A Pentium III runs at
about 850 Mflops. Comparing MIPS or FLOPS from one system to another is
very risky, for many reasons, but as a very rough and ready measure
of comparison, a four processor VAX 9000 is somewhere about the
performance of a P-II or P-III, give or take some fudge factor.

So, depending on when your student did this experiment, it is entirely
conceivable that the VAX might have been faster even without the
optimization you describe. Of course, you haven't told us what model VAX,
or how many processors, or what PC your student had, so this comparison
might not be relevant.


[color=blue]
> In fact, our VAX
> calculated the body of the loop only *once*
> and thus *immediately* announced that it had finished
> the whole test - the compiler on this student's
> PC, on the other hand, had not been clever enough
> for this type of optimization: hence the difference...[/color]

Precisely. And all the Big O notation is the world will not tell you that.
Only an experiment will. Now, perhaps in the simple case of a bare loop
doing the same calculation over and over again, you might be able to
predict ahead of time what optimisations the compiler will do. But for
more complex algorithms, forget it.

This is a clear case of experimentation leading to the discovery
of practical results which could not be predicted from Big O calculations.
I find it quite mind-boggling that you would use as if it was a triumph
of abstract theoretical calculation when it was nothing of the sort.

[color=blue]
> I think this is really a cautionary tale for
> experimentalist s: don't *believe* in the decisiveness
> of the outcomes your experiments, but try to *understand*
> them instead (i.e. relate them to your theoretical grasp
> of the situation)...[/color]

Or, to put it another way: your student discovered something by running an
experimental test of his code that he would never have learnt in a million
years of analysis of his algorithm: the VAX compiler was very cleverly
optimized.

The fact that your student didn't understand the problem well enough to
craft a good test of it is neither here nor there.



--
Steven.

[Ron Adam]

Re: Comparing lists

Christian Stapfer wrote:[color=blue]
> "Ron Adam" <rrr@ronadam.co m> wrote in message
> news:cTp4f.1618 0$ae.11317@torn ado.tampabay.rr .com...
>[color=green]
>>Christian Stapfer wrote:
>>
>>[color=darkred]
>>>This discussion begins to sound like the recurring
>>>arguments 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,
>>>Christian[/color]
>>
>>An interesting parallel can be made concerning management of production vs
>>management 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.[/color]
>
>
> 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
> interesting 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 computuational complexity of string searching
> than any of the then known algorithms could provide.
>
> Regards,
> Christian[/color]

[color=blue]
> (even though you seem to believe that[color=green]
>> a theoretical bent of mind can only serve to stifle
>> creativity)[/color][/color]

No, that is not at all what I believe. What I believe is, "The
insistence of strict conditions can limit creative outcomes."

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. And the
level of insistence you keep in that view, leads me to believe you favor
a more productive environment rather than a more creative one. Both are
good, and I may entirely wrong about you, as many people are capable of
wearing different hats depending on the situation.

I think the gist of this thread may come down to...

In cases where it is not clear on what direction to go because the
choices are similar enough to make the choosing difficult. It is almost
always better to just pick one and see what happens than to do nothing.

Cheers,
Ron

[Christian Stapfer]

Re: Comparing lists

"Fredrik Lundh" <fredrik@python ware.com> wrote in message
news:mailman.21 37.1129475887.5 09.python-list@python.org ...[color=blue]
> Christian Stapfer wrote:
>[color=green]
>> 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
>> interesting 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 computuational complexity of string searching
>> than any of the then known algorithms could provide.[/color]
>
> are you talking about KMP?[/color]

Yes. I cannot give you the source of the story,
unfortunately, because I only have the *memory* of
it but don't know exactly *where* I happended to read
it. There, Knuth was said to have first analyzed the
theoretical argument very, very carefully to figure
out *why* it was that the theoretical bound was so
much better than all "practicall y known" algorithms.
It was by studing the theoretical work on computational
complexity *only* that the light dawned upon him.
(But of course, Knuth is "an uncreative dumbo fit
only for production work" - I am speaking ironically
here, which should be obvious.)
[color=blue]
> I'm not sure that's really a good example of
> how useful "theoretica l work" really is in practice:[/color]

Oh sure, yes, yes, it is. But my problem is to find
a good source of the original story. Maybe one
of the readers of this thread can provide it?
[color=blue]
> the "better" computational complexity of KMP has
> turned out to be mostly useless, in practice.[/color]

Well, that's how things might turn out in the long run.
Still, at the time, to all appearances, it *was* a
case of practical creativity *triggered* by apparently
purely theoretical work in complexity theory.

More interesting than your trying to shoot down
one special case of the more general phenomenon of
theory engendering creativity would be to know
your position on the more general question...

It happens *often* in physics, you known. Einstein
is only one example of many. Pauli's prediction of
the existence of the neutrino is another. It took
experimentalist s a great deal of time and patience
(about 20 years, I am told) until they could finally
muster something amounting to "experiment al proof"
of Pauli's conjecture.

Regards,
Christian
--
"Experience without theory is blind,
but theory without experience is mere
intellectual play."
- Immanuel Kant

»Experience remains, of course, the sole criterion
of the *utility* of a mathematical construction.
But *the*creative*p rinciple* resides in mathematics.«
- Albert Einstein: ‘The World As I See It’

»The astronomer Walter Baade told me that, when he
was dining with Pauli one day, Pauli exclaimed,
"Today I have done the worst thing for a theoretical
physicist. I have invented something which can never
be detected experimentally. " Baade immediately offered
to bet a crate of champagne that the elusive neutrino
would one day prove amenable to experimental discovery.
Pauli accepted, unwisely failing to specify any time
limit, which made it impossible for him ever to win
the bet. Baade collected his crate of champagne (as
I can testify, having helped Baade consume a bottle of it)
when, just over twenty years later, in 1953, Cowan and
Reines did indeed succeed in detecting Pauli’s particle.«
- Fred Hoyle: ‘Astronomy and Cosmology’

[Ron Adam]

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

Christian Stapfer wrote:
[color=blue]
> It turned out that the VAX compiler had been
> clever enough to hoist his simple-minded test
> code out of the driving loop. In fact, our VAX
> calculated the body of the loop only *once*
> and thus *immediately* announced that it had finished
> the whole test - the compiler on this student's
> PC, on the other hand, had not been clever enough
> for this type of optimization: hence the difference...
>
> I think this is really a cautionary tale for
> experimentalist s: don't *believe* in the decisiveness
> of the outcomes your experiments, but try to *understand*
> them instead (i.e. relate them to your theoretical grasp
> of the situation)...
>
> Regards,
> Christian[/color]

True understanding is of course the ideal, but as complexity increases
even theoretical information on a complex system becomes incomplete as
there are often other influences that will effect the outcome.

So the you could say: don't *depend* on the completeness of your
theoretical information, try to *verify* the validity of your results
with experiments.

Cheers,
Ron

[Christian Stapfer]

Re: Comparing lists

"Ron Adam" <rrr@ronadam.co m> wrote in message
news:jYv4f.1520 52$xl6.59875@to rnado.tampabay. rr.com...[color=blue]
> Christian Stapfer wrote:[color=green]
>> "Ron Adam" <rrr@ronadam.co m> wrote in message
>> news:cTp4f.1618 0$ae.11317@torn ado.tampabay.rr .com...
>>[color=darkred]
>>>Christian Stapfer wrote:
>>>
>>>
>>>>This discussion begins to sound like the recurring
>>>>arguments one hears between theoretical and
>>>>experimenta l 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,
>>>>Christian
>>>
>>>An interesting parallel can be made concerning management of production
>>>vs
>>>management 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.[/color]
>>
>>
>> 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
>> interesting 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=green]
>> (even though you seem to believe that[color=darkred]
>>> a theoretical bent of mind can only serve to stifle
>>> creativity)[/color][/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=blue]
> 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=blue]
> And the level of insistence you keep in that view,[/color]

A view that I do not really have: you are really projecting
indeed.
[color=blue]
> leads me to believe you favor a more productive environment
> rather than a more creative one.[/color]

You are mistaken. Although I have some "practical background"
(originally working as a "self-taught" programmer - although,
ironically, for a "developmen t and research department"),
I went on to study mathematics at the Federal Institute
of Technology here in Switzerland. Do you want to say that
having been trained as a mathematician makes one uncreative?
- But it is true that mathematicians are socialized in such
a way that they tend to take over rather high standards of
precision and theoretical grounding of their work.
[color=blue]
> Both are good, and I may entirely wrong about you,[/color]

... you are at least *somewhat* wrong about me,
that I am quite sure of...
[color=blue]
> as many people are capable of wearing different hats depending on the
> situation.
>
> I think the gist of this thread may come down to...
>
> In cases where it is not clear on what direction to go because the choices
> are similar enough to make the choosing difficult. It is almost always
> better to just pick one and see what happens than to do nothing.[/color]

As it appears, not even my most recent post has had
*any* recognizable effect on your thoroughly
misapprehending my position.

Regards,
Christian

[Steven D'Aprano]

Re: Comparing lists

On Sun, 16 Oct 2005 19:42:11 +0200, Christian Stapfer wrote:
[color=blue]
> Pauli's prediction of
> the existence of the neutrino is another. It took
> experimentalist s a great deal of time and patience
> (about 20 years, I am told) until they could finally
> muster something amounting to "experiment al proof"
> of Pauli's conjecture.[/color]

Pauli's conjecture was the result of experimental evidence that was
completely inexplicable according to the theory of the day: energy and
spin was disappearing from certain nuclear reactions. This was an
experimental result that needed to be explained, and Pauli's solution was
to invent an invisible particle that carried that energy and spin away.

(When I put it like that, it sounds stupid, but in fact it was an elegant
and powerful answer to the problem.)

The neutrino wasn't something that Pauli invented from theoretical first
principles. It came out of hard experimental results.

Physics of the last half century is littered with the half-forgotten
corpses of theoretical particles that never eventuated: gravitinos,
photinos, tachyons, rishons, flavons, hypercolor pre-quarks, axions,
squarks, shadow matter, white holes, and so on ad nauseum.

Neutrinos and quarks are exceptional in that experimental predictions of
their existence were correct, and I maintain that is because (unlike all
of the above) they were postulated to explain solid experimental results,
not just to satisfy some theoretical itch.

So yet again, your triumph of theory is actually a victory for experiment.


--
Steven.

[Christian Stapfer]

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

"Steven D'Aprano" <steve@REMOVETH IScyber.com.au> wrote in message
news:pan.2005.1 0.16.16.01.43.5 91166@REMOVETHI Scyber.com.au.. .[color=blue]
> On Sun, 16 Oct 2005 15:16:39 +0200, Christian Stapfer wrote:
>[color=green]
>> Come to think of an experience that I shared
>> with a student who was one of those highly
>> creative experimentalist s you seem to have
>> in mind. He had just bought a new PC and
>> wanted to check how fast its floating point
>> unit was as compared to our VAX. After
>> having done his wonderfully creative
>> experimenting, he was utterly dejected: "Our (old)
>> VAX is over 10'000 times faster than my new PC",
>> he told me, almost in despair.[/color]
>
> Which it was. It finished executing his code in almost 1/10,000th of the
> time his PC could do.
>[color=green]
>> Whereupon I,
>> always the uncreative, dogmatic theoretician,
>> who does not believe that much in the decisiveness
>> of the outcome of mere experiments, told him
>> that this was *impossible*, that he *must* have
>> made a mistake...[/color]
>
> It wasn't a mistake and it did happen.[/color]

Yes, yes, of course, it was a mistake, since
the conclusion that he wanted to draw from
this experiment was completely *wrong*.
Similarly, blind experimentalism *without*
supporting theory is mostly useless.
[color=blue]
> The VAX finished the calculation
> 10,000 times faster than his PC.
>You have a strange concept of "impossible ".[/color]

What about trying, for a change, to suppress
your polemical temperament? It will only lead
to quite unnecessarily long exchanges in this
NG.
[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]

But, mind you, his test was meant to determine,
*not* the cleverness of the VAX compiler *but*
the speed of the floating-point unit. So his
experiment was a complete *failure* in this regard.
[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]

My example was meant to point out how
problematic it is to assume that experimental
outcomes (without carefully relating them
back to supporting theory) are quite *worthless*.
This story was not about Big-Oh notation but
a cautionary tale about the relation between
experiment and theory more generally.
- Got it now?
[color=blue]
> For the record, the VAX 9000 can have up to four vector processors each
> running at up to 125 MFLOPS each, or 500 in total. A Pentium III runs at
> about 850 Mflops. Comparing MIPS or FLOPS from one system to another is
> very risky, for many reasons, but as a very rough and ready measure
> of comparison, a four processor VAX 9000 is somewhere about the
> performance of a P-II or P-III, give or take some fudge factor.[/color]

Well, that was in the late 1980s and our VAX
certanly most definitely did *not* have a
vector processor: we were doing work in
industrial automation at the time, not much
number-crunching in sight there.
[color=blue]
> So, depending on when your student did this experiment, it is entirely
> conceivable that the VAX might have been faster even without the
> optimization you describe.[/color]

Rubbish. Why do you want to go off a tangent like
this? Forget it! I just do not have the time to
start quibbling again.
[color=blue]
> Of course, you haven't told us what model VAX,[/color]

That's right. And it was *not* important. Since the
tale has a simple moral: Experimental outcomes
*without* supporting theory (be it of the Big-Oh
variety or something else, depending on context)
is mostly worthless.
[color=blue]
> or how many processors, or what PC your student had,
> so this comparison might not be relevant.[/color]

Your going off another tangent like this is
certainly not relevant to the basic insight
that experiments without supproting theory
are mostly worhtless, I'd say...
[color=blue][color=green]
>> In fact, our VAX
>> calculated the body of the loop only *once*
>> and thus *immediately* announced that it had finished
>> the whole test - the compiler on this student's
>> PC, on the other hand, had not been clever enough
>> for this type of optimization: hence the difference...[/color]
>
> Precisely. And all the Big O notation is the world will not tell you that.
> Only an experiment will. Now, perhaps in the simple case of a bare loop
> doing the same calculation over and over again, you might be able to
> predict ahead of time what optimisations the compiler will do. But for
> more complex algorithms, forget it.
>
> This is a clear case of experimentation leading to the discovery
> of practical results which could not be predicted from Big O calculations.[/color]

The only problem being: it was *me*, basing
myself on "theory", who rejected the "experiment al
result" that the student had accepted *as*is*.
(The student was actually an engineer, I myself
had been trained as a mathematician. Maybe that
rings a bell?)
[color=blue]
> I find it quite mind-boggling that you would use as if it was a triumph
> of abstract theoretical calculation when it was nothing of the sort.[/color]

This example was not at all meant to be any
such thing. It was only about: "experiment ing
*without* relating experimental outcomes to
theory is mostly worthless". What's more:
constructing an experiment without adequate
supporting theory is also mostly worthless.
[color=blue][color=green]
>> I think this is really a cautionary tale for
>> experimentalist s: don't *believe* in the decisiveness
>> of the outcomes your experiments, but try to *understand*
>> them instead (i.e. relate them to your theoretical grasp
>> of the situation)...[/color]
>
> Or, to put it another way: your student discovered[/color]

No. You didn't read the story correctly.
The student had accepted the result of
his experiments at face value. It was only
because I had "theoretica l" grounds to reject
that experimental outcome that he did learn
something in the process.
Why not, for a change, be a good loser?
[color=blue]
> something by running an experimental test of his code
> that he would never have learnt in a million
> years of analysis of his algorithm: the VAX compiler
> was very cleverly optimized.[/color]

Ok, he did learn *that*, in the end. But he
did *also* learn to thoroughly mistrust the
outcome of a mere experiment. Experiments
(not just in computer science) are quite
frequently botched. How do you discover
botched experiments? - By trying to relate
experimental outcomes to theory.

Regards,
Christian

[Christian Stapfer]

Re: Comparing lists

"Steven D'Aprano" <steve@REMOVETH IScyber.com.au> wrote in message
news:pan.2005.1 0.16.18.52.56.7 97555@REMOVETHI Scyber.com.au.. .[color=blue]
> On Sun, 16 Oct 2005 19:42:11 +0200, Christian Stapfer wrote:
>[color=green]
>> Pauli's prediction of
>> the existence of the neutrino is another. It took
>> experimentalist s a great deal of time and patience
>> (about 20 years, I am told) until they could finally
>> muster something amounting to "experiment al proof"
>> of Pauli's conjecture.[/color]
>
> Pauli's conjecture was the result of experimental evidence that was
> completely inexplicable according to the theory of the day:[/color]

So was it mere experiment or was it the relation
between experiment and theory that provided
the spur for creative advancement? My position
is the latter. Mere experiment does not tell you
anything at all. Only experiment on the background
of suitable theory does that.
[color=blue]
> energy and
> spin was disappearing from certain nuclear reactions. This was an
> experimental result that needed to be explained, and Pauli's solution was
> to invent an invisible particle that carried that energy and spin away.[/color]

Pauli's creativity lay in proposing *this*
particular solution to the puzzle. And, surely,
if it had not been for Pauli's characterizatio n
of that hypothetical particle, experimentalist s
like Cowan and Reines would not have *anything*
to aim for in the first place.

But I'm not going to argue Pauli's case any futher
in this NG, because this is, in the end,
not a physics NG...
[color=blue]
> (When I put it like that, it sounds stupid, but in fact it was an elegant
> and powerful answer to the problem.)
>
> The neutrino wasn't something that Pauli invented from theoretical first
> principles. It came out of hard experimental results.
>
> Physics of the last half century is littered with the half-forgotten
> corpses of theoretical particles that never eventuated: gravitinos,
> photinos, tachyons, rishons, flavons, hypercolor pre-quarks, axions,
> squarks, shadow matter, white holes, and so on ad nauseum.
>
> Neutrinos and quarks are exceptional in that experimental predictions of
> their existence were correct, and I maintain that is because (unlike all
> of the above) they were postulated to explain solid experimental results,
> not just to satisfy some theoretical itch.
>
> So yet again, your triumph of theory is actually a victory for experiment.[/color]

Well, I might tell now the story of Maxwell,
sitting in his garden - and deducing, from
his equations (which, admittedly, were inspired
by earlier experimental work by Faraday),
something really quite shockingly *new*:
the existence of electromagnetic waves.

Regards,
Christian
--
»From a long view of the history of mankind -
seen from, say, ten thousand years from now
- there can be little doubt that the most
significant event of the nineteenth century
will be judged as Maxwell's discovery of the
laws of electrodynamics . The American Civil
War will pale into provincial insignificance
in comparison with this important scientific
event of the same decade.«
- Richard P. Feynman: "The Feynman Lectures"