> > I have no idea why after all these years people still think
> > reference counting is a good idea. It's so trivial to find an
> > example where it utterly fails...
> 
>   Care to give this trivial example?

See the entry 'Moon instructs a student' in:

http://www.catb.org/jargon/html/koans.html


To answer Andy's question, though:

I have no idea why after all these years people still think quicksort is
a good idea. It's so trivial to find an example where it takes O(n^2)
time.

-- 
In LaTeX, you \begin{document}.  In Soviet Russia, document \begin{you}!
http://surreal.istic.org/      Carry me home, my teacher, carry me home.

Post a reply to this message

>> And I'm not sure how you would do a whole bunch of simple things 
>> *without* such objects.
> 
>   Exactly like hundreds of programming languages do.

OK, well how would you build (say) a linked list structure if the new 
node goes out of scope as soon as you get to the end of the function 
that creates it and adds it to the list?

>> I have no idea why after all these years people still think reference 
>> counting is a good idea. It's so trivial to find an example where it 
>> utterly fails...
> 
>   Care to give this trivial example?

OK, how about a double-linked list?

Every node (except the end ones) always has 2 other nodes pointing to 
it. Hence the reference count will never reach zero. QED.

Post a reply to this message

Orchid XP v3 <voi### [at] devnull> wrote:
> OK, well how would you build (say) a linked list structure if the new 
> node goes out of scope as soon as you get to the end of the function 
> that creates it and adds it to the list?

  It goes out of scope, but it has two references pointing to it
(one in the function and another in the list data structure). When
it goes out of scope in the function that simply decreases the
reference count by one.

> OK, how about a double-linked list?

> Every node (except the end ones) always has 2 other nodes pointing to 
> it. Hence the reference count will never reach zero. QED.

  The nodes at the ends of the list have only one.

-- 
                                                          - Warp

Post a reply to this message

Daniel Hulme <pho### [at] isticorg> wrote:
> I have no idea why after all these years people still think quicksort is
> a good idea. It's so trivial to find an example where it takes O(n^2)
> time.

  It's certainly not very trivial to find such an example of the choice
of pivot in the paritioning is smart. Simply making a median-of-3 pivot
choice makes finding such an example non-trivial. Moreover, if the
middle item of the median choice is taken with some randomization to it,
good luck finding a patological example.

  Moreover, quicksort is handy because it can easily be enhanced to
sort small partitions with insertion sort, making it noticeably faster.
(Heapsort, for instance, cannot be enhanced like this. Mergesort can be,
but the problem with mergesort is its additional memory requirements,
at least when sorting arrays.)

  Oh, but of course there's the array where every value is the same.
It's rather trivial to stop partitioning when no swaps were made.

  Sure, it's still possible for a pathological case to happen, but
finding one is not trivial.

-- 
                                                          - Warp

Post a reply to this message

> Daniel Hulme <pho### [at] isticorg> wrote:
> > I have no idea why after all these years people still think
> > quicksort is a good idea. It's so trivial to find an example where
> > it takes O(n^2) time.
> 
>   It's certainly not very trivial to find such an example of the
> choice of pivot in the paritioning is smart.

Thank you for illustrating my point :->

-- 
"Oh, Eeyore, you are wet!" said Piglet, feeling him.
Eeyore shook himself,  and asked somebody to explain to Piglet what hap-
pened when you had been inside a river for a long time.
    A. A. Milne, 'The House at Pooh Corner'    http://surreal.istic.org/

Post a reply to this message

Daniel Hulme <pho### [at] isticorg> wrote:
> > Daniel Hulme <pho### [at] isticorg> wrote:
> > > I have no idea why after all these years people still think
> > > quicksort is a good idea. It's so trivial to find an example where
> > > it takes O(n^2) time.
> > 
> >   It's certainly not very trivial to find such an example of the
> > choice of pivot in the paritioning is smart.

> Thank you for illustrating my point :->

  Your point? You said it's trivial to find such an example, and I said
it isn't. How does that illustrate your point? Unless you were being
sarcastic or something.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>>Every node (except the end ones) always has 2 other nodes pointing to 
>>it. Hence the reference count will never reach zero. QED.

>   The nodes at the ends of the list have only one.

Not necessarily. They're pointed to by the object that represents the 
list as a whole. What pointer would you drop to make the list 
garbage-collect with a reference-count GC?

If you have a "file" that points to its buffer, and its buffer points to 
its file, you have a loop. If you have a declaration object that points 
to the definition object and the definition object points to the 
declaration object, you have a loop. If the window instance points to 
the screen instance and the screen instance points to the window 
instance, you have a loop. If the treenode points to its children and 
the children point back up to the parent, you have a loop.

Plus, reference counting has very bad performance as well as being 
non-real-time and uninterruptable.

None of which has much to do with POV-Ray as such. ;-)

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message

>>>> I have no idea why after all these years people still think
>>>> quicksort is a good idea. It's so trivial to find an example where
>>>> it takes O(n^2) time.
>>>   It's certainly not very trivial to find such an example of the
>>> choice of pivot in the paritioning is smart.
> 
>> Thank you for illustrating my point :->
> 
>   Your point? You said it's trivial to find such an example, and I said
> it isn't. How does that illustrate your point? Unless you were being
> sarcastic or something.

I think he's hinting that finding the right pivot is the "hard" part of 
the algorithm, and if you get that wrong you get poor performance...

Post a reply to this message

Orchid XP v3 <voi### [at] devnull> wrote:
> I think he's hinting that finding the right pivot is the "hard" part of 
> the algorithm, and if you get that wrong you get poor performance...

  But that doesn't make quicksort a bad sorting algorithm.

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Not necessarily. They're pointed to by the object that represents the 
> list as a whole. What pointer would you drop to make the list 
> garbage-collect with a reference-count GC?

  How do languages where there no concept of "new" (as in Java or C++)
nor a Java-style GC of dynamically allocated objects do it?

> Plus, reference counting has very bad performance as well as being 
> non-real-time and uninterruptable.

  Very bad performance? I think that incrementing/decrementing a counter
each time an object is copied doesn't increase too much of its slowness.
(Naturally in situations where you have to locally copy things a lot
you would not use dynamically allocated copies anyways, assuming the
language supports local instances.)

-- 
                                                          - Warp

Post a reply to this message