1

私はJavaが初めてで、longの2D配列で最大値を見つけるメソッドを作成しようとしています.

このメソッドは、個別のスレッドで各行を検索し、スレッドは共有の現在の最大値を維持します。スレッドは、自身のローカル最大値より大きい値を見つけると、この値を共有ローカル最大値と比較し、現在のローカル最大値と場合によっては共有最大値を適切に更新します。計算のインターリーブ方法に関係なく結果が正しいように、適切な同期が実装されていることを確認する必要があります。

私のコードは冗長で面倒ですが、まず、次の関数があります。

   static long sharedMaxOf2DArray(long[][] arr, int r){

     MyRunnableShared[] myRunnables = new MyRunnableShared[r];
     for(int row = 0; row < r; row++){
       MyRunnableShared rr = new MyRunnableShared(arr, row, r);
       Thread t = new Thread(rr);
       t.start();
       myRunnables[row] = rr;
     }

     return myRunnables[0].sharedMax; //should be the same as any other one (?)

   }

適合したランナブルの場合、私はこれを持っています:

   public static class MyRunnableShared implements Runnable{
     long[][] theArray; 
     private int row; 
     private long rowMax; 
     public long localMax; 
     public long sharedMax; 
     private static Lock sharedMaxLock = new ReentrantLock(); 
     MyRunnableShared(long[][] a, int r, int rm){
        theArray = a; 
        row = r;
        rowMax = rm;
      }
      public void run(){
        localMax = 0;
        for(int i = 0; i < rowMax; i++){
          if(theArray[row][i] > localMax){
            localMax = theArray[row][i];
            sharedMaxLock.lock();
            try{
              if(localMax > sharedMax)
                sharedMax = localMax;
            }
            finally{
              sharedMaxLock.unlock(); 
            }
          } 
        }
      }
    }

このロックの使用は、複数のスレッドが一度に干渉するのを防ぐ安全な方法だとsharedMax思いましたが、同じ入力で非同時最大検出関数をテスト/比較すると、結果が正しくないことがわかりました. 私はちょうど私が言うという事実から問題が発生する可能性があると考えています

...
t.start();
myRunnables[row] = rr; 
...

sharedMaxOf2DArray関数で。おそらく、特定のスレッドは、myRunnables の配列に入れる前に終了する必要があります。そうしないと、間違った sharedMax を「キャプチャ」してしまうのでしょうか? それとも別のものですか？物事のタイミングについてはわかりません..

4

4 に答える 4

1

JavaDocs から:

パブリック インターフェイス Callable

結果を返し、例外をスローする可能性があるタスク。実装者は、call という引数のない単一のメソッドを定義します。

Callable インターフェースは Runnable と似ており、どちらもインスタンスが別のスレッドによって実行される可能性があるクラス用に設計されています。ただし、Runnable は結果を返さず、チェック例外をスローできません。

Callable を使用して、1 つの 1darray から結果を計算し、ExecutorService で終了を待つことができます。Callable の各結果を比較して、最大値を取得できるようになりました。コードは次のようになります。

Random random = new Random(System.nanoTime());
long[][] myArray = new long[5][5];
for (int i = 0; i < 5; i++) {
    myArray[i] = new long[5];
    for (int j = 0; j < 5; j++) {
        myArray[i][j] = random.nextLong();
    }
}

ExecutorService executor = Executors.newFixedThreadPool(myArray.length);
List<Future<Long>> myResults = new ArrayList<>();
// create a callable for each 1d array in the 2d array
    for (int i = 0; i < myArray.length; i++) {
        Callable<Long> callable = new SearchCallable(myArray[i]);
    Future<Long> callResult = executor.submit(callable);
    myResults.add(callResult);
}
// This will make the executor accept no new threads
// and finish all existing threads in the queue
executor.shutdown();
// Wait until all threads are finish
while (!executor.isTerminated()) {
}
// now compare the results and fetch the biggest one
long max = 0;
for (Future<Long> future : myResults) {
    try {
        max = Math.max(max, future.get());
    } catch (InterruptedException | ExecutionException e) {
        // something bad happend...!
        e.printStackTrace();
    }
}
System.out.println("The result is " + max);

そしてあなたの Callable:

public class SearchCallable implements Callable<Long> {

    private final long[] mArray;

    public SearchCallable(final long[] pArray) {
        mArray = pArray;
    }

    @Override
    public Long call() throws Exception {
        long max = 0;
        for (int i = 0; i < mArray.length; i++) {
            max = Math.max(max, mArray[i]);
        }
        System.out.println("I've got the maximum " + max + ", and you guys?");
        return max;
    }

}
于 2012-12-06T07:14:26.457 に答える
1

これがタイプミスかどうかはわかりませんが、実装はインスタンス変数としてRunnable宣言されています。sharedMax

public long sharedMax;

共有のものではなく：

public static long sharedMax;

前者の場合、各 Runnable は独自のコピーを取得し、他の値を「見る」ことはありません。後者に変更すると役立つはずです。または、次のように変更します。

public long[] sharedMax; // array of size 1 shared across all threads

ループの外側でサイズ 1 の配列を作成し、それを各 Runnable に渡して共有ストレージとして使用できるようになりました。

余談ですが、すべてのスレッドがループの反復ごとにロックを保持することで共通の sharedMax 値をチェックするため、ロックの競合が非常に大きくなることに注意してください。これにより、パフォーマンスが低下する可能性があります。測定する必要がありますが、各スレッドに行の最大値を見つけさせてから、最終パスを実行して「最大値の最大値」を見つけることは、実際には同等またはより高速であると推測します。

于 2012-12-06T07:39:06.697 に答える
0

まあ、それは明らかに問題ですが、それが唯一のものであるかどうかを理解するのは難しいです。

へのアクセス(およびこの の読み取り) と、他のスレッドでの の変更との間には、基本的に競合状態があります。thread[0]sharedMaxsharedMax

スケジューラーが、今のところどのスレッドも実行させないと決めたらどうなるか考えてみてください。そのため、スレッドの作成が完了したら、一度も変更せずに答えを返すことになります! (もちろん他にも考えられるシナリオはあります...)

join()回答を返す前にすべてのスレッドを ing することで、これを克服できます。

于 2012-12-06T05:55:14.113 に答える