How to limit threads in a Java QuickSort algorithm.
864501May 25 2011 — edited Jun 2 2011With the following piece of code, I quickly run into OutOfMemory exceptions, since the code starts creating Threads exponentially. However, after waiting for a long time (for all the exception texts to print out, obviously making it slower than running it with one thread only), the program eventually ends with the correct result. Is there a way to run the code as is, but making sure that no more that x threads are running at a time?
things I have tried:
- sleeping the current thread - makes it slower than one-thread.
- looping blank while Thread.activeCount() > x - doesnt work at all
- suspending resuming threads based on the activeCount - doesnt work too
Code:
import java.util.*;
import java.io.*;
public class ThreadedSort extends Thread{
private ArrayList<Integer> _list;
public ThreadedSort()
{
_list = new ArrayList<Integer>();
}
public ThreadedSort(ArrayList<Integer> List)
{
_list = List;
}
public void run()
{
threadQuickSort();
}
public void threadQuickSort()
{
try{
if (_list.size() < 2)
return;
Integer pivot = new Integer(_list.get(_list.size()-1));
ArrayList<Integer> left = new ArrayList<Integer>();
ArrayList<Integer> right = new ArrayList<Integer>();
//ListIterator iter = arr.listIterator();
// *** optimize here
for (int i = 0; i < _list.size()-1; i++) {
Integer next = (Integer)_list.get(i);
if (next <= pivot)
left.add(next);
else
right.add(next);
}
ThreadedSort LeftThread = new ThreadedSort(left);
ThreadedSort RightThread = new ThreadedSort(right);
// System.out.println(Thread.currentThread().getName()+" --> "+Thread.activeCount());
// Thread.sleep(4000);
LeftThread.start();
RightThread.start();
// System.out.println(Thread.currentThread().getName()+" --> "+Thread.activeCount());
LeftThread.join();
RightThread.join();
_list.clear();
list.addAll(LeftThread.list);
_list.add(pivot);
list.addAll(RightThread.list);
}catch (InterruptedException ie) { ie.printStackTrace(); }
return;
}
public static void main(String[] args) { ///////////////////////////////////////////
Random rand = new Random();
ArrayList arr1 = new ArrayList();
long before_threadedQuickSort, after_threadedQuickSort;
try{
FileWriter fout = new FileWriter("out.txt");
BufferedWriter bw = new BufferedWriter(fout);
before_populate = System.currentTimeMillis();
for (int i = 0; i< 2000; i++){//***
arr1.add(rand.nextInt(2000000));
}
after_populate = System.currentTimeMillis();
ThreadedSort sorter3 = new ThreadedSort(new ArrayList(arr1));
before_threadedQuickSort = System.currentTimeMillis();
sorter3.start();
sorter3.join();
after_threadedQuickSort = System.currentTimeMillis();
bw.write("time for threadedQuickSort: " + (after_threadedQuickSort - before_threadedQuickSort)); bw.newLine();
bw.newLine();
arr1.clear();
}
bw.close();
}catch (Exception IOException){};
System.out.printf("\n\n");
} //end of main
} //end of class