On Fri, Dec 04, 2015 at 01:37:06PM -0500, Andrei Alexandrescu via Digitalmars-d wrote:
> On 12/04/2015 11:06 AM, Andrei Alexandrescu wrote:
[...]
> Here's the algebra.
> 
> Terms:
> 
> 1 = O(1)
> log = O(log n)
> plog = O((log n)^k)
> sqrt = O(sqrt n)
> lin = O(n)
> linlog = O(n * log n)
> linplog = O(n * (log n)^k)
> poly = O(n^k)
> exp = O(2^n)
> 
> Ordering:
> 
> Terms above are in increasing order.
> 
> Summation:
> 
> x + y = max(x, y)
> 
> Product:
> 
>        | 1       log      plog     sqrt  lin      linlog   poly  exp
> 
> -------+------------------------------------------------------------
> 1      | 1       log      plog     sqrt  lin      linlog   poly  exp
> 
> log    | log     plog     plog     ?     linlog   ?        poly  exp plog   | plog    plog     plog     ?     linplog  linplog  poly  exp sqrt   | sqrt    ?        ?        lin   poly     poly     poly  exp lin    | lin     linlog   linplog  poly  poly     poly     poly  exp linlog | linlog  linplog  linplog  poly  poly     poly     poly  exp poly   | poly    poly     poly     poly  poly     poly     poly  exp exp    | exp     exp      exp      exp   exp      exp      exp   exp
> 
> I've left a few question marks for the tricky cases. Ideas?
[...]

sqrt really belongs under poly, as far as asymptotic behaviour is
concerned. Basically, O(n^j) * O(n^k) for any real j, k > 0 is
asymptotically equal to O(n^(j+k)). Furthermore, O(O(n^j)^k) =
O(n^(j*k)). So you can treat polynomial complexities as a field of real
numbers, where + on the O(...) terms behaves like max(), * behaves like
+, and function composition behaves like ^.

Then exp behaves like an "infinite real", where exp > O(n^k) for all
real k>0. Its inverse, log, therefore, behaves like an "infinitesimal",
where O((log n)^k) for all real k>0 is less than O(n^k) for all real
k>0. (Yes, even O(n^(1/1000000)) will eventually outgrow O(log n).)

The log powers behave like "intermediate infinitesimals", where you have
O((log n)^j) < O((log n)^k) for all positive real j < k.

So these O-terms behave approximately like real numbers (poly) enhanced
with infinite quantities (exp and its derivations) and infinitesimal
quantities (log and its derivations), they follow the usual laws of
arithmetic. Therefore,

	O(n^k) * O(log n)

can be treated as the equivalent of a real number k + an infinitesimal L, such that k < (k+L) < k+j for all real j>0. In other words,

	O(n) < O(n * log n) < O(n^(1+k))  for all k>0.

(Yes, even O(n^1.00000000001) will eventually outgrow O(n*log n). O(log
n) behaves like an infinitesimal.)

The nice thing about this is that you can simplify a lot of complicated O(...) expressions just by applying algebra as described above on the analogous {real + infinities + infinitesimals} system. Ordering relations are preserved (for the most part -- this only breaks down with pathological cases like O(sin n) which is unlikely to be ever encountered). Also, function composition between poly and non-poly complexities will generally be non-commutative, and mostly will break the + = max analogy. (But it seems unlikely, in real-world algorithms, to ever need to worry about the intricacies of exponential-time algorithms, since generally they are to be avoided where possible.)

So you can get a (mostly) closed algebra just by mapping poly to the
real numbers, and then adding:

	L = infinitesimal quantity corresponding to O(log n)
	E = infinite quantity corresponding to exp

Various operations inside O(...) are thus mapped:

	+ inside O(...) = max(...)
	* inside O(...) = + between mapped quantities
	O(f(g(n))) = O(f(n)) * O(g(n))
	O(1) = 0

Example: is O(n^3*log(n)) better than O(n^2*(log(n))^3)?
Answer:
	O(n^3*log(n)) maps to 3 + L, and O(n^2*(log(n))^3) maps to 2 +
	L^3. Since L^3 is infinitesimal, (2 + L^3) is very close to 2,
	whereas (3 + L) lies slightly above 3. Therefore O(n^3*log(n))
	is definitely faster-growing than O(n^2*(log(n))^3).

This algebra leads to various interesting questions like:

