java - セクションでのスレッド実行

Question

class{

...

     method(x,y){

...

     method(x-1,y);  //own thread for recursion
     method(x,y-1);  //own thread for recursion
     }
}

スレッデッドコードセクションを実行したいのですが、Javaでそのようなセクションに署名するにはどうすればよいですか。

Answer 1

組み込みのJava機能を見たことがありますか？Java 7 を使用している場合、並列再帰は簡単です。

RecursiveTask

javadoc には、古典的なフィボナッチ問題の解決策が含まれています。

更新 配列を合計する例を次に示します。RecursiveTask に入れるのが最も効率的だとは言いませんが、使用方法の良い例です。

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;


public class Sum extends RecursiveTask<Long> {
    private static final long serialVersionUID = 1548240649873455442L;
    private int arr[];
    private int hi;
    private int lo;

    public Sum(int arr[]) {
        this.arr = arr;
        this.lo = 0;
        this.hi = arr.length-1;
    }

    private Sum(int arr[], int lo, int hi) {
        this.arr = arr;
        this.hi = hi;
        this.lo = lo;
    }

    @Override
    protected Long compute() {
        if (lo == hi) {
            return Long.valueOf(arr[lo]);
        }
        else {
            int mid = (hi+lo)/2;
            Sum sumleft = new Sum(arr, lo, mid);
            Sum sumright = new Sum(arr, mid+1, hi);
            sumleft.fork();
            return sumright.compute().longValue() + sumleft.join().longValue();
        }
    }


    public static void main(String args[]) throws Exception {
        ForkJoinPool pool = new ForkJoinPool();
        int arr[] = new int[] { 1, 2, 3, 4, 5 };
        Sum sum = new Sum(arr);
        System.out.println(pool.invoke(sum));
    }

}

ここで注目すべき大きな点:

1. 再帰を停止する方法が必要です (この例では、1 つの要素のみを合計する場合です)。

2. リダクションの片側に .compute() を使用し、反対側に .fork() を使用し、.join() を使用してその値を取得する必要があります。

Answer 2

このようなスレッド化シナリオには注意してください。最初の衝動は、次のようなものを書くことです。

 Thread t1 = new Thread(new Runnable() {
           public void run() {
               method(x-1,y);
           }
       });
 Thread t2 = new Thread(new Runnable() {
           public void run() {
               method(x,y-1);
           }
       });
 t1.start();
 t2.start();

 //...
 t1.join();
 t2.join();

これで目的は達成できますが、残念なことに、このメソッドは再帰的であるため、スレッドの生成はすぐに制御不能になり、システムをオーバーサブスクライブします。これは、スレッドが再帰の各レベルで生成されるためです。

しきい値を設定してから、しきい値に達すると順次呼び出しに切り替える必要があります。

 if(currentLevel < threshold) {
    Thread t1 = new Thread(new Runnable() {
              public void run() {
                  method(x-1,y,currentLevel + 1);
              }
          });
    Thread t2 = new Thread(new Runnable() {
              public void run() {
                  method(x,y-1,currentLevel + 1);
              }
          });
    t1.start();
    t2.start();

    //...
    t1.join();
    t2.join();
 } else {
     method(x-1,y); 
     method(x,y-1); 
 }