hadoop-common-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Chris Douglas (JIRA)" <j...@apache.org>
Subject [jira] Updated: (HADOOP-3308) Improve QuickSort by excluding values eq the pivot from the partition
Date Fri, 25 Apr 2008 01:19:55 GMT

     [ https://issues.apache.org/jira/browse/HADOOP-3308?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel

Chris Douglas updated HADOOP-3308:

    Attachment: 3308-2.patch

Made the class final per Nicholas's recommendation. Instead of instance vars, it should be
sufficient to make them final in the call to sort. Also added an additional test case to test
the new code more thoroughly.

> Improve QuickSort by excluding values eq the pivot from the partition
> ---------------------------------------------------------------------
>                 Key: HADOOP-3308
>                 URL: https://issues.apache.org/jira/browse/HADOOP-3308
>             Project: Hadoop Core
>          Issue Type: Improvement
>            Reporter: Chris Douglas
>            Assignee: Chris Douglas
>             Fix For: 0.18.0
>         Attachments: 3308-0.patch, 3308-1.patch, 3308-2.patch
> The current implementation of QuickSort naively partitions on either side of the pivot.
We can improve this by partitioning on either side of the set of values equal to the pivot.
This assumes that comparing keys is expensive compared to swaps and index comparisons (which
it certainly is in MapTask, and should be in general).

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

View raw message