Skip to content

Instantly share code, notes, and snippets.

@SH4DY
Last active October 10, 2016 02:12
Show Gist options
  • Save SH4DY/749c5caf88c9b7f485dd to your computer and use it in GitHub Desktop.
Save SH4DY/749c5caf88c9b7f485dd to your computer and use it in GitHub Desktop.
Find the greatest number in an array with a multi-threaded fork/join approach
/**
* Find the greatest number in an array with a multi-threaded fork/join approach.
*
* This is a simple recursive divide&conquer approach to search through a list
* and return the max-element. It is using a subclass of java.util.concurrent.ForkJoinTask
* (namely RecursiveTask<V>).
*
* Theoretical aspect: Amdahl's Law.
* Possible speedup with n processors: S(n) = 1 / (B + 1-B*(1/n))
* where B is the fractal of the programm which can only be
* executed SERIALLY.
*
* Throws an exception when invoked with an empty list.
* Created by shady on 03/04/15.
*/
public class Multithreading {
public static void main(String[] args){
new Multithreading().compute();
}
public void compute(){
Integer[] ints = {3,2,5,7,1};
List<Integer> list = Arrays.asList(ints);
ForkJoinPool pool = new ForkJoinPool();
Integer result = pool.invoke(new DividerTask(list));
System.out.println(result);
}
class DividerTask extends RecursiveTask<Integer>{
List<Integer> list;
public DividerTask(List list){
this.list = list;
}
@Override
protected Integer compute(){
if(list.size() > 2){
int mid = list.size()/2;
List<Integer> list1 = list.subList(0,mid);
List<Integer> list2 = list.subList(mid,list.size());
DividerTask dt1 = new DividerTask(list1);
dt1.fork();
DividerTask dt2 = new DividerTask(list2);
dt2.fork();
Integer res1 = dt1.join();
Integer res2 = dt2.join();
return (res1 > res2 ? res1 : res2);
}
if(list.size() == 2){
Integer res1 = list.get(0);
Integer res2 = list.get(1);
return (res1 > res2 ? res1 : res2);
}
return list.get(0);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment