"in" everywhere

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Thu Oct 7 14:22:29 PDT 2010


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


More information about the Digitalmars-d mailing list