"in" everywhere

[Rainer Deyke]

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


-- 
Rainer Deyke - rainerd at eldwood.com