Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
Vladimir Iaroslavski
iaroslavski at mail.ru
Fri Sep 11 13:42:12 UTC 2009
Hi Ulf,
Sure, I have tried it, see:
-------- Original Message --------
Subject: Re: Dual-Pivot Quicksort Analysis
Date: Wed, 09 Sep 2009 18:45:46 +0400
From: Vladimir Yaroslavskiy <Vladimir.Yaroslavskiy at Sun.COM>
Organization: Sun Microsystems, Inc.
To: Jon Bentley <jbentley at avaya.com>
CC: Joshua Bloch <jjb at google.com>
Hello,
I've converted the pseudocode into Java and here is the result:
I counted the comps and swaps for array with length n = 2'000'000,
did it 77 times and took the average value:
Classic Quicksort: comps - 52254956
swaps - 26277985
Dual-Pivot Quicksort: comps - 52246553
swaps - 20977937
These values correlate with math proof: the number of comps
the same (2*n*ln(n)) and ratio for swaps is 20977937/26277985
= 0.7983 (theoretical is 0.8/1.0 = 0.8).
I don't have "few words" explanation wh ythe new algorithm is quicker,
just the ratio swaps/comps/partitions is better for Dual-Pivot Quicksort.
If we consider common case when we have (k-1) pivots and divide an
array into k parts, we can ask, if the case k=3 (Dual-Pivot Quicksort)
is the best? May be k=4,5 are better?
It's easy to define recurrence relation for the count of operations
when k=3,4,... but mathematical conclusion will be too complex.
But to find out the answer for this question, I run pseudocode
(in Java, see attached class) for k=4,5 and got:
Quicksort with 3 pivots/4 parts: comps - 54399943
swaps - 24224254
Quicksort with 4 pivots/5 parts: comps - 57241615
swaps - 28659728
So, you can see that "3 pivots/4 parts" is better than
Classic Quicksort for swaps only, "4 pivots/5 parts" is
the looser, and "Dual-Pivot Quicksort" is real winner.
I feel it is expectable result: if we have many pivots
we spent a lot of time on sorting them and dividing into
more parts doesn't save. In case with 2 pivots, we use
only 1 comparison and 1/2 swaps to sort it out.
BTW, the dividing into 3 parts instead of two also shows
better results for MergeSort (but it's not actual for JDK
because TimSort is faster).
Ulf Zibis wrote:
> Very interesting stuff.
>
> Does one have tried (theoretically and/or experimental) P1+P2+P3,
> P1+P2+P3+P2, ... segmentation ?
> Maybe coefficient A has a minimum below 0.8.
>
> -Ulf
>
> Am 11.09.2009 12:35, Vladimir Yaroslavskiy schrieb:
>> Hello All,
>>
>> I'd like to share with you new Dual-Pivot Quicksort which is
>> faster than the known implementations (theoretically and
>> experimental). I'd like to propose to replace the JDK's
>> Quicksort implementation by new one.
>>
>> Description
>> -----------
>> The classical Quicksort algorithm uses the following scheme:
>>
>> 1. Pick an element P, called a pivot, from the array.
>> 2. Reorder the array so that all elements, which are less than
>> the pivot, come before the pivot and all elements greater than
>> the pivot come after it (equal values can go either way). After
>> this partitioning, the pivot element is in its final position.
>> 3. Recursively sort the sub-array of lesser elements and the
>> sub-array of greater elements.
>>
>> The invariant of classical Quicksort is:
>>
>> [ <= p | >= p ]
>>
>> There are several modifications of the schema:
>>
>> [ < p | = p | > p ] or [ = p | < p | > p | = p ]
>>
>> But all of them use *one* pivot.
>>
>> The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
>>
>> 1. Pick an elements P1, P2, called pivots from the array.
>> 2. Assume that P1 <= P2, otherwise swap it.
>> 3. Reorder the array into three parts: those less than the smaller
>> pivot, those larger than the larger pivot, and in between are
>> those elements between (or equal to) the two pivots.
>> 4. Recursively sort the sub-arrays.
>>
>> The invariant of the Dual-Pivot Quicksort is:
>>
>> [ < P1 | P1 <= & <= P2 } > P2 ]
>>
>> The new Quicksort is faster than current implementation of Quicksort
>> in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.
>>
>> The full description of the Dual-Pivot Quicksort you can find
>> on my page: http://iaroslavski.narod.ru/quicksort
>>
>> Performance tests
>> -----------------
>> Here is result of running on different types of input data:
>>
>> Client VM all 85% organ 0..1 0..4
>> random ascend descend equal equal pipes random 010101
>> random
>> Dual-Pivot: 16.83 5.31 5.47 0.35 0.68 10.59 1.06 1.02 2.18
>> Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49
>>
>> Server VM all 85% organ 0..1 0..4
>> random ascend descend equal equal pipes random 010101
>> random
>> Dual-Pivot: 23.94 6.68 6.63 0.43 0.62 17.14 1.42 1.96 3.41
>> Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39
>>
>> The a lot of other tests have been run under client and server mode.
>> The most interesting is BentleyBasher test framework. It runs battery
>> of tests for all cases:
>>
>> { 100, 1000, 10000, 1000000 } x
>> { sawtooth, rand, stagger, plateau, shuffle } x
>> { ident, reverse, reverse_front, reverse_back, sort, dither}
>>
>> where
>>
>> 100, ... , 1000000 - array length
>>
>> sawtooth: x[i] =i%m
>> rand: x[i] = rand() % m
>> stagger: x[i] = (i*m + i) % n
>> plateau: x[i] = min(i, m)
>> shuffle: x[i] = rand()%m? (j+=2): (k+=2)
>>
>> ident(x) - a copy of x
>> reverse(x, 0, n) - reversed copy
>> reverse_front(x, 0, n/2) - front half reversed
>> reverse_back(x, n/2, n) - back half reversed
>> sort(x) - an ordered copy
>> dither(x) - add i%5 to x[i]
>>
>> Here is the result of execution:
>> Server VM:
>> http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html
>>
>> Client VM:
>> http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&gid=0&output=html
>>
>>
>> Mathematical investigations
>> ---------------------------
>> It is proved that for the Dual-Pivot Quicksort the average number of
>> comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
>> whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
>> respectively. Full mathematical proof see in attached proof.txt
>> and proof_add.txt files. Theoretical results are also confirmed
>> by experimental counting of the operations.
>>
>> Diff between current and new implementation of Quicksort
>> --------------------------------------------------------
>>
>> Here is the link to the diff for java.util.Arrays class:
>> http://cr.openjdk.java.net/~alanb/6880672/webrev.00
>>
>> If you like to look and play with new algorithm,
>> please, take attached class DualPivotQuicksort.java
>>
>> Feedback
>> --------
>>
>> Also I'd like to share a feedback from Joshua Bloch and
>> Jon Bentley who spent a lot of time investigating this
>> algorithm, who gave me many advices and tips how to
>> make new Quicksort better.
>>
>> -------- Original Message --------
>> Subject: Re: Integration of new Dual-Pivot Quicksort into JDK 7
>> Date: Thu, 10 Sep 2009 07:20:11 -0700
>> From: Joshua Bloch <jjb at google.com>
>>
>> Jon also says that Vladimir should make every reasonable improvement to
>> the basic method before checking in the code. In his words, "It would be
>> horrible to put the new code into the library, and then have someone
>> else come along and speed it up by another 20% by using standard
>> techniques." I believe it's not unlikely that this code may end up
>> getting ported to many languages and widely deployed in much the manner
>> of Bentley and McIlroy's fine sort (which is nearing 20 successful years
>> in the field). Jon will help Vladimir do this.
>>
>> -------- Original Message --------
>> Subject: Dual-Pivot Quicksort: Next Steps
>> Date: Wed, 09 Sep 2009 15:02:25 -0400
>> From: Jon Bentley <jbentley at avaya.com>
>>
>> Vladimir, Josh,
>> I *finally* feel like I understand what is going on. Now that I
>> (think that) I see it, it seems straightforward and obvious.
>> Tony Hoare developed Quicksort in the early 1960s. I was very
>> proud to make minor contributions to a particularly clean (binary)
>> quicksort in the mid 1980s, to a relatively straightforward, industrial
>> strength Quicksort with McIlroy in the early 1990s, and then to
>> algorithms and data structures for strings with Sedgewick in the mid
>> 1990s.
>> I think that Vladimir's contributions to Quicksort go way beyond
>> anything that I've ever done, and rank up there with Hoare's original
>> design and Sedgewick's analysis. I feel so privileged to play a very,
>> very minor role in helping Vladimir with the most excellent work!
>>
>> -----------------------------------------------
>>
>> Let me know, if you have any questions/comments.
>>
>> Thank you,
>> Vladimir
More information about the core-libs-dev
mailing list