On 12/03/2015 10:46 PM, Walter Bright wrote:
On 12/3/2015 5:27 PM, Andrei Alexandrescu wrote:
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!
Are you sure there are only 3 complexities? What if it's a
self-balancing tree?
I'm also not sure it is a good idea to put the complexity in the name of
the primitive. Do any other algorithm libraries do that?
Looks exaggerated, innit? The fact of the matter is people choose
collections based on the complexity of their operations all the time. "I
need to insert and remove at the front, so I'll use a list here." Or: "I
need random access, I'll use a vector" etc.
Not designing nomenclature for complexity leads to the usual design
disasters such as providing a list with the same indexing operator as an
array.
Turning that on its head, if we want to allow people to design
collection-independent code and mix and match collections based only on
their APIs, those APIs must reflect the complexity of operations.
Collection-independent code is big in my design btw.
One idea is to have the very name reflect the operation. I'm thinking
"insert" to mean "scoot over elements at the tail and insert the new
element in the gap" and "link" to mean "create a new node and link it
within this collection without scooting over anything". Then the
relative costs will be implied.
Another idea is to only classify operations as "quick" (expected O(1) up
to O(log n)) and "not quick" (everything worse). Then we only have two
categories, and "quick" will be in the name of the respective methods.
Andrei
