On 12/03/2015 09:24 PM, Timon Gehr wrote:
> On 12/04/2015 03:18 AM, Andrei Alexandrescu wrote:
>> On 12/03/2015 08:37 PM, Jack Stouffer wrote:
>>> On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
>>>> These complexities must be reflected in the name of the primitives.
>>>
>>> I don't see why. IMO, names should convey what the function does, not
>>> how it does it. Complexity is usually put in the function documentation
>>> in Phobos when it's not constant, especially for range based ones, I
>>> don't see a reason to change that.
>>
>> Complexity is part of the semantics, and in my design names and their
>> semantics go hand in hand. -- Andrei
>>
>
> Which is sensible. But in any given context, some parts of the semantics
> are usually abstracted away. Sometimes one wants to abstract over
> running times of called methods. ("This function calls this other
> function at most O(n) times.")

Sure, and there will be provision for that. The collections framework will contain logic such as: "If collection type C implements insertAfter, then implement UFCS function linearInsertAfter that forwards to it". So if as user you're fine with linearInsertAfter, it'll work as an upper bound. -- Andrei

On 12/03/2015 09:27 PM, Timon Gehr wrote:
> On 12/04/2015 03:19 AM, Andrei Alexandrescu wrote:
>> On 12/03/2015 08:55 PM, Timon Gehr wrote:
>>> I don't really understand what calling it 'complexity' actually buys
>>> though.
>>
>> Instant understanding by everyone. -- Andrei
>
> Well, no. "running time" is actually more descriptive.

http://en.cppreference.com/w/cpp/container/forward_list/insert_after

Andrei

On 12/04/2015 03:34 AM, Xinok wrote:
> On Friday, 4 December 2015 at 01:55:15 UTC, Timon Gehr wrote:
>> Regarding nomenclature, it would be awesome if we could call this
>> "running time" instead of "complexity". Algorithms have running times
>> and memory usages. Problems have (time and space) complexities. I know
>> that calling running time 'complexity' is awfully popular outside of
>> actual complexity theory papers. I don't really understand what
>> calling it 'complexity' actually buys though.
>
> I've seen you mention this before, and while you may be correct, the
> term "complexity" is so widely applied to algorithms that it's not worth
> going against the norm. For the vast majority of computer scientists,
> when they hear the term "time complexity", they immediately understand
> it as running time.

I understand what is meant, but it is painful, much like when somebody uses "literally" but actually means "figuratively". :-)

> In fact, what I've seen most often is that
> algorithms have complexities and problems fall into a *complexity
> class*. For example, just take a look at the Wikipedia page on time
> complexity:
>
> https://en.wikipedia.org/wiki/Time_complexity

It's a schizophrenic article. It mostly uses the standard terminology starting from this section:

https://en.wikipedia.org/wiki/Time_complexity#Constant_time

I guess the article has multiple authors, only some of which are complexity theorists.

On 12/04/2015 03:36 AM, Andrei Alexandrescu wrote:
> On 12/03/2015 09:27 PM, Timon Gehr wrote:
>> On 12/04/2015 03:19 AM, Andrei Alexandrescu wrote:
>>> On 12/03/2015 08:55 PM, Timon Gehr wrote:
>>>> I don't really understand what calling it 'complexity' actually buys
>>>> though.
>>>
>>> Instant understanding by everyone. -- Andrei
>>
>> Well, no. "running time" is actually more descriptive.
>
> http://en.cppreference.com/w/cpp/container/forward_list/insert_after
>
> Andrei

Yes, I know it is popular.

