[
https://issues.apache.org/jira/browse/HADOOP-3442?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12601762#action_12601762
]
chris.douglas edited comment on HADOOP-3442 at 6/2/08 2:12 PM:
---------------------------------------------------------------
Alternatively, we could just effect the tail recursion with a loop (see
attached; credit to Nicholas for the idea). I'm not wild about creating new
java.util.Stack instances, but it's not likely to be a performance issue either
way. As for switching to heapsort from insertion sort for < K or log\(n)
values, though I'd be surprised to learn that was a bottleneck, it sounds like
a cool idea to try.
The recursion itself doesn't seem to be the problem, though; that there's a
case where it becomes unbounded is. This is showing up often enough that there
is likely a framework problem, but nobody has explained how they reproduce it,
yet.
was (Author: chris.douglas):
Alternatively, we could just effect the tail recursion with a loop (see
attached; credit to Nicholas for the idea). I'm not wild about creating new
java.util.Stack instances, but it's not likely to be a performance issue either
way. As for switching to heapsort from insertion sort for < K/log\(n) values,
though I'd be surprised to learn that was a bottleneck, it sounds like a cool
idea to try.
The recursion itself doesn't seem to be the problem, though; that there's a
case where it becomes unbounded is. This is showing up often enough that there
is likely a framework problem, but nobody has explained how they reproduce it,
yet.
> QuickSort may get into unbounded recursion
> ------------------------------------------
>
> Key: HADOOP-3442
> URL: https://issues.apache.org/jira/browse/HADOOP-3442
> Project: Hadoop Core
> Issue Type: Bug
> Components: mapred
> Affects Versions: 0.17.0
> Reporter: Runping Qi
> Assignee: Chris Douglas
> Attachments: 3442-0.patch, HADOOP-3442.patch
>
>
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
