On 10/7/10 15:23 CDT, Rainer Deyke wrote:
On 10/7/2010 13:57, Andrei Alexandrescu wrote:
On 10/7/10 14:40 CDT, bearophile wrote:
Another solution is just to accept O(n) as the worst complexity for
the "in" operator. I don't understand what's the problem in this.
That means we'd have to define another operation, i.e. "quickIn" that
has O(log n) bound.
Why?
I can't say I've ever cared about the big-O complexity of an operation.
Complexity composes very badly. Issues tend to manifest at moderate
sizes and may make things unbearable at large sizes. I'm really grateful
I'm at a workplace where the exclamation "Damn! I was waiting like an
idiot for this quadratic append!" is met with understanding nods from
workmates who've made the same mistake before.
As an example, only last week I was working on cramming a sort of an
index of the entire Wikipedia on one machine. I was waiting for the
indexer which ran slower and slower and slower. In the end I figured
there was only _one_ quadratic operation - appending to a vector<size_t>
that held document lengths. That wasn't even the bulk of the data and it
was the last thing I looked at! Yet it made the run time impossible to
endure.
All I care about is that it's "fast enough", which is highly
context-dependent and may have nothing to do with complexity. I can't
see myself replacing my 'int[]' arrays with the much slower and bigger
'int[MAX_SIZE]' arrays just to satisfy the compiler. I shouldn't have
to. The type system shouldn't encourage me to.
I think it's an abuse of the type system to use it to guarantee
performance. However, if I wanted the type system to provide
performance guarantees, I would need a lot more language support than a
convention that certain operations are supposed to be O(n). I'm talking
performance specification on *all* functions, with a compile-time error
if the compiler can't prove that the compiled function meets those
guarantees. And *even then*, I would like to be able to use an O(n)
implementation of 'in' where I know that O(n) performance is acceptable.
std.container introduces the convention that O(n) methods start with
"linear".
Andrei
