Why Strings as Classes?

[Dee Girl]

Chris R. Miller Wrote:

> superdan wrote:
> > Steven Schveighoffer Wrote:
> > 
> >> "superdan" wrote
> >>> Christopher Wright Wrote:
> >>>
> >>>> superdan wrote:
> >>>>>> class LinkedList(T)
> >>>>>> {
> >>>>>> Node!(T) head;
> >>>>>>
> >>>>>> /** Gets the ith item of the list. Throws: SIGSEGV if i >= length of
> >>>>>> the list. Time complexity: O(N) for a list of length N. This operation
> >>>>>> is provided for completeness and not recommended for frequent use in
> >>>>>> large lists. */
> >>>>>> T opIndex(int i)
> >>>>>> {
> >>>>>> auto current = head;
> >>>>>> while (i)
> >>>>>> {
> >>>>>> current = current.next;
> >>>>>> }
> >>>>>> return current.value;
> >>>>>> }
> >>>>>> }
> >>>>> oopsies. houston we got a problem here. problem is all that pluggable 
> >>>>> sort business works only if it can count on a constant time opIndex. 
> >>>>> why? because sort has right in its spec that it takes o(n log n) time. 
> >>>>> if u pass LinkedList to it you obtain a nonsensical design that 
> >>>>> compiles but runs afoul of the spec. because with that opIndex sort 
> >>>>> will run in quadratic time and no amount of commentin' is gonna save it 
> >>>>> from that.
> >>>> WRONG!
> >>>> Those sorting algorithms are correct. Their runtime is now O(n^2 log n)
> >>>> for this linked list.
> >>> you got the wrong definition of correct. sort became a non-scalable algo 
> >>> from a scalable algo. whacha gonna say next. bubble sort is viable?!?
> >> O(n^2 log n) is still considered solved.
> > 
> > of course. for traveling salesman that is. just not sorting. o(n^2 log n) sorting algo, that's  a no-go. notice also i didn't say solved/unsolved. i said scalable. stuff beyond n log n don't scale.
> 
> Why are people unable to have the brains to understand that they're
> using data structures in an suboptimal nature?
> 
> Furthermore, you're faulting linked lists as having a bad opIndex.  Why
> not implement a cursor (Java LinkedList-like iterator) in the opIndex
> function?  Thus you could retain the reference to the last indexed
> location, and simply use that instead of the root node when calling
> opIndex.  Granted that whenever the contents of the list are modified
> that reference would have to be considered invalid (start from the root
> node again), but it'd work with an O(1) efficiency for sequential
> accesses from 0 to length.  True, it'll add another pointer to a node in
> memory, as well as a integer representing the position of that node
> reference.

I am sorry to enter discussion. But I have some thing to say. Please do not scare me ^_^.

I think Super Dan choose wrong example sort. Because sort is O(n log n) even for list. But good example is find. Taken collection that gives length and opIndex abstraction. Then I write find easy with index. It is slow O(n*n) for list. But with optimization from Chris it is fast again. But if I want to write findLast. Find last element equal to some thing. Then I go back. But going back the optimization never works. I am again to O(n*n)!

This is important because abstraction. You want to write find abstract. Also you want write container abstract. And you want both to work together well. If you choose algorithm manually "you cheat". You break abstraction. Because you want abstract algorithm work on abstract container. Not concrete algorithm on concrete container.

Also is not only detail. When call findLast on container I expect better or worse depending on optimization of library. But I expect proportional with number of elements. If I know is O(n*n) maybe I want redesign. O(n*n) is really bad. 1000 elements is not many. But 1000000 operations is many.

I took two data structures classes. What each structure gives fast is essential. Not detail. I am not sure is clear what I say. Structures are special for certain operations. For example there is suffix tree. It is for fast common substring. Suffix tree must not have same interface as O(n*n) search. Because algorithm should not accept both. If you say list has random access it is naive I think (sorry!). Everybody in class could laugh. To find index in list is linear search. A similar example an array string[] can define overload a["abc"] to do linear search for "abc". But search is not indexing. It must be name search find or linearSearch.