同步访问ArrayList

我想通过并行计算它们来计算任意数量的所有素数。我知道isPrime（）可以从现在改进，但主要问题是我无法同步对存储结果的ArrayList的访问。我已经实例化了一个虚拟对象“m”来充当监视器并控制对数组的访问。很明显，我在某处推理时犯了一个错误，因为每次都得到java.util.ConcurrentModificationException。 NB：gist 同步访问ArrayList

编辑：更新后显示完成建议。

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>

来源

2012-07-28 xst

要评论你的'isPrime（）'方法而不是除以i + = 2，请尝试除以primes.get（i ++）。这会让你在通过3和5之后再除以15。 – gobernador 2012-07-28 06:13:54

@gobernador您的意思是，读取已经计算并以该数字为模的质数的数组？或者你的意思是增加一个不同的值的循环计数器？ – xst 2012-07-28 06:18:00

通过素数低于您测试的数量来模数。这将导致更少的计算，并在质数更少的较高数字上为您提供极大的速度提升。 – gobernador 2012-07-28 18:46:41

如何声明素数为

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

而且你应该能够摆脱监视器和同步块...哦，你将不得不等待直到计算素数到fi的线程从质数列表开始打印值之前，光洁度

编辑

下面是修改程序，其中它只是等待线程完成

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-28 05:58:56 maneesh

我想了解并发编程的血淋淋的细节。否则，我会这样做。 – xst 2012-07-28 06:03:08

所以在Main中，引用应该保留到生成的线程，然后在它们每个上加入（）对吗？ – xst 2012-07-28 06:05:46

查看已编辑的代码答案以等待线程完成 – maneesh 2012-07-28 06:12:09

你得到ConcurrentModificationException因为你遍历数组同时添加到它。它与多线程无关，即使在单线程中也会发生。但在你的具体情况下，它发生的原因是当你开始迭代列表时，线程仍然添加素数。为了防止在打印之前必须等待所有线程完成。要做到这一点，你可以迭代线程数组，并在其中的每一个上调用join()。或者你可以使用CountdownLatch。

根据其他答案的建议，可以通过Collections.synchronizedList()进行同步。

来源

2012-07-28 06:00:54

如果您要在迭代时尝试添加到列表，请先将其转换为数组，然后迭代数组 – MadProgrammer 2012-07-28 06:07:11

原因来自ConcurrentModificationException同步不错。原因是你在迭代过程中修改了列表。

我在你的代码中发现的唯一的迭代

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

这是发生了什么。您正在运行多个执行其工作并将元素添加到集合的线程。运行线程的代码紧接着迭代列表并打印其元素的代码。所以迭代和你的工作线程同时运行。

要解决这个问题，您应该等到所有工作线程完成并打印完毕。事实上，只有在所有计算完成后才打印结果。检查方法Thread.join()来执行此操作。

很明显，@maneesh推荐你，即使用Collections.synchronizedList()而不是你的手动同步。

来源

2012-07-28 06:06:57 AlexR

同步访问ArrayList

回答

相关问题