On 12/05/2015 09:48 PM, Andrei Alexandrescu wrote:
On 12/04/2015 10:24 PM, Timon Gehr wrote:
void foo(@(BigO.linear) int n,@(BigO.linear) int m);
But UDAs for parameters are not supported.
That's actually pretty neat and easy to work around like this:
void foo(int n, int m) @(BigOParam!2(BigO.linear, BigO.linear);
In fact I went through the implementation but soon I hit a wall: what's
the _relationship_ between the two growths? It may be the sum O(m + n)
but also the product O(m * n). So the operator must be encoded as well.
Then what do we do with more complex relationships like O((m + n) log n)
etc.
Then once you get to some reasonable formula, what's the ordering on top
of these complexities? Probably difficult.
...
Some upper bounds are incomparable, so there would not be a total order.
But that is not a problem.
I gave up on this for the time being. Ideas welcome.
...
The next step up the expressiveness scale would be to have a
sum-of-products representation.
Proof of concept (disclaimer: hacked together in the middle of the
night, and not tested thoroughly):
http://dpaste.dzfl.pl/d1512905accd
I think this general approach is probably close to the sweet spot. (The
implementation is not feature-complete yet, though. It would be nice if
it supported automatically computing a new asymptotic runtime bound from
asymptotic bounds on the arguments.)
