0

任意の数までのすべての素数を並列に計算して計算しようとしています。isPrime（）は現在の状態から改善できることは承知していますが、主な問題は、結果を格納しているArrayListへのアクセスを同期できないことです。ダミーオブジェクト「m」をインスタンス化して、モニターとして機能し、配列へのアクセスを制御しました。毎回java.util.ConcurrentModificationExceptionが発生するため、明らかにどこかで推論を間違えました。NB：要点

編集：提案後に完了を表示するように更新されました。

import java.util.ArrayList;
public class Main {
    static final int MAX = 100000000;
    static final int THREADS = Runtime.getRuntime().availableProcessors();
    static final int ARRINITSIZE = 100000;
    static ArrayList<Integer> primes = new ArrayList<Integer>(ARRINITSIZE);

    public static void main(String[] args) {
        Thread[] t = new Thread[THREADS];
        PrimeRun.m = new Monitor();

        for (int i=0; i<THREADS; i++) {
            t[i] = new Thread(new PrimeRun(i) );
            t[i].start();
        }

        // wait for threads to finish
        for (int i=0; i<THREADS; i++)
            t[i].join();

        // NOTE: primes will be out of order because of random thread scheduling 
        for (int n : primes)
            System.out.print("" + n + " ");
        System.out.println();
    }

    static boolean isPrime(int n) {
        if (n == 2 || n == 3 || n == 5) return true;
        if (n <= 1 || (n&1) == 0) return false;

        for (int i = 3; i*i <= n; i += 2)
            if (n % i == 0) return false;

        return true;
    }

    synchronized static void addPrime(int n) {
        primes.add(n);
    }

}

class PrimeRun implements Runnable {
    public static Monitor m;
    final int ID;
    public PrimeRun(int i) {
        ID = i;
    }

    public void run() {
    for(int i=0; i < Main.MAX; i++) {
        if(i % Main.THREADS == ID)
            if(Main.isPrime(i)) 
                m.addPrime(i);
        }
    }
}

class Monitor {
    public synchronized void addPrime(int n) {
        Main.addPrime(n);
    }
}

便宜上、antスクリプトを含めました:)

<project default="cmp">
  <target name="cmp"><javac srcdir="." debug="true"/></target>
  <target name="run" depends="cmp"><java classname="Main" classpath="."/></target>
  <target name="cln"><delete><fileset dir="." includes="*.class"/></delete></target>
</project>
4

3 に答える 3

4

素数を次のように宣言するのはどうですか

static List<Integer> primes = Collections.synchronizedList(new ArrayList<Integer>(ARRINITSIZE));

そして、モニターと同期されたブロックを取り除くことができるはずです...ああ、素数を計算するスレッドが終了するまで待ってから、素数リストから値を出力し始める必要があります

編集

これは、スレッドが終了するのを待つだけの変更されたプログラムです。

    import java.util.ArrayList;
    import java.util.List;

    public class Main {
        static final int MAX = 1000;
        static final int THREADS = Runtime.getRuntime().availableProcessors();
        static final int ARRINITSIZE = 100000;
        static ArrayList<Integer> primes = new ArrayList<Integer>(ARRINITSIZE);

    public static void main(String[] args) {
        PrimeRun.m = new Monitor();

        List<Thread> thread = new ArrayList<Thread>();
        for (int i=0; i<THREADS; i++){
            Thread t = new Thread(new PrimeRun(i));
            t.start();
           thread.add(t);
        }

        for (Thread t : thread) {
            if (t.isAlive()){
                try {
                    t.join();
                } catch (InterruptedException e) {

                }
            }

        }

        for (int n : primes)
            System.out.print("" + n + " ");
    }

    static boolean isPrime(int n) {
        if (n <= 1 || (n&1) == 0) return false;
        if (n == 2 || n == 3 || n == 5) return true;

        for (int i = 3; n*n <= i; i += 2)
            if (n % i == 0) return false;

        return true;
    }

    synchronized static void addPrime(int n) {
        primes.add(n);
    }

}

    class PrimeRun implements Runnable {
        public static Monitor m;
        final int ID;
        public PrimeRun(int i) {
            ID = i;
        }

        public void run() {
        for(int i=0; i < Main.MAX; i++) {
            if(i % Main.THREADS == ID)
                if(Main.isPrime(i)) 
                    m.addPrime(i);
            }
        }
    }

    class Monitor {
        public synchronized void addPrime(int n) {
            Main.addPrime(n);
        }
    }
于 2012-07-28T05:58:56.457 に答える
4

ConcurrentModificationException配列に追加している間、配列を反復処理しているために取得します。これは複数のスレッドとは関係がなく、単一のスレッドでも発生します。ただし、特定のケースでは、リストの反復を開始したときにスレッドがまだ素数を追加しているために発生します。これを防ぐには、すべてのスレッドが終了するのを待ってから印刷する必要があります。これを行うには、スレッドの配列を繰り返しjoin()、それぞれを呼び出すことができます。または、 CountdownLatchを使用できます。

Collections.synchronizedList()他の回答で提案されているように、リストを同期させることができます。

于 2012-07-28T06:00:54.817 に答える
1

原因ConcurrentModificationExceptionは同期が悪いわけではありません。その理由は、反復中にリストを変更しているためです。

あなたのコードで見つけた唯一の繰り返しは

for (int n : primes)
      System.out.print("" + n + " ");

これが何が起こるかです。仕事をしてコレクションに要素を追加するいくつかのスレッドを実行しています。スレッドを実行するコードの直後に、リストを反復処理してその要素を出力するコードが続きます。したがって、反復と作業スレッドが同時に実行されます。

これを修正するには、すべての作業スレッドが終了するまで待ってから印刷する必要があります。実際、すべての計算が終了したときにのみ結果を印刷したいと考えています。Thread.join()これを実装する方法を確認してください。

そして、明らかに@maneeshが推奨することを行います。つまりCollections.synchronizedList()、手動同期の代わりに使用します。

于 2012-07-28T06:06:57.630 に答える