Re: Recursive functions and stack overload
Re: Recursive functions and stack overload
- Subject: Re: Recursive functions and stack overload
- From: Nicko van Someren <email@hidden>
- Date: Thu, 27 Apr 2006 11:38:07 +0100
On 27 Apr 2006, at 10:58, Paolo Bertani wrote:
My problem is not actually the quicksort algorithm itself but the
behaviour of the runtime in a single threaded application when the
stack size grows up due to a recursive function calling itself
around 100,000 times.
If the heap automatically and dinamically grows as more space is
needed (as Dado Colussi says) then I'm out of troubles.
It's true that if the stack grew automatically then it helps, but if
you're recusing 100,000 then you've got other problems, not least
that your sort has descended into taking O(n^2) time. For twice the
memory and twice the best-case amount of data copying compared to
Quicksort you could switch to a merge sort, which always has order
n.log2(n) execution time and will never recurse more than log2(n) times.
Sorry, this is sliding rapidly off the topic of the Cocoa runtime and
into theoretical CompSci. I suggest that if you are running out of
stack in your program then you should first and foremost look at what
your program is doing before trying to mess with the runtime system.
You're not the first person to want to sort 100,000 items in a Cocoa
application and this should not be causing you problems. Excessively
deep recursion is usually a problem with the application and I
suggest that you start by trying to fix that.
Nicko
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden