7

私は 0 から 1000000 までのすべての素数を見つけたいと思っています。そのために、私はこの愚かな方法を書きました:

public static boolean isPrime(int n) {
    for(int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

それは私にとって良いことであり、編集は必要ありません。私が次のコードを書いたよりも：

private static ExecutorService executor = Executors.newFixedThreadPool(10);
private static AtomicInteger counter = new AtomicInteger(0);
private static AtomicInteger numbers = new AtomicInteger(0);

public static void main(String args[]) {
    long start = System.currentTimeMillis();
    while (numbers.get() < 1000000) {
        final int number = numbers.getAndIncrement();  // (1) - fast
        executor.submit(new Runnable() {
            @Override
            public void run() {
  //               int number = numbers.getAndIncrement(); // (2) - slow
                if (Main.isPrime(number)) {
                    System.out.println("Ts: " + new Date().getTime() + " " + Thread.currentThread() + ": " + number + " is prime!");
                    counter.incrementAndGet();
                }
            }
        });
    }
    executor.shutdown();
    try {
        executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
        System.out.println("Primes: " + counter);
        System.out.println("Delay: " + (System.currentTimeMillis() - start));
    } catch (Exception e) {
        e.printStackTrace();
    }
}

(1)と(2)の行に注目してください。(1) を有効にするとプログラムは高速に実行されますが、(2) を有効にするとプログラムの動作が遅くなります。

出力は、大きな遅延を伴う小さな部分を示しています

Ts: 1480489699692 Thread[pool-1-thread-9,5,main]: 350431 is prime!
Ts: 1480489699692 Thread[pool-1-thread-6,5,main]: 350411 is prime!
Ts: 1480489699692 Thread[pool-1-thread-4,5,main]: 350281 is prime!
Ts: 1480489699692 Thread[pool-1-thread-5,5,main]: 350257 is prime!
Ts: 1480489699693 Thread[pool-1-thread-7,5,main]: 350447 is prime!
Ts: 1480489711996 Thread[pool-1-thread-6,5,main]: 350503 is prime!

そしてスレッドは等しいnumber値を取得します:

 Ts: 1480489771083 Thread[pool-1-thread-8,5,main]: 384733 is prime!
 Ts: 1480489712745 Thread[pool-1-thread-6,5,main]: 384733 is prime!

オプション (2) がより遅い理由と、AtomicInteger マルチスレッドが安全であるにも関わらず、スレッドが数値に対して等しい値を取得する理由を説明してください。

4

4 に答える 4

9

(2) の場合、最大 11 個のスレッド ( からの 10 個ExecutorServiceとメイン スレッドの合計) が へのアクセスをめぐって競合しますが、AtomicInteger(1) の場合は、メイン スレッドだけがそれにアクセスします。int実際、ケース (1) の場合、 の代わりに使用できますAtomicInteger。

このAtomicIntegerクラスはCASレジスタを使用します。これは、値を読み取り、インクリメントを行い、最初に読み取った値と同じ値が残っている場合は、その値をレジスター内の値と交換する (比較して交換する) ことによって行われます。別のスレッドが値を変更した場合は、成功するまで読み取り - インクリメント - 比較と交換を繰り返します。

利点は、これがロックレスであるため、ロックを使用するよりも潜在的に高速であることです。しかし、激しい競合下ではパフォーマンスが低下します。競合が増えるということは、再試行が増えることを意味します。

編集

@teppic が指摘しているように、別の問題により、ケース (2) がケース (1) よりも遅くなります。ポストされたジョブで数値の増分が発生すると、ループ条件が必要以上に長く true のままになります。エグゼキュータの 10 個のスレッドすべてが、与えられた数が素数であるかどうかを判断するためにどんどん離れていきますが、メイン スレッドは新しいジョブをエグゼキュータにポストし続けます。これらの新しいジョブは、前のジョブが完了するまで数値を増やす機会がありません。そのため、それらがキューにある間numbersは増加せず、その間にメイン スレッドが 1 つ以上のループ ループを完了し、新しいジョブを投稿できます。最終的な結果として、必要な 1000000 よりも多くの求人を作成して掲載することができます。

于 2016-11-30T06:57:04.133 に答える
4

あなたの外側のループは次のとおりです。 while (numbers.get() < 1000000)

これにより、メイン スレッドで ExecutorService に意図したよりも多くの Runnables を送信し続けることができます。

ループを次のように変更してみてください。for(int i=0; i < 1000000; i++)

(他の人が言ったように、明らかに競合の量が増えていますが、余分なワーカースレッドが、あなたが見ている速度低下の大きな要因であると思われます.)

2 番目の質問については、2 つの子スレッドが getAndIncrement の同じ値を参照することは、AtomicInteger の契約に違反していると確信しています。したがって、コードサンプルからは見えない何か他のことが起こっているに違いありません。プログラムの 2 つの別々の実行からの出力が表示されている可能性がありますか?

于 2016-11-30T06:53:12.860 に答える