Complexity nomenclature

[ZombineDev via Digitalmars-d]

On Friday, 4 December 2015 at 06:05:55 UTC, Tofu Ninja wrote:
> On Friday, 4 December 2015 at 03:37:10 UTC, Andrei Alexandrescu 
> wrote:
>> 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
>
> This sounds really complicated to use? What are the benefits?
> When would a generic algorithm even need to know the complexity 
> of the container?
>
> 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.

Ranges are a good example - they provide only the operations thay 
can efficiently implement. For example forward ranges could 
provide random access but at the cost of linear running time.

std.containers provides the `elem in container` operation only if 
they can implement it in logarithmic time or faster.

The fact that you can't use opIn for DList or Array is very good, 
because it prevents you from writing inefficient genric code. 
You're algorithm will manifest that it can only work with 
containers provide efficient operations and because of that you 
can be sure what its time complexity would be.

You should choose a specific data structure only because you can 
efficiently implement the algorithm you have in mind with it.

One of worst examples of the opposite is .Count extention method 
in .NET (which happens to have the same name as .Count member 
function of ICollection - one of the most used (often implicitly) 
interfaces), which has linear running time. The most horrible 
thing I have seen!