Why Strings as Classes?

[Chris R. Miller]

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.

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

Wrong.  It works.  That it's not precisely what the spec for sort
dictates (which is probably in error, since no spec can guarantee a
precise efficiency if it doesn't know the precise container type).  You
are also misinterpreting the spec.  It is saying that it uses a specific
efficiency of algorithm, not that you can arbitrarily expect a certain
efficiency out of it regardless of how dumb you might be with the choice
of container you use.

>> 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 ;)

A Ph.D from superdan... gee, I'd value that just above my MSDN
membership.  Remember: I value nothing less than my MSDN membership.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 258 bytes
Desc: OpenPGP digital signature
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20080826/cab19c25/attachment.pgp>