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
Why not create the capability to get the complexity by the user:
writeln(c.insertAfter(r, null).complexity);
If all algorithms implemented such a feature, one could have a
compile time argument to display the complexity of the algorithms
along with profiling.
Complexity is not important except when profiling. It's also
generally static depending on the types rather than the values of
the types.