- Is there an intermediate complexity that lies between poly and exp?
  Yes: since exp is mapped to the infinite quantity E, it follows that
  E/2 is still an infinite quantity (even though it's strictly less than
  E). E/2 corresponds to E*1/2, which is the composition of exp with
  sqrt, so it follows that O(n^k) < O(e^sqrt(n)) < O(e^n) for all real
  k>0. (There are, of course, many other possibilities.)

- Similarly, the log powers O((log n)^k) are *always* slower-growing
  than any polynomial complexity, because L*k, being still
  infinitesimal, will always < j for all real j>0. So even
  O((log n)^10000) will not outgrow O(n^1.000000001). Multiplying with a
  poly function preserves this relationship:

  	O(n^j * (log n)^k) --> j + L*k < j + m, for all real j,m>0, so
	O(n^j * (log n)^k) < O(n^(j+m)) for all j,m>0.

  Basically you're just displacing the mapped values by a constant.


T

-- 
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird. -- D. Knuth

Timon Gehr <timon.gehr@gmx.ch> wrote:
> On 12/04/2015 07:37 PM, Andrei Alexandrescu wrote:
>> Following up on this, I thought I'd define a little algebra ....
>> It will be closed (no arbitrary expressions)
>> ...
> 
> I think that the exponents matter. E.g. n^1.5 vs n^2.
> The algebra can be made more expressive while simplifying its
> implementation.
> 
>> 
>> The idea is to allow functions to compute their own complexity in terms of complexities of their respective primitives.
>> 
>> Here's the algebra.
>> 
>> Terms:
>> 
>> 1 = O(1)
>> log = O(log n)
>> plog = O((log n)^k)
>> sqrt = O(sqrt n)
>> lin = O(n)
>> linlog = O(n * log n)
>> linplog = O(n * (log n)^k)
>> poly = O(n^k)
>> exp = O(2^n)
> 
> Example alternative:
> 
> struct BigO{
>     Fraction logExp;
>     Fraction polyExp;
>     Fraction expBase;
> 
>     bool opCmp(BigO rhs){
>         return
> tuple(expBase,polyExp,logExp).opCmp(tuple(rhs.expBase,polyExp,logExp));
>     }
>     BigO opBinary(string op:"*")(BigO rhs){
>         return
> BigO(logExp+rhs.logExp,polyExp+rhs.polyExp,expBase*rhs.expBase);
>     }
>     // ...
> }
> 
> Your cases then become:
> 
> O(1):     expBase=1, polyExp=0, logExp=0;
> O(log n): expBase=1, polyExp=0, logExp=1;
> O((log n)^k): expBase=1, polyExp=0, logExp=k;
> O(sqrt n): expBase=1, polyExp=Fraction(1,2), logExp=0;
> O(n): expBase=1, polyExp=1, logExp=0;
> O(n * log n): expBase=1, polyExp=1, logExp=1;
> O(n * (log n)^k): expBase=1, polyExp=1, logExp=k;
> O(n^k): expBase=1, polyExp=k, logExp=0;
> O(2^n): expBase=2, polyExp=0, logExp=0;
> 
> Combinations just work, especially n^(1/2) * log n.
> 
> 
> 

Nice, I'll continue with this. Thanks! I won't use expBase because no operation leads to it; instead I'll just lump everything superpoly into one "fast growing" category.

I'll get back to this (on the phone) but this is incorrect:

sqrt really belongs under poly, as far as asymptotic behaviour is concerned.

Fractional powers are sublinear. And sqrt times sqrt is linear which is important.


Andrei

On Friday, 4 December 2015 at 18:21:41 UTC, Walter Bright wrote:
> I suggested in the pseudo namespaces thread using template parameters to express characteristics, as in:
>
>     remove!(stable, linear)
>
> with sensible defaults so most of the time the user would just use:
>
>     remove

The nice thing about this is that it can be easy to specify which complexities an operation supports.

---

void remove(complexity, T)(List!T list, size_t index) if(complexity >=
    Complexity.linear); //or however complexity objects work...

List l;
//...
l.remove(3);
l.remove!(Complexity.polynomial(2))(3);
l.remove!(Complexity.constant)(3);//fails; there's no template specialization for this case because complex < linear.

On Fri, Dec 04, 2015 at 08:03:17PM +0000, Andrei Alexandrescu via Digitalmars-d wrote:
> I'll get back to this (on the phone) but this is incorrect:
> 
> sqrt really belongs under poly, as far as asymptotic behaviour is concerned.

