Yes. I prefer F (Find First zero using binary search) over C (Count negatives) and S (Smart Scan for zero).
> From: [email protected] > To: [email protected] > CC: [email protected]; [email protected]; [email protected] > Subject: Re[4]: New portion of improvements for Dual-Pivot Quicksort > Date: Thu, 13 May 2010 21:34:54 +0400 > > Dmytro, > > I've tested your suggested variants, and found that case "C" > (very interesting approach to find first position of zero > by counting negative elements) works slower than original > or two other cases. > > Implementations "F" and "S" are very close to each other > and little bit faster than original. I prefer case "F": > it is shorter and more clear. Do you agree? > > I'll prepare updated DualPivotQuicksort file and send it > tomorrow. > > Thank you, > Vladimir > > Wed, 12 May 2010 17:04:52 +0700 письмо от Dmytro Sheyko > <[email protected]>: > > > Vladimir, > > > > Your changes are good for me. > > > > Additionally I have some comments/proposals regarding dealing with negative > > zeros. > > > > 1. Scanning for the first zero we can avoid range check (i >= left) if we > > have at least one negative value. > > --- DualPivotQuicksort.java Tue May 11 09:04:19 2010 > > +++ DualPivotQuicksortS.java Wed May 12 12:10:46 2010 > > @@ -1705,10 +1705,15 @@ > > } > > > > // Find first zero element > > - int zeroIndex = findAnyZero(a, left, n); > > + int zeroIndex = 0; > > > > - for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) { > > - zeroIndex = i; > > + if (a[left] < 0.0f) { > > + zeroIndex = findAnyZero(a, left, n); > > + > > + // there is at least one negative value, so range check is not > > needed > > + for (int i = zeroIndex - 1; /*i >= left &&*/ a[i] == 0.0f; > > i--) { > > + zeroIndex = i; > > + } > > } > > > > // Turn the right number of positive zeros back into negative zeros > > > > 2. We can find the position of the first zero by counting negative values > > during preprocessing phase. > > --- DualPivotQuicksort.java Tue May 11 09:04:19 2010 > > +++ DualPivotQuicksortC.java Wed May 12 12:01:24 2010 > > @@ -1678,7 +1678,7 @@ > > * Phase 1: Count negative zeros and move NaNs to end of array. > > */ > > final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f); > > - int numNegativeZeros = 0; > > + int numNegativeZeros = 0, numNegativeValues = 0; > > int n = right; > > > > for (int k = left; k <= n; k++) { > > @@ -1689,6 +1689,8 @@ > > } else if (ak != ak) { // i.e., ak is NaN > > a[k--] = a[n]; > > a[n--] = Float.NaN; > > + } else if (ak < 0.0f) { > > + numNegativeValues++; > > } > > } > > > > @@ -1705,7 +1707,7 @@ > > } > > > > // Find first zero element > > - int zeroIndex = findAnyZero(a, left, n); > > + int zeroIndex = numNegativeValues; > > > > for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) { > > zeroIndex = i; > > > > 3. We can use binary search to find the first zero and thus avoid linear > > scan. > > --- DualPivotQuicksort.java Tue May 11 09:04:19 2010 > > +++ DualPivotQuicksortF.java Wed May 12 12:03:58 2010 > > @@ -1705,11 +1705,7 @@ > > } > > > > // Find first zero element > > - int zeroIndex = findAnyZero(a, left, n); > > - > > - for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) { > > - zeroIndex = i; > > - } > > + int zeroIndex = findFirstZero(a, left, n); > > > > // Turn the right number of positive zeros back into negative zeros > > for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; > > i++) { > > @@ -1718,7 +1714,7 @@ > > } > > > > /** > > - * Returns the index of some zero element in the specified range via > > + * Returns the index of the first zero element in the specified range > > via > > * binary search. The range is assumed to be sorted, and must contain > > * at least one zero. > > * > > @@ -1726,18 +1722,17 @@ > > * @param low the index of the first element, inclusive, to be searched > > * @param high the index of the last element, inclusive, to be searched > > */ > > - private static int findAnyZero(float[] a, int low, int high) { > > - while (true) { > > + private static int findFirstZero(float[] a, int low, int high) { > > + while (low < high) { > > int middle = (low + high) >>> 1; > > float middleValue = a[middle]; > > > > if (middleValue < 0.0f) { > > low = middle + 1; > > - } else if (middleValue > 0.0f) { > > - high = middle - 1; > > - } else { // middleValue == 0.0f > > - return middle; > > + } else { // middleValue >= 0.0f > > + high = middle; > > } > > + return low; > > } > > } > > > > Counting negative values appeared more expensive than any other variants. > > The last proposal seems to me as efficient as the current solution is in > > its worst case - when we have only one negative zero (in the half of array). > > And it shows the best result if we have many zeros. > > > > Regards, > > Dmytro Sheyko > > > > > From: [email protected] > > > To: [email protected]; [email protected] > > > CC: [email protected]; [email protected] > > > Subject: Re[2]: New portion of improvements for Dual-Pivot Quicksort > > > Date: Sun, 9 May 2010 23:51:27 +0400 > > > > > > Josh, > > > Dmytro, > > > > > > I have done more thoroughly testing "great - less > 5 * seventh" vs. > > > "less < e1 && great > e5", > > > and found that more symmetric code "less < e1 && great > e5" is little > > > bit faster, ~0.5..0.7% > > > on both VMs. Other code has not been changed. > > > > > > Please, take the latest version in attachment. > > > > > > Vladimir > > > > > > Tue, 4 May 2010 21:57:42 -0700 письмо от Joshua Bloch <[email protected]>: > > > > > > > Vladimir, > > > > > > > > Old: > > > > > > > >298 if (less < e1 && great > e5) { > > > > > > > > New: > > > > > > > >256 if (great - less > 5 * seventh) { > > > > > > >Regards, > > > >Josh _________________________________________________________________ Hotmail: Trusted email with Microsoft’s powerful SPAM protection. https://signup.live.com/signup.aspx?id=60969
