Why Strings as Classes?

[Dee Girl]

Michiel Helvensteijn Wrote:

> 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.

I write example with findLast a little time a go. But there are many examples. For example move to front algorithm. It is linear but with "trick" opIndex it is O(n*n) even with optimization. Bad!

> 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).

Michiel-san, this is new data structure very different from list! If I want list I never use this structure. It is like joking. Because when you write this you agree that list is not vector.

> >> 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).

It is not nicer. It is more deceiving (correct spell?). If you look at code it looks like array code.

foreach (i; 0 .. a.length)
{
    a[i] += 1;
}

For array works nice. But for list it is terrible! Many operations for incrementing only small list.

> 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.

I do not agree with this. I am sorry! I think nobody should write find() that uses nth().

> >> * 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.

Lists allocate memory each insert. Array allocate memory some time. With doubling cost of allocation+copy converge to zero. 

> > 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 think it is mistake to not taken into consideration time complexity. For basic data structures specially. I do not think you can call them equivalent.

> 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 think is convenient syntax. Maybe too convenient ^_^.

> 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.

The specification I think is with types. If that works tool is the compiler.

> > 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.

Many things in STL can be better with D. But iterators and complexity is beautiful in STL.