Why Strings as Classes?

[Michiel Helvensteijn]

superdan wrote:

>> 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).
> 
> it oughtn't. & you digress in the wrong direction. you can't prove a
> majority of "practical cases" will not suffer a performance hit.

Perhaps. It's been a while since I've worked with data-structures on this
level, but I seem to remember there are ways.

What if you maintain a linked list of small arrays? Say each node in the
list contains around log(n) of the elements in the entire list. Wouldn't
that bring random access down to O(log n)? Of course, this would also bring
insertions up to O(log n).

And what if you save an index/pointer pair after each access. Then with each
new access request, you can choose from three locations to start walking:
* The start of the list.
* The end of the list.
* The last access-point of the list.

In a lot of practical cases a new access is close to the last access. Of
course, the general case would still be O(n).

>> That, in turn, means that a linked list and a dynamic array can not share
>> a common interface that includes opIndex.
> 
> so what. they can share a common interface that includes nth(). what
> exactly is yer problem with that.

That's simple. a[i] looks much nicer than a.nth(i).

By the way, I suspect that if opIndex is available only on arrays and nth()
is available on all sequence types, algorithm writers will forget about
opIndex and use nth(), to make their algorithm more widely compatible. And
I wouldn't blame them, though I guess you would.

>> * A list has faster insertions and growth.
> 
> o(1) insertion if u have the insertion point.  both list and vector have
> o(1) growth.

Yeah, but dynamic arrays have to re-allocate once in a while. Lists don't.

> we get to the point where we realize the two r fundamentally different
> structures built around fundamentally different tradeoffs. they do satisfy
> the same interface. just ain't the vector interface. it's a
> sequential-access interface. not a random-access interface.

I believe we agree in principle, but are just confused about each others
definitions. If the "random-access interface" guarantees O(1) for
nth/opIndex/whatever, of course you are right.

But if time-complexity is not taken into consideration, the
sequential-access interface and the random-access interface are equivalent,
no?

I'm not opposed to complexity guarantees in public contracts. Far from it,
in fact. Just introduce both interfaces and let the algorithm writers
choose which one to accept. But give both interfaces opIndex, since it's
just good syntax.

I do think it's a good idea for algorithms to support the interface with the
weakest constraints (sequential-access). As long as they specify their
time-complexity in terms of the complexities of the interface operations,
not in absolute terms.

Then, when a programmer writes 'somealgorithm(someinterfaceobject)', a
hypothetical analysis tool could tell him the time-complexity of the the
resulting operation. The programmer might even assert a worst-case
complexity at that point and the compiler could bail out if it doesn't
match.

> even if u don't use c++ for its many faults. understand stl coz it's d
> shiznit.

I use C++. I use STL. I love both. But that doesn't mean there is no room
for improvement. The STL is quite complex, and maybe it doesn't have to be.

-- 
Michiel