Why Strings as Classes?

[superdan]

Dee Girl Wrote:

> Michiel Helvensteijn Wrote:
> 
> > Dee Girl wrote:
> > 
> > >> 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.
> > 
> > Yes, the first 'trick' makes it a different datastructure. The second does
> > not. Would you still be opposed to using opIndex if its time-complexity is
> > O(log n)?
> 
> This is different question. And tricks are not answer for problem. Problem is list has other access method than array.  
> 
> > >> 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.
> > 
> > With that second trick the loop would have the same complexity for lists.
> 
> Not for singly linked lists. I think name "trick" is very good. It is trick like prank to a friend. It does not do real thing. It only fools for few cases.

guess i'll risk telling which. forward iteration. backward iteration. accessing first k. accessing last k. that's pretty much it. and first/last k are already available in standard list. all else is linear time. so forget about using that as an index table. a naive design at best.

> > But putting that aside for the moment, are you saying you would allow
> > yourself to be deceived by a syntax detail? No, mentally attaching O(1) to
> > the *subscripting operator* is simply a legacy from C, where it is
> > syntactic sugar for pointer arithmetic.
> 
> I do not think so. I am sorry. If a[n] is not allowed then other array access primitive is allowed. Give index(a, n) as example. If language say index(a, n) is array access then it is big mistake for list to also define index(a, n). List maybe should define findAt(a, n). Then array also can define findAt(a, n). It is not mistake.

boils down to what's primitive access vs. what's actual algorithm. indexing in array is primitive. indexing in list is same algorithm as finding nth element anywhere - singly, doubly, file, you name it. so can't claim indexing is primitive for 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().
> > 
> > Of course not. Find should be written with an iterator, which has optimal
> > complexity for both data-structures. My point is that an algorithm should
> > be generic first and foremost. Then you use the operations that have the
> > lowest complexity over all targeted data-structures if possible.
> 
> Maybe I think "generic" word different than you. For me generic is that algorithm asks minimum from structure to do its work. For example find ask only one forward pass. Input iterator does one forward pass. It is mistake if find ask for index. It is also mistake if structure makes an algorithm think it has index as primitive operation.
> 
> > >> >> * 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.
> > 
> > Lists allocate memory for bare nodes, but never have to copy their elements.
> > Arrays have to move their whole content to a larger memory location each
> > time they are outgrown. For more complex data-types that means potentially
> > very expensive copies.
> 
> I think this is mistake. I think you should google "amortized complexity". Maybe that can help much.

to expand: array append is o(1) averaged over many appends if you double the capacity each time you need. interesting if you only add k complexity jumps to quadratic.

> > >> 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 did say 'if'. You have to agree that if you disregard complexity issues
> > (for the sake of argument), the two ARE equivalent.
> 
> But it is useless comparison. Comparison can not forget important aspect. If we ignore fractionary floating point is integer. If organism is not alive it is mostly water.

pwned if u ask me :D