Last active
October 10, 2016 02:12
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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