Yes. I prefer F (Find First zero using binary search) over C (Count negatives)
and S (Smart Scan for zero).
> From: iaroslav...@mail.ru
> To: dmytro_she...@hotmail.com
> CC: j...@google.com; core-libs-dev@openjdk.java.net; iaroslav...@mail.ru
> 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
> <dmytro_she...@hotmail.com>:
>
> > 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: 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: 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 <j...@google.com>:
> > >
> > > > 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
