On 12/04/2015 09:50 AM, tn wrote:
> However, my point is that it seems backwards if
> 1) When I don't care about the complexity, then I need to specify one
> (e.g. linearInsert).
> 2) When I care and want a constant complexity, then I don't specify one
> (e.g. use insert instead of constantInsert).

When complexity information is not present, the name of the function may carry an implicit and documented assumption of complexity bounds. -- Andrei

On 12/04/2015 01:05 AM, 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.

Well look at what the cat dragged in:

http://dpaste.dzfl.pl/711aecacc450

That's quite promising. The code is very preliminary and uses strings for typical complexity values (e.g. "constant", "linear", and later "loglinear" etc). I need to see how to integrate this whole idea.

Also an unpleasant problem is overloading - when present, user code needs to specify which overload they're referring to.

Anyhow, this is really interesting. Thanks Tofu.


Andrei

On Friday, 4 December 2015 at 15:33:56 UTC, Jonathan M Davis wrote:
> Only when dealing with an arbitrary number of elements. O(n^2) could be fine if you know for a fact that you're always dealing with a very small number of elements.

I think there was a misunderstanding about notation here. If we know that we use a small number of elements, then all operations are O(1) by definition, for any small constant.

> different algorithms perform there. O(1) is definitely better, but it's not necessarily required.

Well, O(1) isn't better, it is just mandatory for anything real time. E.g: you fix your buffer to 1 seconds of audio and that is 44100 samples, then filling it is O(44100) == O(1).

If am doing a scanline renderer for 2048 pixels, then an insertion sort is faster than merge sort, because most linesegments only move a few pixels per scanline. But here the problem is that there might be a 0.1% chance that most lines are almost horizontal in a variety of angles and then it breaks down, so that will be very limiting, but I still can figure out the hard maximum time required to complete, so it is still O(1) and tractable as a real time operation.

If I accept arbitrary input, then I no longer can meet real time requirements, I cannot get to O(1) and therefore cannot put a fixed limit on maximum time required to complete.

And that is really the only thing O(1) says: you can put a fixed limit on the time needed to complete the operation at compile time.

> actually involved. With large numbers of elements, Big-Oh starts mattering, but if the number of elements isn't large, then coefficients and minor implementation details of an algorithm start mattering a lot more than its conceptual worst case.

Yes, but most collections of entities are not very large by nature. Usually, when you try to solve a problem faster you break it down by useful segmentation and clusters (like age, kind, proximity).

Complexity is mostly for thinking about what options you have when designing an algorithm. The cookbook/library approach to complexity is rather limited since they were not written for the specifics of the problem.

> Still, in general, it's better to be aware of algorithmic complexity and favor algorithms with lower complexity until you need to optimize the code based on your specific use case and determine that a higher complexity algorithm actually performs better in that specific use case.

Be aware of it, yes. Although in real code it is often best to just start out with something flexible like a dynamic array, and optimize when you know which operations are required and what operations you never will need. That often changes over time.

I find that I am able to solve most of my real time problems with arrays. When I need hard requirements, I often end up using very simple datastructures like fixed sized circular buffers with a carefully calculated headroom (number of mostly unused elements) or linked lists of chunks or something really easy to reason about.

During initialisation of the program it often does not matter. So if I use linear search and it completes in 100ms then fine. I don't care if there is a delay of 100ms at startup.

For batch things done in Python, I just use whatever is easy, with current machines most things complete in less than a few seconds anyway.

Making libraries easy to use is by far the most important parameter, I think. What would be cool is if the compiler could adjust the implementation of collections based on profiling!

On Friday, 4 December 2015 at 16:06:25 UTC, Andrei Alexandrescu wrote:
> Well look at what the cat dragged in:
>
> http://dpaste.dzfl.pl/711aecacc450
>
> That's quite promising. The code is very preliminary and uses strings for typical complexity values (e.g. "constant", "linear", and later "loglinear" etc). I need to see how to integrate this whole idea.
>
> Also an unpleasant problem is overloading - when present, user code needs to specify which overload they're referring to.
>
> Anyhow, this is really interesting. Thanks Tofu.
>
>
> Andrei

Wow! It looks really great.

On Friday, 4 December 2015 at 16:06:25 UTC, Andrei Alexandrescu wrote:
> Well look at what the cat dragged in:
>
> http://dpaste.dzfl.pl/711aecacc450

This is a great compromise; I (and everyone else probably) would love to see a prototype of this when it's ready.

On 12/4/2015 7:11 AM, Jonathan M Davis wrote:
> On Friday, 4 December 2015 at 14:51:40 UTC, CraigDillabaugh wrote:
>> My personal preference would be not to have the complexity in the names, as I
>> prefer shorter/concise names. Typically when I am writing code using
>> containers of any sort I will check the documentation to determine what the
>> cost of the operations I need is and base my choice off of that. I would think
>> (hope) most others do this too.  However, I don't have a strong objection to
>> the what is being proposed.
>
> 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.


> But actually using something like stableLinearRemove in code (or
> stable.linear.remove) becomes hideous _very_ quickly. No one is going to like
> it,

I agree. Having such long names consisting of repeated use of the same words is a problem.

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.

On 12/04/2015 11:06 AM, Andrei Alexandrescu wrote:
> On 12/04/2015 01:05 AM, 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.
>
> Well look at what the cat dragged in:
>
> http://dpaste.dzfl.pl/711aecacc450

Following up on this, I thought I'd define a little algebra for complexities. It will be closed (no arbitrary expressions) and will support only the usually encountered complexities.

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)

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?


Andrei

On 12/04/2015 01:37 PM, Andrei Alexandrescu wrote:
>         | 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?

The question mark at log * linlog is spurious; should be replaced with linplog.

So the tricky cases are sqrt * log and sqrt * plog.


Andrei

On 04-Dec-2015 19:06, Andrei Alexandrescu wrote:
> On 12/04/2015 01:05 AM, 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.
>
> Well look at what the cat dragged in:
>
> http://dpaste.dzfl.pl/711aecacc450

Was vaguely terrified reading this whole thread until hitting this gem. Seems like a creative use for UDA.

>
> That's quite promising. The code is very preliminary and uses strings
> for typical complexity values (e.g. "constant", "linear", and later
> "loglinear" etc). I need to see how to integrate this whole idea.
>
> Also an unpleasant problem is overloading - when present, user code
> needs to specify which overload they're referring to.
>
> Anyhow, this is really interesting. Thanks Tofu.
>
>
> Andrei
>


-- 
Dmitry Olshansky

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.