Timon Gehr <[email protected]> wrote: > 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.) >
Brilliant! My wife has a work emergency so I've been with the kids all day, but here's what can be done to make this simpler. Use D parsing and eliminate the whole parsing routine. Add multiply and power are all defined so you only need log of bigo. Define global constants K, N, and N1 through N7. K is constant complexity all others are free variables. Then complexities are regular D expressions e.g BigO(N^2 * log(N)). On a the phone sry typos.
