Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2016-03-02 Thread Jason C. McDonald
Hi Stuart, I hate replying to an ancient threat, but I figured it was the best method. Thanks for the tips. The original paper was almost as hard to find as he is proving to be. :) All the best, -Jason C. McDonald On 02/26/2016 06:05 PM, Stuart Marks wrote: Wow, is this a reply to a nearly

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2016-02-26 Thread Stuart Marks
Wow, is this a reply to a nearly seven-year-old email? [1] I don't know if Vladimir Yaroslavskiy is still on core-libs-dev. I dug through tthe archives and found that he had posted a couple messages somewhat later [2] [3] using different email addresses: Vladimir Iaroslavski Vladimir Iar

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2016-02-23 Thread Jason C . McDonald
I think this is the best place to contact the original authors. The link to Vladimir Yaroslavskiy's original whitepaper describing the algorithm and its proofs was, unfortunately, broken. Using Archive.org's Wayback Machine, I was able to get the last known revision. I reformatted the document in

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-10-19 Thread Vladimir Iaroslavski
Date: Tue, 6 Oct 2009 23:11:25 + (UTC) From: quitos Subject: Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort To: core-libs-dev@openjdk.java.net I suppose if the array is small enough, it is better to use simple Quicksort. And the larger the array, the more

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-10-06 Thread quitos
I suppose if the array is small enough, it is better to use simple Quicksort. And the larger the array, the more sense it makes to use more pivots, because the calculation cost of comparing against many pivots becomes more affordable than iterating for a larger subset. So you think the optimal n

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-13 Thread Oleg Anashkin
Hello Vladimir, First thing that came to mind - have you thought about extrapolating this approach to more pivots? If 2-pivot algorithm is faster than 1-pivot, then 3-pivot might be even faster, right? Can the number of pivots be chosen as a function of array size (to mitigate overhead)? Thanks,

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-13 Thread Goktug Gokdogan
I reviewed the code. A few simple tricks helped me to speed-up code in my tests:1. Falling back-to insertion sort at <17 instead of <27 (JDK 6 Arrays.sort falls back <7) 2. (a[great] > pivot2) test is more likely to fail compared to (k < great) in the while loop, so exchange them (ie. use while (a

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-12 Thread Joshua Bloch
To amplify my previous statement, I think this is a great piece of work! Vladimir is to be commended. I also think that it may well get substantially faster as Vladimir continues to make minor algorithmic modifications. Jon Bentley has made many fine suggestions that Vladimir will try out.There ar

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-12 Thread Goktug Gokdogan
Sorry :( . Please ignore previous post. Warming-up yield to better results in dual-pivot's favor. On Sat, Sep 12, 2009 at 2:43 PM, Goktug Gokdogan wrote: > My absolutely non-scientific preliminary tests indicate Arrays.sort > performs better with the same input (5000 items) in nearly all runs >

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-12 Thread Goktug Gokdogan
My absolutely non-scientific preliminary tests indicate Arrays.sort performs better with the same input (5000 items) in nearly all runs (-client). public static void main(String[] args) { final int n = 5000; int[] array = new int[n]; int[] array2 = new int[n]; Random random = new Random(); for (int

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Vadim Ponomarenko
> Vadim-It would be very interesting if something along these lines could be made practical.  It isn't obvious how to do step (3) in place.  Either you end up allocating extra storage to do it, in which case you might as well have used a merge sort, or you end up doing some extra shuffling aroun

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Neal Gafter
Vadim- It would be very interesting if something along these lines could be made practical. It isn't obvious how to do step (3) in place. Either you end up allocating extra storage to do it, in which case you might as well have used a merge sort, or you end up doing some extra shuffling around o

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Vadim Ponomarenko
Vladimir Yaroslavskiy writes: > 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. This is a great idea; as a mathematician I immed

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Leonid Geller
As an observation, why not expand the new algorithm to N-Pivot where N = round(ln(array length)). This should lower the average sort cost even lower.

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Jonathan Graehl
Nice. > int third = len / div; > > // "medians" > int m1 = left + third; > int m2 = right - third; > > if (m1 <= left) { > m1 = left + 1; > } > if (m2 >= right) { > m2 = right - 1; > } I'd suggest this inst

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Vladimir Iaroslavski
Hi, I've tried to use local variable int ak = a[k] in the loop and not found saving of time. There are 3 occurrences of a[k] in each loop, but only two can be changed because third comes after line: swap(a, k, great--); As summary: I'm changing only hardcoded constant by private static final var

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Ulf Zibis
Am 11.09.2009 15:32, Rémi Forax schrieb: just my two cents : In the loop tagged "sorting" and "equals element", a[k] can be stored in a local variable to avoid to recompute it several time. I add 2 cents more: Doesn't HotSpot see this, and optimize accordingly? IMO: It's time that javac should

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Vladimir Iaroslavski
sure, will do it Rémi Forax wrote: just my two cents : In the loop tagged "sorting" and "equals element", a[k] can be stored in a local variable to avoid to recompute it several time. The algorithm use two constants: 37 and 13, I think they should be declared as private static final. Rémi L

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Vladimir Iaroslavski
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 Organization: Sun Microsystems, Inc. To: Jon Bentley CC: Joshua Bloch Hello, I've converted the pseudocode into

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Ulf Zibis
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 whi

Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Rémi Forax
just my two cents : In the loop tagged "sorting" and "equals element", a[k] can be stored in a local variable to avoid to recompute it several time. The algorithm use two constants: 37 and 13, I think they should be declared as private static final. Rémi Le 11/09/2009 12:35, Vladimir Yarosla

Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

2009-09-11 Thread Vladimir Yaroslavskiy
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 followi