December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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 |
December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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.
|
December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | 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 |
December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | 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. |
December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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 |
December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tofu Ninja | 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!
|
December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dmitry Olshansky | 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.
|
December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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.
|
December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | 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 |
December 04, 2015 Re: Complexity nomenclature | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | 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 |
Copyright © 1999-2021 by the D Language Foundation