"in" everywhere

[Jonathan M Davis]

On Friday 08 October 2010 03:06:01 Stanislav Blinov wrote:
> Yet still, generality ends at some point. You can't devise every
> possible algorithm for any possible types and have it have set-in-stone
> complexity independently of types.
> 
> Take std.range.popFrontN(). It's generic, and it's used in other
> algorithms. Yet it has O(1) complexity for ranges that support slicing,
> and O(n) for those that do not. But you don't take into account
> complexity of slicing operation, or complexity of stepping through the
> range.
> 
> Or std.algorithm.find(). It's basically O(n), but then again, when using
> it, one should also consider complexity of used predicate.
> Just the same happened in the case Andrei described: the algorithm was
> O(n) judging from the description (performing n insertions into
> container). But the container itself blew it up into quadratic time
> because of it's own insertion algorithm.
> 
> What I mean is you'll always have algorithms that will perform
> differently for different containers, and you'll always have to choose
> containers that best fit your needs. Generic code is not only about
> efficiency: you'd at least expect it to work for different types.
> Replacing vector with list in Andrei's case would probably solve the
> problem at the cost of losing random access (together with contiguous
> storage). Which means it'd also require changing code if random access
> was in use somewhere. Having a generic random access function
> at(Container,index) (offering complexity that varies with container
> used: e.g. O(1) for arrays, O(n) for lists) would save you maintenance.

All true. However, the point is that operations need to have a know complexity. 
If in is known to be O(1), the algorithms can safely use it, knowing that it's 
O(1). Any container that can't do it in O(1) doesn't implement in. You could, on 
the other hand, have in be O(n) (which doesn't stop containers from implementing 
it as O(1) since that's better than O(n)), and then any algorithm that uses it 
has to assume that it could be O(n) and therfore may need to avoid it. The real 
question is what complexity we want to define it as. At the moment, the only 
container to use it are the built-in associative arrays, and for them, it's 
O(1). Since find() is already going to be O(n), it seems to me that in should be 
better than O(n) - be it O(1) or O(log n) - and Andrei appears to agree, but 
others don't, hence this long discussion...

- Jonathan M Davis