"in" everywhere

[Stanislav Blinov]

Jonathan M Davis wrote:
> On Thursday, October 07, 2010 14:44:50 Stanislav Blinov wrote:

>> But that is not a matter of library interface isn't it? It's a matter of
>> algorithm/container choice. It's not the push_back that was slow in the
>> end, it was std::vector (yes, that's arguable, but the point is that
>> container defines rules for its methods, not vice-versa).
> 
> Except that when you're dealing with generic code which has to deal with 
> multiple container types (like std.algorithm), you _need_ certain complexity 
> guarantees about an operation since it could happen on any container that it's 
> given. Using operator in in an algorithm could be perfectly reasonable if it had 
> O(1) or O(log n) complexity but be completely unreasonable if it had O(n) 
> complexity. So, the algorithm then is reasonable with some containers and not 
> others when if in were restricted to O(1) or O(log n), it could be used by the 
> algorithm without worrying that a container would be used with it which would 
> make it an order of complexity greater, or worse.
> 
> If it were strictly a matter of writing code which directly used a particular 
> algorithm and container type, then you could know what the complexities of the 
> algorithm and operations on the container are, but once you're dealing with 
> generic code, operations need to have complexity guarantees regardless of their 
> container, or the complexity of the algorithm will vary with the container type. 
> And if that algorithm is used in yet another algorithm, then it gets that much 
> worse. It can quickly become easy to bury the place where what you're trying to 
> do becomes an order of complexity greater, because the container that you 
> selected was an order of complexity greater than other containers on an 
> operation that an algorithm is using buried in code somewhere.
> 
> - Jonathan M Davis

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.