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
_________________________________________________________________
Your E-mail and More On-the-Go. Get Windows Live Hotmail Free.
https://signup.live.com/signup.aspx?id=60969
