Results 1 to 7 of 7
  1. #1
    roise_r is offline Member
    Join Date
    May 2011
    Posts
    9
    Rep Power
    0

    Default How to limit threads in a Java QuickSort algorithm.

    With 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:
    Java 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

  2. #2
    kjkrum's Avatar
    kjkrum is offline Senior Member
    Join Date
    Apr 2011
    Location
    Tucson, AZ
    Posts
    1,060
    Rep Power
    6

    Default

    Try using a thread pool. Instead of making your ThreadedSort extend Thread, make it implement Runnable. Then, instead of recursively creating new threads, recursively add runnable tasks to the thread pool.

    Check out this tut: Thread Pools (The Java™ Tutorials > Essential Classes > Concurrency)
    Last edited by kjkrum; 05-27-2011 at 11:36 PM. Reason: typo/thinko
    Get in the habit of using standard Java naming conventions!

  3. #3
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,882
    Rep Power
    25

    Default

    Does the posted code compile? I get an error because of mismatched {}s

    After correcting the errors, I noticed that the results of the sort were not verified in the code.
    How do you know the sort worked?
    Last edited by Norm; 05-28-2011 at 03:49 AM.

  4. #4
    roise_r is offline Member
    Join Date
    May 2011
    Posts
    9
    Rep Power
    0

    Default

    so I finally devised a code where I get marginal performance improvement. I still cant get my mind around the fact that even with 16 threads all the improvement I get for a list size of 5000000 elements where the values can range from 0-2000000 is about 30%. I can see in the log diagram for processor activity that all 16 threads are getting involved, but not in a consistent basis (sometimes they'll all be active, sometimes only eight will be active, sometimes only one). The other thing that I noticed is that just by declaring a Thread object inside my main algorithm ( Thread thread1 = new Thread(); ), not actually starting it or using it in anyway, just by creating it - the runtime increases by 70%-100%. So the question is, when is multi-threading really applicable ??!

    Java 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;
    	}
    	
    	@Override
    	public void run()
    	{
    		if (Thread.activeCount() >= 16) //***
    			quickSort();
    		else
    			threadQuickSort();
    	}
    	
        public void threadQuickSort()
        {
    		try{
            if (_list.size() < 2)
                return;
    
    		ThreadedSort LeftThread = new ThreadedSort();
    		ThreadedSort RightThread = new ThreadedSort();
    		
            Integer pivot = new Integer(_list.get(_list.size()-1));
            
            for (int i = 0; i < _list.size()-1; i++) {
    			Integer next = (Integer)_list.get(i);
    			if (next <= pivot)
    				LeftThread._list.add(next);
    			else
    				RightThread._list.add(next);
    		}
    		_list.clear();
    		
    		LeftThread.start();
    		RightThread.run();
    		LeftThread.join();
    		
    		_list.addAll(LeftThread._list);
    		_list.add(pivot);
    		_list.addAll(RightThread._list);
    		LeftThread._list.clear();
    		RightThread._list.clear();
    		}catch (InterruptedException ie) { ie.printStackTrace(); }
    		return;
        }
    	
        public void quickSort()
        {
    		if (_list.size() < 2)
                return;
    
            Integer pivot = new Integer(_list.get(_list.size()-1));
            
    		ThreadedSort temp_thread = new ThreadedSort();
    		ArrayList<Integer> temp_arr = new ArrayList<Integer>();
    
            for (int i = 0; i < _list.size()-1; i++) {
    			Integer next = (Integer)_list.get(i);
    			if (next <= pivot)
    				temp_thread._list.add(next);
    			else
    				temp_arr.add(next);
    		}
    		_list.clear();
    		
    		temp_thread.run();
    		_list.addAll(temp_thread._list);
    		_list.add(pivot);
    		temp_thread._list = temp_arr;
    		temp_thread.run();
    		_list.addAll(temp_thread._list);
    		temp_thread._list.clear();
    		temp_arr.clear();
    
    		return;
        }
    
        public static void main(String[] args) { ///////////////////////////////////////////
    
    		try{
    		FileWriter writer = new FileWriter("out.txt");
    		BufferedWriter bw = new BufferedWriter(writer);
    		
    		Random rand = new Random();
    		ArrayList arr1 = new ArrayList();
    
    		long before_populate, after_populate, before_threadedQuickSort, after_threadedQuickSort;
    
    		before_populate = System.currentTimeMillis();
    		for (int i = 0; i< 2000000; i++){//***
    			arr1.add(rand.nextInt(2000000));
    		}
    		after_populate = System.currentTimeMillis();
    
    		ThreadedSort sorter1 = new ThreadedSort(new ArrayList(arr1));
    
    		before_threadedQuickSort = System.currentTimeMillis();
    		sorter1.run();
    		after_threadedQuickSort = System.currentTimeMillis();
    
    		bw.write("time for population: " + (after_populate - before_populate)); bw.newLine();
    		bw.write("time for threadedQuickSort: " + (after_threadedQuickSort - before_threadedQuickSort)); 
    		bw.newLine();
    		bw.newLine();
    		
    		bw.close();
    
    		}catch (Exception IOException){};
    		System.out.printf("\n\n");
        } //end of main
    
    } //end of class

  5. #5
    kjkrum's Avatar
    kjkrum is offline Senior Member
    Join Date
    Apr 2011
    Location
    Tucson, AZ
    Posts
    1,060
    Rep Power
    6

    Default

    The number of threads that can actually execute simultaneously is limited by the number of CPUs/cores/threads in your hardware. (I'm not sure what a CPU "thread" is, but I've seen CPUs described in advertisements as "2 cores/4 threads".) If you create more threads than that, you'll probably actually decrease performance because of the extra overhead involved in switching threads in and out of the CPU. The only good reason to create more threads than your hardware can run is if your program makes more sense that way.
    Get in the habit of using standard Java naming conventions!

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,882
    Rep Power
    25

    Default

    Does this code actually sort the items in order? Did you test that the array is sorted?

    If I reduce the number to sort to 200, this is the results:

    arr1=[143, 0, 158, 23, 116, 39, 33, 164, 192, 185, 90, 68, 32, 150, 121, 140, 13, 45, 162, 70, 175, 106, 97, 110, 70, 72, 58, 185, 132, 71, 109, 196, 79, 170, 198, 6, 138, 73, 178, 131, 171, 54, 118, 47, 151, 29, 34, 83, 114, 92, 51, 198, 139, 181, 54, 99, 147, 53, 47, 67, 86, 98, 1, 175, 42, 29, 25, 69, 140, 121, 83, 84, 107, 160, 150, 117, 108, 113, 27, 152, 52, 167, 96, 24, 12, 73, 52, 108, 46, 9, 107, 67, 174, 20, 160, 91, 36, 93, 122, 102, 134, 14, 183, 50, 19, 196, 54, 180, 90, 157, 177, 32, 176, 169, 31, 143, 8, 50, 143, 29, 116, 18, 160, 125, 98, 160, 126, 36, 187, 118, 190, 79, 61, 185, 179, 50, 79, 54, 169, 71, 4, 174, 183, 182, 89, 46, 18, 127, 65, 29, 124, 129, 193, 194, 3, 30, 141, 170, 181, 133, 112, 27, 193, 11, 59, 72, 73, 144, 45, 178, 173, 170, 80, 191, 153, 72, 76, 65, 126, 124, 125, 85, 21, 29, 96, 175, 71, 8, 123, 135, 59, 107, 73, 34, 87, 183, 141, 31, 79, 151]
    Last edited by Norm; 06-02-2011 at 03:01 PM.

  7. #7
    kjkrum's Avatar
    kjkrum is offline Senior Member
    Join Date
    Apr 2011
    Location
    Tucson, AZ
    Posts
    1,060
    Rep Power
    6

    Default

    I wanted to add that another good reason to use threads is to keep your program responsive during blocking, slow, or unpredictable I/O. But the point is, threads are not a panacea for better performance, and often actually hurt, even when an algorithm is distributable.
    Get in the habit of using standard Java naming conventions!

Similar Threads

  1. How to limit characters textbox in java
    By rjagan in forum New To Java
    Replies: 11
    Last Post: 03-28-2011, 11:09 PM
  2. setting memory limit for java?
    By MuslimCoder in forum New To Java
    Replies: 1
    Last Post: 08-26-2010, 07:09 PM
  3. Boggled by this, Fast QuickSort Algorithm
    By gcampton in forum New To Java
    Replies: 0
    Last Post: 12-08-2009, 04:07 PM
  4. quicksort program
    By jvasilj1 in forum New To Java
    Replies: 5
    Last Post: 03-03-2009, 04:47 AM
  5. Quicksort
    By little_polarbear in forum New To Java
    Replies: 12
    Last Post: 07-12-2008, 10:20 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •