Why Strings as Classes?

Michiel Helvensteijn nomail at please.com
Wed Aug 27 04:28:54 PDT 2008


superdan wrote:

> my point was opIndex should not be written for a list to begin with.

Ok. So you are not opposed to the random access operation on a list, as long
as it doesn't use opIndex but a named function, correct?

You are saying that there is a rule somewhere (either written or unwritten)
that guarantees a time-complexity of O(1) for opIndex, wherever it appears.

This of course means that a linked list cannot define opIndex, since a
random access operation on it will take O(n) (there are tricks that can
make it faster in most practical cases, but I digress).

That, in turn, means that a linked list and a dynamic array can not share a
common interface that includes opIndex.

Aren't you making things difficult for yourself with this rule?

A list and an array are very similar data-structures and it is natural for
them to share a common interface. The main differences are:
* A list takes more memory.
* A list has slower random access.
* A list has faster insertions and growth.

But the interface shouldn't necessarily make any complexity guarantees. The
implementations should. And any programmer worth his salt will be able to
use this wisely and choose the right sorting algorithm for the right
data-structure. There are other algorithms, I'm sure, that work equally
well on either. Of course, any algorithm should give its time-complexity in
terms of the complexity of the operations it uses.

I do understand your point, however. And I believe my argument would be
stronger if there were some sort of automatic complexity analysis tool.
This could either warn a programmer in case he makes the wrong choice, or
even take the choice out of the programmers hands and automatically choose
the right sorting algorithm for the job. That's a bit ambitious. I guess a
profiler is the next best thing.

-- 
Michiel




More information about the Digitalmars-d mailing list