On 12/07/2015 05:15 PM, Andrei Alexandrescu wrote:
On 12/07/2015 09:43 AM, Timon Gehr wrote:
1-2) BigO("1")
3) BigO("count")
4) BigO("distance(first,last)")
5) BigO("ilist.size()")
There's also this:
On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
Well you'd need multiple terms if you want to say things like,
"inserting a range into an array is O(array[].walkLength +
r.walkLength)." When you insert a range in a binary search tree, the
complexity would be O(log(array[].walkLength) * r.walkLength).
BigO("array[].walkLength + r.walkLength");
BigO("log(array[].walkLength) * r.walkLength");
These are still expressible without a DSL:
BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc.
...
This just goes from one string to two strings and adds some noise on top
of it. Also, now, what is D and what is in a string is arbitrary.
BigO(Var.array[].walkLength + Var.r.walkLength);
Somewhat independently of DSL or not:
Yes, notation does not matter at this stage.
At this point I'm unclear whether
supporting free variables with arbitrary names is a good thing.
Restricting the set of names to 8 predefined ones does not simplify
anything. It just means that a mapping of predefined names to real names
has to be carefully managed manually and clashes have to be avoided, all
while limiting the value of BigO as documentation.
The key
to unleashing the power of BigO is to compute it when combining
functions, and the names seem to be specific to the function and
therefore not easy to combine.
...
Just substitute something else for those names to get rid of them. That
is how passing of parameters is handled. Probably we should get some
actual examples where combination should work to see what could be done.
If you have:
void foo(int n,int m) @BigO("n*m^2"){ ... }
Something like this is easy to implement:
// compute runtime bound from bounds on parameters:
// first expression passed is O(x^3) and second expression passed
// is O(log(y)^(1/2)).
enum bound = getRuntimeBound!foo(BigO("x^3"),BigO("log(y)^(1/2)"));
static assert(bound == BigO("x^3*log(y)"));
Note how the end user does not need to worry much about names.
