Comparing lists - somewhat OT, but still ...

[Ognen Duzlevski]

Steven D'Aprano <steve at removethiscyber.com.au> wrote:
> On Sun, 16 Oct 2005 15:16:39 +0200, Christian Stapfer wrote:

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

> 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?

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