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
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
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 marqu...@marquits.com
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
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
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,
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
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 gokdo...@gmail.com wrote:
My absolutely non-scientific preliminary tests indicate Arrays.sort
performs better with the same input (5000 items) in
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
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
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
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
Le
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 do
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 instead:
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.
Vladimir Yaroslavskiy vladimir.yaroslavs...@... 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
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
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
18 matches
Mail list logo
