Why Strings as Classes?

[superdan]

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?!?

> > this design is a stillborn.
> > 
> > what needs done is to allow different kinds of containers implement different interfaces. in fact a better way to factor things is via iterators, as stl has shown.
> 
> You didn't ask for an O(1) opIndex on a linked list. You asked for a 
> correct opIndex on a linked list.

the correct opIndex runs in o(1).

> Any sorting algorithm you name that 
> would work on an array would also work on this linked list. Admittedly, 
> insertion sort would be much faster than qsort, but if your library 
> provides that, you, knowing that you are using a linked list, would 
> choose the insertion sort algorithm.

no. the initial idea was for a design that allows that cool mixing and matching gig thru interfaces without knowing what is where. but ur design leads to a lot of unworkable mixing and matching.

it is a stillborn design.

> >>> how do you make a hashtable, an array, and a linked list obey the same interface? guess hashtable has stuff that others don't support?
> >> You have an interface for collections (you can add, remove, and get the 
> >> length, maybe a couple other things).
> > 
> > this is an incomplete response. what do you add for a vector!(T)? A T. what do you add for a hash!(T, U)? you tell me. and you tell me how you make that signature consistent across vector and hash.
> 
> interface List(T) : Collection!(T) {}
> 
> class Vector(T) : List!(T) {}
> 
> class HashMap(T, U) : Collection!(KeyValuePair!(T, U)) {}
> 
> Have a look at C#'s collection classes. They solved this problem.

dood. i know how the problem is solved. stl solved that before c#. my point was that making vector!(string) and hash!(int, string) offer the same interface is a tenuous proposition. 

> >> You have an interface for lists (they're collections, and you can index 
> >> them).
> > 
> > wrong. don't ever mention a linear-time indexing operator in an interview. you will fail it right then. you can always define linear-time indexing as a named function. but never masquerade it as an index operator.
> 
> If you create a linked list with O(1) indexing, that might suffice to 
> get you a PhD. If you claim that you can do so in an interview, you 
> should be required to show proof; and should you fail to do so, you will 
> probably be shown the door.
> 
> Even if you did prove it in the interview, they would probably consider 
> you overqualified, unless the company's focus was data structures.

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

> >> Then you can use all the collection-oriented stuff with lists, and you 
> >> can do special list-type things with them if you want.
> >>
> >>> these are serious questions. not in jest not rhetorical and not trick.
> >> Yes, but they're solved problems.
> > 
> > apparently not since you failed at'em.
> 
> You claimed that a problem with an inefficient solution has no solution, 
> and then you execrate me for providing an inefficient solution. Why?

because the correct answer was: a list cannot implement opIndex. it must be in a different hierarchy branch than a vector. which reveals one of the wrongs in the post i answered.

> >>>> Someone else comes along and writes a library of algorithms. The 
> >>>> algorithms can operate on any container that implements the necessary 
> >>>> operations.
> >>> hm. things are starting to screech a bit. but let's see your answers to your questions above.
> >>>
> >>>> When someone clever comes along and writes a new sorting algorithm, I 
> >>>> can plug my new container class right into it, and get the algorithm for 
> >>>> free. Likewise for the guy with the clever new collection class.
> >>> things ain't that simple.
> >> Collection-oriented library code will care sufficiently about 
> >> performance that this mix-and-match stuff is not feasible.
> > 
> > what's that supposed to mean? you sayin' stl don't exist?
> 
> No, I'm saying that for efficiency, you need to know about the internals 
> of a data structure to implement a number of collection-oriented 
> algorithms. Just like the linked list example.

wrong. you only need to define your abstract types appropriately. e.g. stl defines forward and random iterators. a forward iterators has ++ but no []. random iterator has both. so a random iterator can be substituted for a forward iterator. but not the other way. bottom line, sort won't compile on a forward iterator. your design allowed it to compile. which makes the design wrong.

> >> Almost 
> >> anything else doesn't care enough to take only an 
> >> AssociativeArrayHashSet and not a TreeSet or a LinkedList or a primitive 
> >> array.
> > 
> > wrong for the reasons above.
> 
> They expose very similar interfaces. You might care about which you 
> choose because of the efficiency of various operations, but most of your 
> code won't care which type it gets; it would still be correct.

no. you got the wrong notion of correctness.

> Well, sets have a property that no element appears in them twice, so 
> that is an algorithmic consideration sometimes.

finally a good point. true. thing is, that can't be told with types. indexing can.

> >>> saw this flick "the devil wears prada", an ok movie but one funny remark stayed with me. "you are in desperate need of chanel." 
> >>>
> >>> i'll paraphrase. "you are in desperate need of stl." you need to learn stl and then you'll figure why you can't plug a new sorting algorithm into a container. you need more guarantees. and you need iterators.
> >>>
> >>>> We don't bat an eye at the idea of containers & algorithms connecting to 
> >>>> one another using a reciprocal set of interfaces.
> >>> i do. it's completely wrong. you need iterators that broker between containers and algos. and iterators must give complexity guarantees.
> >> I don't. If I'm just going to iterate through the items of a collection, 
> >> I only care about the opApply. If I need to index stuff, I don't care if 
> >> I get a primitive array or Bob Dole's brand-new ArrayList class.
> > 
> > you too are in desperate need for stl.
> 
> You are in desperate need of System.Collections.Generic. Or 
> tango.util.container.

guess my advice fell on deaf ears eh.

btw my respect for tango improved when i found no opIndex in their list container.