In the mists of memory I recall hearing of such exploits. Sorry, I have
no reference.
I don't have a tacit tail-recursion for quicksort, but an explicit one
would look like
qsort =: 3 : 0
region =. 0 , <: #y NB. The region being sorted here
while. there is data do.
choose pivot;
NB. partition (sortregion =. region ;.0 y) so that indexes in
NB. ({. region to <: ppoint) are before (ppoint to {: region)
'y ppoint' =. partition y
NB. get start/end points of partition
intervals =. 1 0 1 #^:_1!.ppoint region
NB. Get the index of the smaller region
recursionindex =. >/ 2 -~/\ intervals
NB. recur to sort the smaller interval
y =. (qsort on the smaller interval) (smaller interval)} y
NB. loop back to process the larger interval (tail recursion)
region =. recursionindex { 2 ]\ intervals
end.
)
Untested!
The idea is, sort in-place, and recur only on the smaller partition,
leaving a change of 'region' to control which part of the array you are
sorting in the loop. The loop sorts the larger partition, the recursion
the smaller, and since you recur only for the smaller partition you are
guaranteed stack depth of no more than lg(n).
Not that this solves all problems! You still have an algorithm that
runs in O(n^2) time in the worst case, even though it won't overrun the
stack. If the Evil People send you a malformed array, you won't crash,
but you will go silent for a very long time.
The best practice to avoid this is, I think, a hybrid that runs
quicksort until the stack depth exceeds some large value, and then
switches over to heapsort (which has guaranteed performance, though a
bit slower than quicksort) to avoid pathological cases.
Me, I don't see Evil People, so I just use /:~ .
Henry Rich
On 8/28/2014 9:27 PM, Thomas Costigliola wrote:
Henry, out of sheer curiosity, if you have a story of such evil follies I
would be delighted to hear it. More seriously, do you have a tacit tail
recursive verb for quicksort to share ? This is related to this post
http://www.jsoftware.com/pipermail/programming/2014-August/039023.html
On Thu, Aug 28, 2014 at 9:18 PM, Henry Rich <[email protected]> wrote:
On the contrary, stack depth is a killer for quicksort. In the worst
case, the stack depth is the number of items, as each partitioning gives a
partition of just one element. Tail recursion solves this problem.
Not likely, you say? If your code is deployed somewhere important, Evil
People will send it an array that will produce a worst case.
Perhaps you can use a random pivot... as long as the Evil People can't
guess your sequence.
Henry Rich
On 8/28/2014 9:13 PM, Raul Miller wrote:
I guess I'd like to see your code to better understand how you are
thinking.
You might have a good point. You might be overlooking something. But I do
not know yet.
(This sounds fun, but stack depth is unlikely to be a problem for
quicksort. Also, quicksort is often overkill and /:~ or bare /: are also
worth considering.)
Thanks,
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