On 12/04/2015 03:35 AM, Andrei Alexandrescu wrote:
> On 12/03/2015 09:24 PM, Timon Gehr wrote:
>> On 12/04/2015 03:18 AM, Andrei Alexandrescu wrote:
>>> On 12/03/2015 08:37 PM, Jack Stouffer wrote:
>>>> On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
>>>>> These complexities must be reflected in the name of the primitives.
>>>>
>>>> I don't see why. IMO, names should convey what the function does, not
>>>> how it does it. Complexity is usually put in the function documentation
>>>> in Phobos when it's not constant, especially for range based ones, I
>>>> don't see a reason to change that.
>>>
>>> Complexity is part of the semantics, and in my design names and their
>>> semantics go hand in hand. -- Andrei
>>>
>>
>> Which is sensible. But in any given context, some parts of the semantics
>> are usually abstracted away. Sometimes one wants to abstract over
>> running times of called methods. ("This function calls this other
>> function at most O(n) times.")
>
> Sure, and there will be provision for that. The collections framework
> will contain logic such as: "If collection type C implements
> insertAfter, then implement UFCS function linearInsertAfter that
> forwards to it". So if as user you're fine with linearInsertAfter, it'll
> work as an upper bound. -- Andrei

This only works if the module imports std.container. Also, I might be okay with arbitrary running times, even super-linear. There's also the case where I want to implement a wrapper around a generic container. I will then need to provide static introspection in order to expose the methods with the correct names.

On 12/03/2015 09:52 PM, Timon Gehr wrote:
> This only works if the module imports std.container.

Yeah, that's the way it works.

> Also, I might be
> okay with arbitrary running times, even super-linear.

Hmmmm... right, no provision for that right now. Need to think about it. Maybe put them all in a "superlinear" bin.

Names are hard.

> There's also the
> case where I want to implement a wrapper around a generic container. I
> will then need to provide static introspection in order to expose the
> methods with the correct names.

Yep, again that's the way it's done.


Andrei

On 12/04/2015 03:36 AM, Andrei Alexandrescu wrote:
> On 12/03/2015 09:27 PM, Timon Gehr wrote:
>> On 12/04/2015 03:19 AM, Andrei Alexandrescu wrote:
>>> On 12/03/2015 08:55 PM, Timon Gehr wrote:
>>>> I don't really understand what calling it 'complexity' actually buys
>>>> though.
>>>
>>> Instant understanding by everyone. -- Andrei
>>
>> Well, no. "running time" is actually more descriptive.
>
> http://en.cppreference.com/w/cpp/container/forward_list/insert_after
>
> Andrei

http://www.merriam-webster.com/dictionary/literally

On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
> I know names are something we're awfully good at discussing :o). Destroy!
>
>
> Andrei

I find it ironic that this thread has moved to discuss how to name complexity/running-time...

On Friday, 4 December 2015 at 02:21:12 UTC, Andrei Alexandrescu wrote:
> On 12/03/2015 09:10 PM, Idan Arye wrote:
>> The complexities of the operations is a property of the data structure
>> being used. If each collection type will have it's own set of method
>> names based on the complexity of operations on it, we won't be able to
>> have templated functions that operate on any kind of collection(or at
>> the very least, these functions will be really tedious to code).
>
> Your premise is right but you reach the negation of the correct conclusion. -- Andrei

How so? If a singly linked list and a doubly linked list have two different method names for the same operation, then they cannot be easily templated.

On 12/3/15 10:29 PM, Jack Stouffer wrote:
> On Friday, 4 December 2015 at 02:21:12 UTC, Andrei Alexandrescu wrote:
>> On 12/03/2015 09:10 PM, Idan Arye wrote:
>>> The complexities of the operations is a property of the data structure
>>> being used. If each collection type will have it's own set of method
>>> names based on the complexity of operations on it, we won't be able to
>>> have templated functions that operate on any kind of collection(or at
>>> the very least, these functions will be really tedious to code).
>>
>> Your premise is right but you reach the negation of the correct
>> conclusion. -- Andrei
>
> How so? If a singly linked list and a doubly linked list have two
> different method names for the same operation, then they cannot be
> easily templated.

Took me a while to figure. There's a hierarchy of operations, e.g. if a collection implements insert, it automatically implements linearInsert. And so on. The collections framework provides these defaults, so client code that needs quick insert uses insert, whereas code that's fine with a linear upper bound uses linearInsert and captures both.

Another way to look at it: in STL container-independent code is near impossible because different containers use the same signature for operations that are different (either wrt iterator invalidation or complexity). My design avoids that by giving distinct operations distinct names.


Andrei