埃拉托色尼并行筛 - Java 多线程

我想编写埃拉托斯特尼筛法，它将使用特定数量的线程来工作。我发现，它将按以下方式工作： 2 个线程，最多 17 个。 Thread-1 获取 2，并开始从 List 中删除 2 的倍数。并行线程 2 需要 3 个线程并执行相同的操作。之后，Thread-1 取 5（因为 List 中没有 4），Thread-2 取 7，依此类推，直到到达末尾。 我写了下面一段代码：

private List<Integer> array = new ArrayList<Integer>();
private List<Integer> results = new ArrayList<Integer>();
public synchronized void run(){
    while(array.size() > 0){
        Integer tmp = array.get(0);
        for(int i = 1; i < array.size(); i++){
            if( (array.get(i).intValue() % tmp.intValue()) == 0)
                array.remove(i);
        }
        results.add(array.get(0));
        array.remove(0);
    }
}

public void setArray(int x){
    for(int i = 2; i < x; i++)
        array.add(Integer.valueOf(i));
}
public void printArray(){
    for(Integer i: results){
        System.out.println(i);
    }
}

这段代码有效，但我在我的主类中添加了时间测量“工具”：

ThreadTask task = new ThreadTask();
task.setArray(5000);
Long beg = new Date().getTime();
for(int i = 0; i < 3;i++){
    new Thread(task).start();
}
Long sleep = 1000L;
Thread.sleep(sleep);// I am sleeping main thread to wait until other Threads are done
task.printArray();
System.out.println("Time is "+(new Date().getTime()-beg-sleep));

问题是用 2 个线程运行比用 1 个线程运行要慢，而 3 个线程比用 2 个线程运行慢。谁能给我解释一下，为什么？

EDIT:

其中有一件重要的事情。我不需要尽快完成它。我需要它在线程上工作有一个原因。我的老师想要比较使用 1、2 .. n 个线程运行同一程序的运行时间。结果应该类似于this http://pl.wikipedia.org/wiki/Plik%3aParallelization_graph.jpg graph.

EDIT2:

我已将代码重写为以下内容

private HashMap<Integer,Boolean> array = new HashMap<Integer,Boolean>();
private int counter = 1;
private int x;
public void run(){
    while(counter < x-1){
        do{
            counter++;
        }
        while( array.get(counter));
        int tmp = counter;
        for(int i = tmp; i < array.size(); i+=tmp){
            if( i!= tmp)
                array.put(i,true);
        }
        try{
        Thread.sleep(0L, 1);
        }
        catch (Exception e){}
    }
}

public void setArray(int x){
    this.x = x;
    for(int i = 2; i < x; i++)
        array.put(i, false);
}
public void printArray(){

    for(int i = 2; i < array.size();i++){
        if( !array.get(i))
        System.out.println(i);

    }
}

现在它使用 HashMap，它的工作原理如下：

1. 用 2 到 n 的键和 false 值填充 HashMap。
2. 新线程进入 while 循环，该循环基于counter多变的。Counter代表当前键。
3. 请求时增加计数器，这样新线程就不会运行counter较早启动的线程。
4. Put counter值存入临时变量tmp所以即使当另一个线程增加时我们也可以工作counter
5. 通过递增来迭代 HashMapi with tmp（它实际上是在 i 的倍数上跳跃）并将它们的值设置为true.
6. 所有具有true值在 print 方法中被忽略。还counter递增时跳过它们。

问题是它仍然有效slower有更多线程。现在怎么了？

这个错误比我最初想象的要简单。所有线程都在做同样的事情，因此每个线程都会做更多的工作。为了使多线程程序运行得更快，您必须划分工作，这些工作必须同时执行。

当您有一个线程访问数据结构时，它可以位于一个核心最快的缓存中，使用多个线程，它们需要协调它们的操作，并且由于大部分工作都是更新数据结构，因此很多时间都在损失为开销。即使您的数据结构不是线程安全的并且可能会产生损坏的结果，情况也是如此。

顺便说一句，更新 ArrayList 的成本非常高，并且使用集合对象也是一种开销。

使用 BitSet 和一个线程，您将获得更快的结果。

public class BitSetSieveMain {
    private final BitSet set;
    private final int size;

    public BitSetSieveMain(int x) {
        size = x + 1;
        set = new BitSet(size);
        set.flip(2, size);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            long start = System.nanoTime();
            BitSetSieveMain bitSetSieveMain = new BitSetSieveMain(5000);
            bitSetSieveMain.sieve();
            long time = System.nanoTime() - start;
            System.out.println(time / 1000 + " micro-seconds to perform " + bitSetSieveMain);
        }
    }

    public void sieve() {
        int i = 2;
        do {
            for (int j = i*2; j < size; j += i)
                set.clear(j);
            i = set.nextSetBit(i+1);
        } while (i > 0);
    }

    public String toString() {
        return set.toString();
    }
}

