Why Strings as Classes?

[Steven Schveighoffer]

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

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)

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

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.

-Steve