Author: cdouglas
Date: Fri Apr 25 16:06:56 2008
New Revision: 651735
URL: http://svn.apache.org/viewvc?rev=651735&view=rev
Log:
HADOOP-3308. Improve QuickSort by excluding values eq the pivot from the
partition.
Modified:
hadoop/core/trunk/CHANGES.txt
hadoop/core/trunk/src/java/org/apache/hadoop/util/QuickSort.java
hadoop/core/trunk/src/test/org/apache/hadoop/util/TestIndexedSort.java
Modified: hadoop/core/trunk/CHANGES.txt
URL:
http://svn.apache.org/viewvc/hadoop/core/trunk/CHANGES.txt?rev=651735&r1=651734&r2=651735&view=diff
==============================================================================
--- hadoop/core/trunk/CHANGES.txt (original)
+++ hadoop/core/trunk/CHANGES.txt Fri Apr 25 16:06:56 2008
@@ -46,6 +46,9 @@
HADOOP-3295. Allow TextOutputFormat to use configurable spearators.
(Zheng Shao via cdouglas).
+ HADOOP-3308. Improve QuickSort by excluding values eq the pivot from the
+ partition. (cdouglas)
+
OPTIMIZATIONS
HADOOP-3274. The default constructor of BytesWritable creates empty
Modified: hadoop/core/trunk/src/java/org/apache/hadoop/util/QuickSort.java
URL:
http://svn.apache.org/viewvc/hadoop/core/trunk/src/java/org/apache/hadoop/util/QuickSort.java?rev=651735&r1=651734&r2=651735&view=diff
==============================================================================
--- hadoop/core/trunk/src/java/org/apache/hadoop/util/QuickSort.java (original)
+++ hadoop/core/trunk/src/java/org/apache/hadoop/util/QuickSort.java Fri Apr 25
16:06:56 2008
@@ -21,7 +21,7 @@
* An implementation of the core algorithm of QuickSort.
* See "Median-of-Three Partitioning" in Sedgewick book.
*/
-public class QuickSort implements IndexedSorter {
+public final class QuickSort implements IndexedSorter {
public QuickSort() { }
@@ -39,7 +39,8 @@
* Same as [EMAIL PROTECTED] #sort}, but indicate that we're making progress
after
* each partition.
*/
- public void sort(IndexedSortable s, int p, int r, Progressable rep) {
+ public void sort(final IndexedSortable s, final int p, final int r,
+ final Progressable rep) {
if (null != rep) {
rep.progress();
}
@@ -60,26 +61,45 @@
fix(s, p, r-1);
// Divide
- int x = p;
int i = p;
int j = r;
+ int ll = p;
+ int rr = r;
+ int cr;
while(true) {
- while (++i < r && s.compare(i, x) < 0) { } // move lindex
- while (--j > x && s.compare(x, j) < 0) { } // move rindex
+ while (++i < j) {
+ if ((cr = s.compare(i, p)) > 0) break;
+ if (0 == cr && ++ll != i) {
+ s.swap(ll, i);
+ }
+ }
+ while (--j > i) {
+ if ((cr = s.compare(p, j)) > 0) break;
+ if (0 == cr && --rr != j) {
+ s.swap(rr, j);
+ }
+ }
if (i < j) s.swap(i, j);
else break;
}
- // swap pivot into position
- s.swap(x, i - 1);
+ j = i;
+ // swap pivot- and all eq values- into position
+ while (ll >= p) {
+ s.swap(ll--, --i);
+ }
+ while (rr < r) {
+ s.swap(rr++, j++);
+ }
// Conquer
// Recurse on smaller interval first to keep stack shallow
- if (i - p - 1 < r - i) {
- sort(s, p, i - 1, rep);
- sort(s, i, r, rep);
+ assert i != j;
+ if (i - p < r - j) {
+ sort(s, p, i, rep);
+ sort(s, j, r, rep);
} else {
- sort(s, i, r, rep);
- sort(s, p, i - 1, rep);
+ sort(s, j, r, rep);
+ sort(s, p, i, rep);
}
}
Modified: hadoop/core/trunk/src/test/org/apache/hadoop/util/TestIndexedSort.java
URL:
http://svn.apache.org/viewvc/hadoop/core/trunk/src/test/org/apache/hadoop/util/TestIndexedSort.java?rev=651735&r1=651734&r2=651735&view=diff
==============================================================================
--- hadoop/core/trunk/src/test/org/apache/hadoop/util/TestIndexedSort.java
(original)
+++ hadoop/core/trunk/src/test/org/apache/hadoop/util/TestIndexedSort.java Fri
Apr 25 16:06:56 2008
@@ -165,18 +165,31 @@
}
public void testAllEqual() throws Exception {
- final int SAMPLE = 50;
+ final int SAMPLE = 500;
int[] values = new int[SAMPLE];
Arrays.fill(values, 10);
SampleSortable s = new SampleSortable(values);
IndexedSorter sorter = new QuickSort();
sorter.sort(s, 0, SAMPLE);
int[] check = s.getSorted();
- assertTrue(Arrays.equals(values, check));
+ assertTrue(Arrays.toString(values) + "\ndoesn't match\n" +
+ Arrays.toString(check), Arrays.equals(values, check));
+ Random r = new Random();
+ int diff = r.nextInt(SAMPLE);
+ values[diff] = 9;
+ values[(diff + r.nextInt(SAMPLE >>> 1)) % SAMPLE] = 11;
+ s = new SampleSortable(values);
+ sorter.sort(s, 0, SAMPLE);
+ check = s.getSorted();
+ Arrays.sort(values);
+ assertTrue(check[0] == 9);
+ assertTrue(check[SAMPLE - 1] == 11);
+ assertTrue(Arrays.toString(values) + "\ndoesn't match\n" +
+ Arrays.toString(check), Arrays.equals(values, check));
}
public void testSorted() throws Exception {
- final int SAMPLE = 50;
+ final int SAMPLE = 500;
int[] values = new int[SAMPLE];
Random r = new Random();
for (int i = 0; i < SAMPLE; ++i) {
@@ -187,7 +200,22 @@
IndexedSorter sorter = new QuickSort();
sorter.sort(s, 0, SAMPLE);
int[] check = s.getSorted();
- assertTrue(Arrays.equals(values, check));
+ assertTrue(Arrays.toString(values) + "\ndoesn't match\n" +
+ Arrays.toString(check), Arrays.equals(values, check));
+ }
+
+ public void testSequential() throws Exception {
+ final int SAMPLE = 500;
+ int[] values = new int[SAMPLE];
+ for (int i = 0; i < SAMPLE; ++i) {
+ values[i] = i;
+ }
+ SampleSortable s = new SampleSortable(values);
+ IndexedSorter sorter = new QuickSort();
+ sorter.sort(s, 0, SAMPLE);
+ int[] check = s.getSorted();
+ assertTrue(Arrays.toString(values) + "\ndoesn't match\n" +
+ Arrays.toString(check), Arrays.equals(values, check));
}
public void testSingleRecord() throws Exception {
@@ -198,18 +226,20 @@
IndexedSorter sorter = new QuickSort();
sorter.sort(s, 0, SAMPLE);
int[] check = s.getSorted();
- assertTrue(Arrays.equals(values, check));
+ assertTrue(Arrays.toString(values) + "\ndoesn't match\n" +
+ Arrays.toString(check), Arrays.equals(values, check));
}
public void testQuickSort() throws Exception {
- final int SAMPLE = 10000;
+ final int SAMPLE = 100000;
SampleSortable s = new SampleSortable(SAMPLE);
int[] values = s.getValues();
Arrays.sort(values);
IndexedSorter sorter = new QuickSort();
sorter.sort(s, 0, SAMPLE);
int[] check = s.getSorted();
- assertTrue(Arrays.equals(values, check));
+ assertTrue(Arrays.toString(values) + "\ndoesn't match\n" +
+ Arrays.toString(check), Arrays.equals(values, check));
}
public void testWritable() throws Exception {
@@ -220,7 +250,8 @@
IndexedSorter sorter = new QuickSort();
sorter.sort(s, 0, SAMPLE);
String[] check = s.getSorted();
- assertTrue(Arrays.equals(values, check));
+ assertTrue(Arrays.toString(values) + "\ndoesn't match\n" +
+ Arrays.toString(check), Arrays.equals(values, check));
}
}
