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.

I gave up on this for the time being. Ideas welcome.


Andrei

On Saturday, 5 December 2015 at 20:48:16 UTC, Andrei Alexandrescu wrote:
> On 12/04/2015 10:24 PM, Timon Gehr wrote:
> 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.
>
> I gave up on this for the time being. Ideas welcome.
>
> Andrei

Well, we could see how CAS libraries handle this kind of stuff (if there _is_ one which handles it)...

Really, though, with the more complex algorithms, you start running into the kinds of issues noted in the first reply to this article: http://www.perlmonks.org/?node_id=573138

Besides, is anyone actually going to specify that they need an algorithm that is O(log(n) + m^2) or whatever? Or would a function just take _two_ algorithms, assert that each is O(log(n)) and O(m^2), respectively, and then compose them itself? The complexities depend on the types of container anyway, so in general, you should get only multi-term big-O notation when you're using multiple containers (or Cartesian products of a container with itself or something like that). Can't we just make sure one container's insert() and the other container's sort() work within a certain complexity?

On Sat, Dec 05, 2015 at 09:52:08PM +0000, BLM768 via Digitalmars-d wrote:
> On Saturday, 5 December 2015 at 20:48:16 UTC, Andrei Alexandrescu wrote:
> >On 12/04/2015 10:24 PM, Timon Gehr wrote:
> >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.
> >
> >I gave up on this for the time being. Ideas welcome.
> >
> >Andrei
> 
> Well, we could see how CAS libraries handle this kind of stuff (if there _is_ one which handles it)...
> 
> Really, though, with the more complex algorithms, you start running into the kinds of issues noted in the first reply to this article: http://www.perlmonks.org/?node_id=573138
> 
> Besides, is anyone actually going to specify that they need an
> algorithm that is O(log(n) + m^2) or whatever? Or would a function
> just take _two_ algorithms, assert that each is O(log(n)) and O(m^2),
> respectively, and then compose them itself? The complexities depend on
> the types of container anyway, so in general, you should get only
> multi-term big-O notation when you're using multiple containers (or
> Cartesian products of a container with itself or something like that).
> Can't we just make sure one container's insert() and the other
> container's sort() work within a certain complexity?

Multi-term complexities arise from trivial graph algorithms. They are not limited to the use of multiple containers. More precisely, the multiple terms arise because of the structure of the graph (being composed of nodes and edges); what the algorithms add are functions on nodes and edges.

Unfortunately, once you have more than a single variable in your functions, the big-O expressions rapidly become inextricably complex, and can no longer map to nice abstractions like the reals + infinities + infinitesimals linear ordering. For example, two graph algorithms may be, respectively, O(V^2 + E) and O(V + E^2); it's difficult to judge based on that which one is "superior".


T

-- 
They say that "guns don't kill people, people kill people." Well I think the gun helps. If you just stood there and yelled BANG, I don't think you'd kill too many people. -- Eddie Izzard, Dressed to Kill

On 12/05/2015 04:52 PM, BLM768 wrote:
>
> Well, we could see how CAS libraries handle this kind of stuff (if there
> _is_ one which handles it)...

CAS = ?

> Really, though, with the more complex algorithms, you start running into
> the kinds of issues noted in the first reply to this article:
> http://www.perlmonks.org/?node_id=573138
>
> Besides, is anyone actually going to specify that they need an algorithm
> that is O(log(n) + m^2) or whatever? Or would a function just take _two_
> algorithms, assert that each is O(log(n)) and O(m^2), respectively, and
> then compose them itself? The complexities depend on the types of
> container anyway, so in general, you should get only multi-term big-O
> notation when you're using multiple containers (or Cartesian products of
> a container with itself or something like that). Can't we just make sure
> one container's insert() and the other container's sort() work within a
> certain complexity?

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).

Part of the art here, I feel, is knowing when to stop going too crazy about this. At this point we have a nice, round system that's simple to understand and use. Making it more complex should come only with a corresponding growth in power.


Andrei

On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
> On 12/05/2015 04:52 PM, BLM768 wrote:
>>
>> Well, we could see how CAS libraries handle this kind of stuff (if there
>> _is_ one which handles it)...
>
> CAS = ?
> ...

Computer Algebra System, I assume.

On Saturday, 5 December 2015 at 23:55:16 UTC, Andrei Alexandrescu wrote:
> On 12/05/2015 04:52 PM, BLM768 wrote:
>>
>> Well, we could see how CAS libraries handle this kind of stuff (if there
>> _is_ one which handles it)...
>
> CAS = ?

https://en.wikipedia.org/wiki/Computer_algebra_system

On Saturday, 5 December 2015 at 22:56:23 UTC, H. S. Teoh wrote:
> Multi-term complexities arise from trivial graph algorithms. They are not limited to the use of multiple containers. More precisely, the multiple terms arise because of the structure of the graph (being composed of nodes and edges); what the algorithms add are functions on nodes and edges.

True. I don't expect that very many people would want to specify an algorithmic complexity for those operations, though. It seems much more rigidly defined than for lists, arrays, etc. The question is not really about whether "complex complexities" will exist but whether the user has a practical reason to care about specifying them.

> Unfortunately, once you have more than a single variable in your functions, the big-O expressions rapidly become inextricably complex, and can no longer map to nice abstractions like the reals + infinities + infinitesimals linear ordering. For example, two graph algorithms may be, respectively, O(V^2 + E) and O(V + E^2); it's difficult to judge based on that which one is "superior".

Well, if one variable is "capped" (or at least expected to be "small") it's easy enough to eliminate that term. Beyond that, there isn't necessarily a single ordering of big-O expressions, but many of them can be ordered relative to a single variable. For instance, O(n + m^2) is less complex than O(n^2 + m) with respect to n (and vice versa for m). It's trickier when expressions are more deeply nested, but if select one term (in this case, n), set all the others to be constant (since none of them depends on n), and evaluate the resulting expression tree, you should get something half-usable. Some simplifying rules may be useful. For instance, log(x^2) should approach log(x) as x approaches infinity, I think. (My calculus is a bit rusty.)

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.)

On 12/06/2015 03:47 AM, BLM768 wrote:
> log(x^2) should approach log(x) as x approaches infinity, I think. (My
> calculus is a bit rusty.)

log(x^2) = 2 log x.

On Sunday, 6 December 2015 at 03:30:51 UTC, Timon Gehr wrote:
> log(x^2) = 2 log x.

Why do log rules have to make everything so simple? ;)