Re: Recursive functions and stack overload
Re: Recursive functions and stack overload
- Subject: Re: Recursive functions and stack overload
- From: Günther Blaschek <email@hidden>
- Date: Sat, 29 Apr 2006 14:50:23 +0200
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.
Nicko van Someren replied:
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.
You can get guarantee a log2(n) recursion depth quite easily. At the
end of each recursion, "regular" quicksort implementations
recursively sort two subarrays at the beginning and end of the array,
like this:
quicksort(..., m, j); // the first j-m+1 elements
quicksort(..., i, n); // the last n-i+1 elements
Just check which of these parts is shorter, and start another
recursion only for this part. Then adjust the parameters and jump to
the beginning to sort the other part (within the same recursion
depth). In this way, the length of the part to sort will always be
halved (at least) in the next level.
Note that this simple trick solves the stack overflow problem, but
quicksort will still have order O(n^2) in the worst case.
Attachment:
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________
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