Prev: adding a new library .jar to your path (netbeans)
Next: Turning off JIT Optimisation
From: Jon Harrop on 15 May 2010 11:35
I cannot find an implementation of parallel quicksort in Java. Does anyone
have one or know where I can get one?

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com

From: Kevin McMurtrie on 15 May 2010 19:19
In article <d7-dnea9C8TRInPWnZ2dnUVZ7o2dnZ2d(a)brightview.co.uk>,
"Jon Harrop" <usenet(a)ffconsultancy.com> wrote:

> I cannot find an implementation of parallel quicksort in Java. Does anyone
> have one or know where I can get one?

This question came up before and I still have the code lying around.
It is not tuned and better algorithms exist. This only demonstrates
putting the left and right sub-sorts of an existing algorithm on
different threads.

Quicksort is typically limited by memory throughput. Multithreading
helps when comparing values is computationally expensive. For a massively
parallel system you'd probably quicksort subsets on different hardware
then produce a single sorted stream through mergesort.


public class Run
{
/***************************************************************************
* Quicksort code from Sedgewick 7.1, 7.2.
**************************************************************************/
public static void quicksort(double[] a)
{
//shuffle(a); // to guard against worst-case
quicksort(a, 0, a.length - 1, 0);
}

static void quicksort(final double[] a, final int left, final int right, final int tdepth)
{
if (right <= left)
return;
final int i = partition(a, left, right);

if ((tdepth < 4) && ((i - left) > 1000))
{
final Thread t = new Thread()
{
public void run()
{
quicksort(a, left, i - 1, tdepth + 1);
}
};
t.start();
quicksort(a, i + 1, right, tdepth + 1);

try
{
t.join();
}
catch (InterruptedException e)
{
throw new RuntimeException("Cancelled", e);
}
} else
{
quicksort(a, left, i - 1, tdepth);
quicksort(a, i + 1, right, tdepth);
}
}

// partition a[left] to a[right], assumes left < right
private static int partition(double[] a, int left, int right)
{
int i = left - 1;
int j = right;
while (true)
{
while (less(a[++i], a[right]))
// find item on left to swap
; // a[right] acts as sentinel
while (less(a[right], a[--j]))
// find item on right to swap
if (j == left)
break; // don't go out-of-bounds
if (i >= j)
break; // check if pointers cross
exch(a, i, j); // swap two elements into place
}
exch(a, i, right); // swap with partition element
return i;
}

// is x < y ?
private static boolean less(double x, double y)
{
return (x < y);
}

// exchange a[i] and a[j]
private static void exch(double[] a, int i, int j)
{
double swap = a[i];
a[i] = a[j];
a[j] = swap;
}

// shuffle the array a[]
private static void shuffle(double[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
{
int r = i + (int) (Math.random() * (N - i)); // between i and N-1
exch(a, i, r);
}
}

// test client
public static void main(String[] args)
{
int N = 5000000; // Integer.parseInt(args[0]);

// generate N random real numbers between 0 and 1
long start = System.currentTimeMillis();
double[] a = new double[N];
for (int i = 0; i < N; i++)
a[i] = Math.random();
long stop = System.currentTimeMillis();
double elapsed = (stop - start) / 1000.0;
System.out.println("Generating input: " + elapsed + " seconds");

// sort them
start = System.currentTimeMillis();
quicksort(a);
stop = System.currentTimeMillis();
elapsed = (stop - start) / 1000.0;
System.out.println("Quicksort: " + elapsed + " seconds");

}
}
--
I won't see Google Groups replies because I must filter them as spam
From: Arne Vajhøj on 15 May 2010 19:26
On 15-05-2010 11:35, Jon Harrop wrote:
> I cannot find an implementation of parallel quicksort in Java. Does
> anyone have one or know where I can get one?

public static void tqsint(int[] ia, int tdepth) {
tqsint_help(0, ia.length - 1, ia, 0, tdepth);
return;
}
public static void tqsint_help(int n1, int n2, int[] ia, int depth,
int tdepth) {
int tmp;
int l = n1;
int r = n2;
int pivot = ia[(n1 + n2) / 2];
do {
while (ia[l] < pivot)
l++;
while (ia[r] > pivot)
r--;
if (l <= r) {
tmp = ia[l];
ia[l] = ia[r];
ia[r] = tmp;
l++;
r--;
}
} while (l <= r);
if (depth >= tdepth) {
if (n1 < r)
tqsint_help(n1, r, ia, depth + 1, tdepth);
if (l < n2)
tqsint_help(l, n2, ia, depth + 1, tdepth);
} else {
ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1,
tdepth);
ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1,
tdepth);
h1.start();
h2.start();
try {
h1.join();
h2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
return;
}

....

class ThreadSortHelp extends Thread {
private int n1;
private int n2;
private int[] ia;
private int depth;
private int tdepth;
public ThreadSortHelp(int n1, int n2, int[] ia, int depth, int tdepth) {
super();
this.n1 = n1;
this.n2 = n2;
this.ia = ia;
this.depth = depth;
this.tdepth = tdepth;
}
public void run() {
ThreadSort.tqsint_help(n1, n2, ia, depth, tdepth);
}
}

Arne
From: markspace on 15 May 2010 19:47
Arne Vajh�j wrote:
> } else {
> ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1,
> tdepth);
> ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1,
> tdepth);


Just a thought: Why spawn two threads here? You already have one
thread running (the current one). Spawn one thread (proabaly on the
larger span between pivot and start/end) and sort the other bit
recursively in the current thread. Then just wait on the other thread
after you're done with the recursive sort.


However, I played around with this myself a while ago, and I'm not sure
the whole idea is a great one. Quicksorts are god-awful at sorting many
real world types of data. If a list is already sorted, then quicksort
degenerates into a bubble sort. That's N^2 performance. And pre-sorted
data is pretty common so you're likely to hit this issue often.

I think it would be better to change the problem to some kind of
multi-threaded mergesort . Merge sort always takes n log n, it's got no
weird corners like quicksort. You could probably speed up the
multi-threaded version by having higher level "merges" merge data as it
becomes available, rather than waiting for an entire lower level pass to
complete.
From: Arne Vajhøj on 15 May 2010 20:14
On 15-05-2010 19:47, markspace wrote:
> Arne Vajh�j wrote:
>> } else {
>> ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1, tdepth);
>> ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1, tdepth);
>
> Just a thought: Why spawn two threads here? You already have one thread
> running (the current one). Spawn one thread (proabaly on the larger span
> between pivot and start/end) and sort the other bit recursively in the
> current thread. Then just wait on the other thread after you're done
> with the recursive sort.

It may be more efficient. But I like the symmetric approach of
this code.

> However, I played around with this myself a while ago, and I'm not sure
> the whole idea is a great one. Quicksorts are god-awful at sorting many
> real world types of data. If a list is already sorted, then quicksort
> degenerates into a bubble sort. That's N^2 performance. And pre-sorted
> data is pretty common so you're likely to hit this issue often.

Not quite correct.

Quicksort degenerate into O(n^2) for sorted data *if* the first
or last element is used as pivot.

My code used the middle element.

For the very same reason.

That works super for sorted data.

Ofcourse there still exists some orders that degenerate
into O(n^2), but they are not very likely (unlike the already
sorted order).

Arne
 |  Next  |  Last
Pages: 1 2 3
Prev: adding a new library .jar to your path (netbeans)
Next: Turning off JIT Optimisation