|
|
Back to UserFriendly Strip Comments Index
|
recursive -> iterative | by dennismv | 2004-12-21 02:24:43 |
|
I don't have time to give a full answer... | by Liava | 2004-12-21 03:55:22 |
|
Qsort | by dennismv | 2004-12-21 04:15:00 |
|
I'd still call that a recursive solution, though | by Liava | 2004-12-21 04:30:46 |
|
recursion | by dennismv | 2004-12-21 04:50:19 |
|
Well, the algorithm is as follows: | by Liava | 2004-12-21 11:46:07 |
|
ok | by dennismv | 2004-12-21 19:34:10 |
|
Not what I meant | by Liava | 2004-12-21 22:05:31 |
| Much of this could be avoided. |
by williamashbless |
2004-12-21 23:32:22 |
1) You don't need to use the heap. You could use a statically allocated array of sufficient size, or several arrays if you need to store multiple types of data, or arrays of structures if you prefer, any will do.
By doing it this way, you don't save yourself space on the program stack, because that's where local variables get stuffed, just like when you're using recursion. But you will save yourself the overhead in performing a function call.
The downside is that you have to be very sure that the deepest level of recursion won't exceed the bounds of the array.
But you need to do that anyway with recursion -- runaway or excessive recursion can still blow your stack. So you're no worse or better off. Having a massive stack won't solve your speed problem. You just, as I said, save on the function call overhead.
However, the overhead _is_ minimal, typically, so you have to be very _very_ careful how you code your iterative version, otherwise you will chew up any benefit of jumping through these hoops.
2) Even if you want to use a 'stack' that is larger than the typical function call stack, you can allocate it from the heap as a single array (using the new array syntax), and use that instead of a local array. This gets around the size limitation on local arrays imposed by a very small program stack. The downside is that it's still fixed in size up front.
3) There's all sorts of ways to avoid having to do a 'new' heap allocation for every individual item to avoid the overhead of heap allocation.
Heap allocation (with new or malloc) is slow. Do it minimally, if performance is an issue. Also, you have to clean up anything you allocate from the heap, or you have a memory leak. Preferably do it not at all, or just once, for something like this.
---
But this really, as mentioned before, doesn't solve your problem. Making a massive stack won't make your program faster. Using it efficiently will.
First, if your quicksort stands a good chance of hitting the 'degenerate' case where it always choses a 'pivot' that ends up consistently off to one side, then you'll end up with bad levels of recursion (proportional to the number of items being sorted!). This will blow your stack with a sufficiently large array.
The degenerate case also causes the slowest sort, being time proportional to the SQUARE of the number of items. This, beyond anything else you could possibly do, will affect the speed the most.
But I'm sure you know all that.
Efficient use of whatever stack you have involves:
1) not doing a heap allocation for each level of recursion, if at all possible. (Create a fixed size stack of your own, and pushes become nothing more than assignment to successive portions of the array via an incremented counter. Pops become the subtraction of a counter. Very cheap.)
2) Pushing the least amount of data on to the stack possible.
3) If the very very last thing in the recursive function is to make a recursive call, then technically you don't need that recursion in the first place. This is true even if you don't make your program fully iterative. If you wrap your function's guts in a loop, and allow the tail 'recursion' function call parameters to be used back at the top of the loop, the tail recursion goes away. You don't need to push it, or pop it, from the stack.
3a) If you eliminate a tail recursion via a loop, eliminate it for the one with the largest subproblem. The smaller subproblem should be the one made recursive, because there's less chance of having a bad degenerate case that blows your stack.
Quicksort is nice because it exhibits properties 3, and 3a. It's tail recursive. You can get rid of one recursive call _even_ _if_ you leave the other one in.
|
|
[ Reply ] |
|
|
[Todays Cartoon Discussion]
[News Index]
|
|
