SHARE
TWEET

Untitled

a guest Nov 21st, 2011 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class Main {
  2.  
  3.     private static final ForkJoinPool mainPool = new ForkJoinPool();
  4.     public static final int NUMBER = Integer.MAX_VALUE;
  5.  
  6.     public static void main(final String[] args) {
  7.         new Main().doIt();
  8.     }
  9.  
  10.     protected void doIt() {
  11.  
  12.         final List<First> firsts = createFirsts();
  13.         System.out.println("Sequential");
  14.         final Stopwatch sequentialStopWatch = SimonManager.getStopwatch("sequential");
  15.         for (int i = 0; i < 5000; i++) {
  16.             findNumberSequentially(firsts);
  17.         }
  18.         System.out.println(sequentialStopWatch);
  19.         System.out.println("Parallel");
  20.         final Stopwatch parallelStopWatch = SimonManager.getStopwatch("parallel");
  21.         for (int i = 0; i < 5000; i++) {
  22.             findNumberUsingParallelism(firsts);
  23.         }
  24.         System.out.println(parallelStopWatch);
  25.     }
  26.  
  27.     protected List<First> createFirsts() {
  28.         System.out.print("Generating some data...");
  29.         final List<First> firsts = Lists.newArrayList();
  30.         for (int i = 0; i < 10; i++) {
  31.             final First first = new First();
  32.             firsts.add(first);
  33.         }
  34.         final First specialFirst = new First();
  35.         final Second specialSecond = new Second();
  36.         final Third specialThird = new Third(NUMBER);
  37.         specialSecond.addThird(specialThird);
  38.         specialFirst.addSecond(specialSecond);
  39.         firsts.add(specialFirst);
  40.         System.out.println("done!");
  41.         return firsts;
  42.     }
  43.  
  44.     protected void findNumberSequentially(final List<First> firsts) {
  45.         final Split split = SimonManager.getStopwatch("sequential").start();
  46.         doSequentially(firsts);
  47.         split.stop();
  48.     }
  49.  
  50.     protected void doSequentially(final List<First> firsts) {
  51.         for (final First first : firsts) {
  52.             for (final Second second : first.getSeconds()) {
  53.                 for (final Third third : second.getThirds()) {
  54.                     if (third.getValue() == NUMBER) {
  55.                         return;
  56.                     }
  57.                 }
  58.             }
  59.         }
  60.     }
  61.  
  62.     protected void findNumberUsingParallelism(final List<First> firsts) {
  63.         final Split split = SimonManager.getStopwatch("parallel").start();
  64.         doInParallel(firsts);
  65.         split.stop();
  66.     }
  67.  
  68.     protected void doInParallel(final List<First> firsts) {
  69.         for (final First first : firsts) {
  70.             for (final Second second : first.getSeconds()) {
  71.                 if (mainPool.invoke(new FinderTask(second.getThirds()))) {
  72.                     return;
  73.                 }
  74.             }
  75.         }
  76.     }
  77.  
  78. }
  79.  
  80. public class First {
  81.  
  82.     private List<Second> seconds = Lists.newArrayList();
  83.  
  84.     public First() {
  85.         for (int i = 0; i < 100; i++) {
  86.             final Second second = new Second();
  87.             seconds.add(second);
  88.         }
  89.     }
  90.  
  91.     public void setSeconds(final List<Second> seconds) {
  92.         this.seconds = seconds;
  93.     }
  94.  
  95.     public void addSecond(final Second second) {
  96.         seconds.add(second);
  97.     }
  98.  
  99.     public List<Second> getSeconds() {
  100.         return seconds;
  101.     }
  102.  
  103. }
  104.  
  105. public class Second {
  106.  
  107.     private List<Third> thirds = Lists.newArrayList();
  108.  
  109.     public Second() {
  110.         for (int i = 0; i < 50000; i++) {
  111.             final Third third = new Third(i);
  112.             thirds.add(third);
  113.         }
  114.     }
  115.  
  116.     public void setThirds(final List<Third> thirds) {
  117.         this.thirds = thirds;
  118.     }
  119.  
  120.     public void addThird(final Third third) {
  121.         thirds.add(third);
  122.     }
  123.  
  124.     public List<Third> getThirds() {
  125.         return thirds;
  126.     }
  127.  
  128. }
  129.  
  130.  
  131. public class Third {
  132.  
  133.     private final int value;
  134.  
  135.     public Third(final int value) {
  136.         this.value = value;
  137.     }
  138.  
  139.     public int getValue() {
  140.         return value;
  141.     }
  142.  
  143. }
  144.  
  145. public class FinderTask extends RecursiveTask<Boolean> {
  146.  
  147.     private static final long serialVersionUID = 8711505823183192823L;
  148.     private static final int THRESHOLD = 100;
  149.     private final List<Third> thirds;
  150.  
  151.     public FinderTask(final List<Third> thirds) {
  152.         this.thirds = thirds;
  153.     }
  154.  
  155.     @Override
  156.     protected Boolean compute() {
  157.         if (thirds.size() < THRESHOLD) {
  158.             return solveSequentially();
  159.         }
  160.         final List<List<Third>> partitioned = Lists.partition(thirds, thirds.size() / 2);
  161.         final FinderTask[] finderTasks = new FinderTask[partitioned.size()];
  162.         for (int i = 0; i < partitioned.size(); i++) {
  163.             finderTasks[i] = new FinderTask(partitioned.get(i));
  164.         }
  165.         invokeAll(finderTasks);
  166.         for (final FinderTask finderTask : finderTasks) {
  167.             if (finderTask.isCompletedNormally() && finderTask.getRawResult()) {
  168.                 return true;
  169.             }
  170.         }
  171.         return false;
  172.     }
  173.  
  174.     private boolean solveSequentially() {
  175.         for (final Third third : thirds) {
  176.             if (third.getValue() == Main.NUMBER) {
  177.                 return true;
  178.             }
  179.         }
  180.         return false;
  181.     }
  182.  
  183. }
  184.  
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top