On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
>
>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. ...
>
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.
...
The implementation of power on BigO given does not actually work in
general (there should have been an enforcement that makes sure there is
only one summand). I'll think about whether and how it can be made to
work for multiple summands.
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.
I generally tend to avoid DSLs based solely on operator overloading, as
they don't always work and hence are awkward to evolve. Here, the
biggest current nuisance is that the variable names are not very
descriptive. If we'll go with a log(BigO) function, we possibly want to
make BigO closed under log without approximating iterated logarithms:
struct Term{
Variable n;
Fraction[] exponents; // exponents[0] is exponent of n,
// exponents[1] is exponent of log n,
// exponents[2] is exponent of log log n, ...
}
Then O(log(f^c*g^d)) = O(log(f)+log(g)) = O(log(f+g)) [1], and hence
every BigO has a well-defined logarithm.
[1] O(log(f+g)) ⊆ O(log(f*g)) = O(log(f)+log(g)).
O(log(f)+log(g)) ⊆ O(max(log(f),log(g)))
= O(log(max(f,g)))
⊆ O(log(f+g)).