OK, I guess by poly you mean n^k for k>1.  I was lumping everything under polynomial for k>0. The reason is because of the homogeneity for all values of k>0 when it comes to the algebra of complexities. Obviously, for performance-measuring purposes, k=1 is a significant landmark.


> Fractional powers are sublinear.

Wrong, O(n^(4/3)) is a fractional power, but it's not sublinear.


> And sqrt times sqrt is linear which is important.
[...]

But it's just a special case of the general multiplicative->additive rule. Everyone knows 1/2 + 1/2 = 1; it doesn't seem to warrant special treatment above, say, 1/3 + 2/3 = 1, or any of the other endless identities involving 1.


T

-- 
Meat: euphemism for dead animal. -- Flora

On 12/3/2015 10:05 PM, Tofu Ninja wrote:
> Also maybe a simpler idea would just be to annotate the the operations with
> there complexity with UDAs. That way things that really care about the
> complexity can get it, and those who don't can ignore it. It has the benefit of
> being self documenting as well.

Dang, you beat me to it!

On 12/4/2015 10:49 AM, Dmitry Olshansky wrote:
> Was vaguely terrified reading this whole thread until hitting this gem. Seems
> like a creative use for UDA.

Yeah, I think it puts UDA on the map!

Instead of string arguments, though, I suggest enums.

On 12/04/2015 09:03 PM, Andrei Alexandrescu wrote:
>> >
>> >Your cases then become:
>> >
>> >O(1):     expBase=1, polyExp=0, logExp=0;
>> >O(log n): expBase=1, polyExp=0, logExp=1;
>> >O((log n)^k): expBase=1, polyExp=0, logExp=k;
>> >O(sqrt n): expBase=1, polyExp=Fraction(1,2), logExp=0;
>> >O(n): expBase=1, polyExp=1, logExp=0;
>> >O(n * log n): expBase=1, polyExp=1, logExp=1;
>> >O(n * (log n)^k): expBase=1, polyExp=1, logExp=k;
>> >O(n^k): expBase=1, polyExp=k, logExp=0;
>> >O(2^n): expBase=2, polyExp=0, logExp=0;
>> >
>> >Combinations just work, especially n^(1/2) * log n.
>> >
>> >
>> >
> Nice, I'll continue with this. Thanks! I won't use expBase because no
> operation leads to it; instead I'll just lump everything superpoly into one
> "fast growing" category.
>

This is probably sensible in the context of std.container.
Note that some containers only give amortized guarantees. E.g. in C++, calling push_back n times on a vector that starts out empty is O(n), but the worst case for a single push_back is Ω(n).

Another question is how widely applicable BigO should become beyond std.container. E.g. some runtime bounds have multiple parameters.

On Friday, 4 December 2015 at 18:21:41 UTC, Walter Bright wrote:
> On 12/4/2015 7:11 AM, Jonathan M Davis wrote:
>> std.container puts linear and/or stable in some of its names and then creates an
>> alias to whichever one makes sense as the default where the alias doesn't have
>> linear or stable in the name. e.g. linearRemove becomes remove via an alias.
>
> Excessive use of aliases is a problem in and of itself - for example, trying to use a debugger with it, or examining the object code.

Oh, I agree. But if we end up with stuff like stableLinearRemove all over the place, it's better to have the aliases than not. However, it's far better IMHO to avoid having all of those long names in the first place.

> I suggested in the pseudo namespaces thread using template parameters to express characteristics, as in:
>
>     remove!(stable, linear)
>
> with sensible defaults so most of the time the user would just use:
>
>     remove
>
> Generic code could use the parameters. Another alternative is to have attributes for the algorithm:
>
>     @stable @linear remove() { ... }
>
> and then generic code could test for those attributes.

Either of those would be better than stableLinearRemove or stable.linear.remove. The UDAs would be more documentation friendly, though being able to pass around template arguments could be valuable for the cases where you're trying to enforce specific complexity requirements.

- Jonathan M Davis

On 12/04/2015 03:43 PM, Walter Bright wrote:
> On 12/4/2015 10:49 AM, Dmitry Olshansky wrote:
>> Was vaguely terrified reading this whole thread until hitting this
>> gem. Seems
>> like a creative use for UDA.
>
> Yeah, I think it puts UDA on the map!
>
> Instead of string arguments, though, I suggest enums.

"Even better".

http://dpaste.dzfl.pl/50340e189f92

That code is actually remarkably complete, with algebra and remarkable constants.

Pretty crazy, yo. Thanks all for the great ideas. D is a remarkable language.


Andrei