Not logged in. Log in with GitHub. About Websheets.

List of all available Websheets


Viewing java/16-threads/FJSort by daveagp@gmail.com. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.
PropertyValue
Description
html markup
shown to student
 
TODO
Public permissions remove
Engine
Template / Reference solution
 
public class FJSort {
   public static void main(String[] args) {
      int SIZE = 2_000_000;
      int[] list = new int[SIZE];
        
      for (int i = 0; i < SIZE; i++)
         list[i] = (int)(Math.random() * Integer.MAX_VALUE);
      int maxProc = Runtime.getRuntime().availableProcessors();
      // timing[i] : time to sort on i processors
      long[] timing = new long[maxProc+1];
      for (int i=1; i<=maxProc; i++)
        timing[i] = parallelMergeSort((int[])list.clone(), i);
 
      for (int i=2; i<=maxProc; i++)
         if (!(timing[i] < timing[i-1]/1.05))
           throw new RuntimeException("More processors should make it faster!");
    }
    
    public static long parallelMergeSort(int[] list, int proc) {
       long startTime = System.currentTimeMillis();
       ForkJoinPool pool = new ForkJoinPool(proc);
       pool.invoke(new SortTask(list));
       pool.shutdown();
       while (!pool.isTerminated()) Thread.yield();
       long time = System.currentTimeMillis() - startTime;
       System.out.println("Time with "+proc+" processors is "+time+" ms");
       return time;
    }  
    
    private static class SortTask extends RecursiveAction {
       private int[] list;
       SortTask(int[] list) { this.list = list; }
        
       @Override
       protected void compute() {
          if (list.length < 2) return; // base case
          // split into halves  
          int[] firstHalf = new int[list.length / 2];
          System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
          int secondHalfLength = list.length - list.length / 2;
          int[] secondHalf = new int[secondHalfLength];
          System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
                
          // recursively sort the two halves
\[
          invokeAll(new SortTask(firstHalf),
                    new SortTask(secondHalf));
\show:
       new SortTask(firstHalf).invoke();
       new SortTask(secondHalf).invoke();
]\
          // merge halves together
          merge(firstHalf, secondHalf, list);
      }
   }
   public static void merge(int[] list1, int[] list2, int[] merged) {
      int i1 = 0, i2 = 0, i3 = 0; // index in list1, list2, out
        
      while (i1 < list1.length && i2 < list2.length) 
         merged[i3++] = (list1[i1] < list2[i2]) ? list1[i1++] : list2[i2++];
      
      // any trailing ends        
      while (i1 < list1.length) merged[i3++] = list1[i1++];
      while (i2 < list2.length) merged[i3++] = list2[i2++];
   }
}
Java test suite
See manual
 
dontRunReference = true;
testMain();
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]
 
["java.util.concurrent.RecursiveAction", "java.util.concurrent.ForkJoinPool"]
remove


Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.