On 12/04/2015 11:57 PM, Andrei Alexandrescu wrote:
On 12/04/2015 04:40 PM, Timon Gehr wrote:
Another question is how widely applicable BigO should become beyond
std.container.
I'm thinking we could add complexity annotations to range functions. For
example the complexity of map is linear etc.
...
It depends on the mapped function.
E.g. some runtime bounds have multiple parameters.
Yah, I was wondering how necessary that'd be. One problem is how to
align parameters of different algorithms, for example say one is n * m
and the other is m log n. What if they swap the order of m and n?
I guess some reasonable convention should take care of this. Otherwise,
we'll need to use a hashtable mapping names to (exp, logExp) tuples.
Andrei
If only products should be expressible, this would maybe be reasonable
as well:
void foo(@(BigO.linear) int n,@(BigO.linear) int m);
But UDAs for parameters are not supported.
