Consider the collections universe. So we have an imperative primitive like:

c.insertAfter(r, x)

where c is a collection, r is a range previously extracted from c, and x is a value convertible to collection's element type. The expression imperatively inserts x in the collection right after r.

Now this primitive may have three complexities:

* linear in the length of r (e.g. c is a singly-linked list)

* linear in the number of elements after r in the collection (e.g. c is an array)

* constant (c is a doubly-linked list)

These complexities must be reflected in the name of the primitives. Or perhaps it's okay to conflate a couple of them. I know names are something we're awfully good at discussing :o). Destroy!


Andrei

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.

On 12/04/2015 02:27 AM, Andrei Alexandrescu wrote:
> Consider the collections universe. So we have an imperative primitive like:
>
> c.insertAfter(r, x)
>
> where c is a collection, r is a range previously extracted from c, and x
> is a value convertible to collection's element type. The expression
> imperatively inserts x in the collection right after r.
>
> Now this primitive may have three complexities:
>
> * linear in the length of r (e.g. c is a singly-linked list)
>
> * linear in the number of elements after r in the collection (e.g. c is
> an array)
>
> * constant (c is a doubly-linked list)
>
> These complexities must be reflected in the name of the primitives. Or
> perhaps it's okay to conflate a couple of them. I know names are
> something we're awfully good at discussing :o). Destroy!
>
>
> Andrei

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.

On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
> Consider the collections universe. So we have an imperative primitive like:
>
> c.insertAfter(r, x)
>
> where c is a collection, r is a range previously extracted from c, and x is a value convertible to collection's element type. The expression imperatively inserts x in the collection right after r.
>
> Now this primitive may have three complexities:
>
> * linear in the length of r (e.g. c is a singly-linked list)
>
> * linear in the number of elements after r in the collection (e.g. c is an array)
>
> * constant (c is a doubly-linked list)
>
> These complexities must be reflected in the name of the primitives. Or perhaps it's okay to conflate a couple of them. I know names are something we're awfully good at discussing :o). Destroy!
>
>
> Andrei

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

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

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

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

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.")

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.

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