Why Strings as Classes?

[superdan]

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.

>  Anything that is not exponential 
> is usually considered P-complete, meaning it can be solved in polynomial 
> time.  The unsolvable problems are NP-complete, i.e. non-polynomial.  Non 
> polynomial usually means n is in one of the exponents, e.g.:
> 
> O(2^n).

sure thing.

> That being said, it doesn't take a genius to figure out that a standard 
> sorting algorithm on a linked list while trying to use random access is 
> going to run longer than the same sorting algorithm on a random-access list. 
> But there are ways around this.  For instance, you can sort a linked list in 
> O(n log n) time with (in pseudocode):
> 
> vector v = list; // copy all elements to v, O(n)
> v.sort; // O(n lgn)
> list.replaceAll(v); // O(n)

sure thing. problem is, you must know it's a list. otherwise you wouldn't make a copy. 

don't forget how this all started when answering tiny bits of my post. it started with a dood claiming vector and list both have opIndex and then sort works with both without knowing the details. it don't work with both.

> So the total is O(2n + n lgn), and we all know you always take the most 
> significant part of the polynomial, so it then becomes:
> 
> O(n lgn)
> 
> Can I have my PhD now? :P

sure. i must have seen an email with an offer somewhere ;)

> In all seriousness though, with the way you can call functions with arrays 
> as the first argument like member functions, it almost seems like they are 
> already classes.  One thing I have against having a string class be the 
> default, is that you can use substring on a string in D without any heap 
> allocation, and it is super-fast.  And I think substring (slicing) is one of 
> the best features that D has.
> 
> FWIW, you can have both a string class and an array representing a string, 
> and you can define the string class to use an array as it's backing storage. 
> I do this in dcollections (ArrayList).  If you want the interface, wrap the 
> array, if you want the speed of an array, it is accessible as a member. 
> This allows you to decide whichever one you want to use.  You can even use 
> algorithms on the array like sort by using the member because you are 
> accessing the actual storage of the ArrayList.

that sounds better.