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
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
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
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
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
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,
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
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
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
>
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
> 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
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
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
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.
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
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
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
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
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
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
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
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
22 matches
Mail list logo
