On Friday, 4 December 2015 at 22:48:03 UTC, Andrei Alexandrescu wrote:
> 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

Looks good :)

On 12/4/15 5:48 PM, Andrei Alexandrescu wrote:
> 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.

This looks very excellent, nice work!

-Steve

On 12/04/2015 04:40 PM, Timon Gehr wrote:
> Another question is how widely applicable BigO should become beyond
> std.container.

I'm thinking we could add complexity annotations to range functions. For example the complexity of map is linear etc.

>E.g. some runtime bounds have multiple parameters.

Yah, I was wondering how necessary that'd be. One problem is how to align parameters of different algorithms, for example say one is n * m and the other is m log n. What if they swap the order of m and n?

I guess some reasonable convention should take care of this. Otherwise, we'll need to use a hashtable mapping names to (exp, logExp) tuples.


Andrei

On Fri, Dec 04, 2015 at 05:48:03PM -0500, Andrei Alexandrescu via Digitalmars-d wrote:
> 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.
[...]

Nice, very nice!

But ... opMul? I thought that was deprecated? Shouldn't we be using opBinary!"*" instead?


T

-- 
Food and laptops don't mix.

On 12/4/2015 2:48 PM, Andrei Alexandrescu wrote:
> 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.


This is very similar to the si units program Oskar Linde wrote back in 2006.

Anyhow, this is very cool and should:

1. have an article written about it
2. get its own Phobos module

On Friday, 4 December 2015 at 22:17:21 UTC, Jonathan M Davis wrote:
> 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.

It should be possible to unify the template and UDA forms. Assuming a template supportsComplexity(func, complexity) that determines whether a function or method has the specified complexity UDA (or a "faster" one), it's not hard to implement something like this:

void removeWithComplexity(T, complexity)(T collection, size_t index) if(supportsComplexity!(T.remove, complexity) {
    collection.remove(idx);
}

List!int list;
//...
list.removeWithComplexity(Complexity.linear, 3);

---

Of course, this implementation has issues with collection operations which are defined as UFCS functions (as opposed to methods), but it should be possible to get around that issue.

On Saturday, 5 December 2015 at 00:13:02 UTC, BLM768 wrote:
> list.removeWithComplexity(Complexity.linear, 3);

Uh, I mean list.removeWithComplexity!(Complexity.linear)(3).

On 12/04/2015 11:57 PM, Andrei Alexandrescu wrote:
> On 12/04/2015 04:40 PM, Timon Gehr wrote:
>> Another question is how widely applicable BigO should become beyond
>> std.container.
>
> I'm thinking we could add complexity annotations to range functions. For
> example the complexity of map is linear etc.
> ...

It depends on the mapped function.

>> E.g. some runtime bounds have multiple parameters.
>
> Yah, I was wondering how necessary that'd be. One problem is how to
> align parameters of different algorithms, for example say one is n * m
> and the other is m log n. What if they swap the order of m and n?
>
> I guess some reasonable convention should take care of this. Otherwise,
> we'll need to use a hashtable mapping names to (exp, logExp) tuples.
>
>
> Andrei
>

If only products should be expressible, this would maybe be reasonable as well:

void foo(@(BigO.linear) int n,@(BigO.linear) int m);

But UDAs for parameters are not supported.

On 12/05/2015 04:24 AM, Timon Gehr wrote:
>>
>
> If only products should be expressible,

But I think not. O(n+m) is common.

On 05-Dec-2015 01:48, Andrei Alexandrescu wrote:
> 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

Better still - no more strings:

http://dpaste.dzfl.pl/5ed2b3ad3043

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


-- 
Dmitry Olshansky