Hi,
Wouldn't it better to use boolean flag instead of int index?
--
Dmytro Sheyko
PS
--- DualPivotQuicksortWithoutSentinel.java Fri May 07 10:40:14 2010
+++ DualPivotQuicksortWithoutSentinelA.java Fri May 07 11:54:51 2010
@@ -39,7 +39,7 @@
* @version 2010.04.30 m765.827.12i:5\7
* @since 1.7
*/
-final class DualPivotQuicksortWithoutSentinel {
+final class DualPivotQuicksortWithoutSentinelA {
/**
* Prevents instantiation.
@@ -78,7 +78,7 @@
* @param a the array to be sorted
*/
public static void sort(int[] a) {
- dualPivotQuicksort(a, 0, a.length - 1, 0);
+ dualPivotQuicksort(a, 0, a.length - 1, true);
}
/**
@@ -96,7 +96,7 @@
*/
public static void sort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- dualPivotQuicksort(a, fromIndex, toIndex - 1, fromIndex);
+ dualPivotQuicksort(a, fromIndex, toIndex - 1, true);
}
/**
@@ -108,12 +108,12 @@
* @param right the index of the last element, inclusive, to be sorted
* @param fromIndex the first index of the original range to be sorted
*/
- private static void dualPivotQuicksort(int[] a, int left, int
right, int fromIndex) {
+ private static void dualPivotQuicksort(int[] a, int left, int
right, boolean leftmost) {
int length = right - left + 1;
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
- if (left > fromIndex) {
+ if (!leftmost) {
/*
* TODO
*/
@@ -129,11 +129,11 @@
* For case, when left == fromIndex, traditional (without
* sentinel) insertion sort, optimized for server VM,
is used.
*/
- for (int i = fromIndex, j = i; i < right; j = ++i) {
+ for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
- if (j-- == fromIndex) {
+ if (j-- == left) {
break;
}
}
@@ -237,8 +237,8 @@
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known
pivots
- dualPivotQuicksort(a, left, less - 2, fromIndex);
- dualPivotQuicksort(a, great + 2, right, fromIndex);
+ dualPivotQuicksort(a, left, less - 2, leftmost);
+ dualPivotQuicksort(a, great + 2, right, false);
/*
* If center part is too large (comprises > 5/7 of the array),
@@ -295,7 +295,7 @@
}
// Sort center part recursively
- dualPivotQuicksort(a, less, great, fromIndex);
+ dualPivotQuicksort(a, less, great, false);
} else { // Pivots are equal
/*
@@ -350,8 +350,8 @@
}
// Sort left and right parts recursively
- dualPivotQuicksort(a, left, less - 1, fromIndex);
- dualPivotQuicksort(a, great + 1, right, fromIndex);
+ dualPivotQuicksort(a, left, less - 1, leftmost);
+ dualPivotQuicksort(a, great + 1, right, false);
}
}
> From: iaroslav...@mail.ru
> To: j...@google.com; dmytro_she...@hotmail.com
> CC: core-libs-dev@openjdk.java.net; iaroslav...@mail.ru
> Subject: Re[2]: New portion of improvements for Dual-Pivot Quicksort
> Date: Fri, 7 May 2010 00:46:59 +0400
>
> Hello Josh, Dmytro,
>
> I've modified the DQP and now it doesn't touch elements outside of
> the range and doesn't set a sentinel at all. Elements from the left
> part are used as a sentinel (as it was suggested by Dmytro) and index
> fromIndex is used as left boundary (suggestion from Josh). The index
> fromIndex is the initial left boundary and passed down through the
> recursions. No any tricks with changing outside of the range and
> negative infinity.
>
> The fragment of code is (full version see in attachment):
>
> * ...
> * @param fromIndex the first index of the original range to be sorted
> */
> private static void dualPivotQuicksort(int[] a, int left, int right,
int fromIndex) {
> int length = right - left + 1;
>
> // Use insertion sort on tiny arrays
> if (length < INSERTION_SORT_THRESHOLD) {
> if (left > fromIndex) {
> /*
> * TODO
> */
> for (int j, i = left + 1; i <= right; i++) {
> int ai = a[i];
> for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
> a[j + 1] = a[j];
> }
> a[j + 1] = ai;
> }
> } else {
> /*
> * For case, when left == fromIndex, traditional (without
> * sentinel) insertion sort, optimized for server VM, is used.
> */
> for (int i = fromIndex, j = i; i < right; j = ++i) {
> int ai = a[i + 1];
> while (ai < a[j]) {
> a[j + 1] = a[j];
> if (j-- == fromIndex) {
> break;
> }
> }
> a[j + 1] = ai;
> }
> }
> return;
> }
> ...
>
> This variant is little bit faster (~0.5%) on client VM and slower (~2%)
> on server VM than original variant. I think that it is not too bad.
> What do you think?
>
> And one question: the method declaration
>
> private static void dualPivotQuicksort(int[] a, int left, int right,
int fromIndex) {
>
> now is too long, how should I format it? What is the guideline?
>
> Thank you,
> Vladimir
>
> Wed, 5 May 2010 18:21:18 -0400 письмо от Joshua Bloch <j...@google.com>:
>
> > Vladimir,
> >
> > On Wed, May 5, 2010 at 12:57 AM, Joshua Bloch <j...@google.com> wrote:
> >
> > The sentinel technique that you use in lines 118 - 136 is
questionable: you are modifying a portion of the array outside the
specified range of the call, which arguably violates the contract of the
call, and could be observed in a multithreaded program. It's not beyond
the realm of reason that it could break existing clients. I will discuss
it with Doug Lea and let you know what he says.
> >
> > I talked to Doug, and he agrees that it's not acceptable to modify
any location outside the array range that the caller has asked you to
sort. This doesn't entirely kill the optimization; it's still OK to use
on subranges that don't include the first element of the range that you
were asked to sort. In other words, this test
> >
> > 120 if (left > 0) {
> >
> > Should be replaced by:
> >
> > 120 if (left > fromIndex + 1) {
> >
> > and you have to pass original fromIndex down to the recursive calls
(in fact, you could pass fromIndex +1 to avoid the cost of the addition
in each test). It's not clear whether the cost of passing this index
down through the recursive calls will eliminate the gains of the
optimization, but it's worth performing the experiment.
> >
> > Sorry,
> > Josh