最后打印

执行需要 87 微秒 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 21 1 、 223、 227、 229、 233、 239、 241、 251、 257、 263、 269、 271、 277、 281、 283、 293、 307、 311、 313、 317、 331、 337、 347、 349、 353、第359章、 367、 373、 379、 383、 389、 397、 401、 409、 419、 421、 431、 433、 439、 443、 449、 457、 461、 463、 467、 479、 487、 491、 499、 503、 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,第673章, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,第853章, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 10 19, 1021 、 1031、1033、1039、1049、1051、1061、1063、1069、1087、1091、1093、1097、1103、1109、1117、1123、1129、1151、1153、1163、 1171、1181、1187、1193、1201 、 1213、 1217、 1223、 1229、 1231、 1237、 1249、 1259、 1277、 1279、 1283、 1289、 1291、 1297、 1301、 1303、 1307、 1319、 1321、 1327、 1361、1367、1373、1381、1399 、 1409、 1423、 1427、 1429、 1433、 1439、 1447、 1451、 1453、 1459、 1471、 1481、 1483、 1487、 1489、 1493、 1499、 1511、 1523、 1531、 1543, 1549, 1553, 1559, 1567 , 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747 , 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913年、1931年、1933年、1949年、1951年, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137 、 2141、2143、2153、2161、2179、2203、2207、2213、2221、2237、2239、2243、2251、2267、2269、2273、2281、2287、2293、2297、 2309、2311、2333、2339、2341 、 2347、2351、2357、2371、2377、2381、2383、2389、2393、2399、2411、2417、2423、2437、2441、2447、2459、2467、2473、2477、 2503、2521、2531、2539、2543 、 2549、2551、2557、2579、2591、2593、2609、2617、2621、2633、2647、2657、2659、2663、2671、2677、2683、2687、2689、2693、 2699、2707、2711、2713、2719 、 2729、2731、2741、2749、2753、2767、2777、2789、2791、2797、2801、2803、2819、2833、2837、2843、2851、2857、2861、2879、 2887, 2897, 2903, 2909, 2917 , 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109、3119、3121、3137、3163 、 3167、 3169、 3181、 3187、 3191、 3203、 3209、 3217、 3221、 3229、 3251、 3253、 3257、 3259、 3271、 3299、 3301、 3307、 3313、 3319、 3323, 3329, 3331, 3343, 3347 、 3359、 3361、 3371、 3373、 3389、 3391、 3407、 3413、 3433、 3449、 3457、 3461、 3463、 3467、 3469、 3491、 3499、 3511、 3517、 3527、 3529, 3533, 3539, 3541, 3547 、 3557、 3559、 3571、 3581、 3583、 3593、 3607、 3613、 3617、 3623、 3631、 3637、 3643、 3659、 3671、 3673、 3677、 3691、 3697、 3701、 3709, 3719, 3727, 3733, 3739 、 3761、 3767、 3769、 3779、 3793、 3797、 3803、 3821、 3823、 3833、 3847、 3851、 3853、 3863、 3877、 3881、 3889、 3907、 3911、 3917、 3919, 3923, 3929, 3931, 3943 、 3947、 3967、 3989、 4001、 4003、 4007、 4013、 4019、 4021、 4027、 4049、 4051、 4057、 4073、 4079、 4091、 4093、 4099、 4111、 4127、 4129、4133、4139、4153、4157 、 4159、 4177、 4201、 4211、 4217、 4219、 4229、 4231、 4241、 4243、 4253、 4259、 4261、 4271、 4273、 4283、 4289、 4297、 4327、 4337、 4339、4349、4357、4363、4373 、 4391、 4397、 4409、 4421、 4423、 4441、 4447、 4451、 4457、 4463、 4481、 4483、 4493、 4507、 4513、 4517、 4519、 4523、 4547、 4549、 4561, 4567, 4583, 4591, 4597 、 4603、 4621、 4637、 4639、 4643、 4649、 4651、 4657、 4663、 4673、 4679、 4691、 4703、 4721、 4723、 4729、 4733、 4751、 4759、 4783、 4787, 4789, 4793, 4799, 4801 、 4813、 4817、 4831、 4861、 4871、 4877、 4889、 4903、 4909、 4919、 4931、 4933、 4937、 4943、 4951、 4957、 4967、 4969、 4973、 4987、 4993, 4999}