我想写筛埃拉托色尼的工作，并会使用线程的具体数量。我想通了，它会工作方式如下： 对于2个线程最多17。 线程1需要2，并开始从列表中删除多个的2。并行线程2需要3并且做相同的。在那之后线程1需要5（因为没有在列表无4）和线程2需要7等等，直到达到终点。 我写了下面这段code：

I wanted to write sieve of Eratosthenes which will work using specific number of threads. I figured out, that it will work in following way: For 2 threads up to 17. Thread-1 takes 2, and starts to remove multiple of 2 from List. Parallel Thread-2 takes 3 and does the same. After that Thread-1 takes 5( because there is no 4 in List) and Thread-2 takes 7 and so on until they reach end. I wrote following piece of code:

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);
    }
}

这code的工作，但我说的时间测量的工具我的主类：

This code works, but I added time measurement "tool" to my main class:

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个线程。任何人都可以解释我为什么？

The problem is that running this with 2 threads is slower than running with 1 thread, and 3 threads are slower than 2 threads. Could anyone explain me, why?

编辑：

有一个关于这重要的事情。我并不需要它尽可能快，因为它可以做到的。我需要工作线程的原因之一。我的老师要进行比较与1，2 ... n个线程运行同一程序的运行时间。结果应该看起来像这图。

There is one important thing about that. I don't need it to be done as fast as it can be. I need it working on Threads for one reason. My Teacher wants to compare runtimes of running same program with 1, 2 .. n threads. Results should look like in this graph.

EDIT2：

我已经重写code到以下

I have rewritten code to following

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的，这是它如何工作的：

Now it uses HashMap and this is how it works:

填写的HashMap与键2至n和假值。 新线程进入while循环是基于柜台变量。 计数器重presents当前关键。 在乞讨，以便新主题递增计数器不上柜台早期的工作开始线程。 把柜台值到临时变量 TMP 这样我们就可以工作，即使另一个线程增量柜台 通过增加我与 TMP （它实际上是跳对我的乘）遍历HashMap中和其值设置为真。 所有按键具有真的价值被忽略的打印方式。此外柜台跳过它们加时。 Fill HashMap with keys from 2 to n and false values. New thread goes into while loop which is based on counter variable. Counter represents current key. Increment counter on the begging so new threads doesn't operate on counter of earlier started thread. Put counter value into temporary variable tmp so we can work even when another thread increment counter Iterate through the HashMap by incrementing i with tmp ( it is actually jumping on the multiplies of i) and set their values to true. All keys which has true value are ignored in print method. Also counter skips them when incremented.

现在的问题是，它仍然工作的慢有更多的线程。有什么不对呢？

The problem is that it still works slower with more threads. What's wrong now?

推荐答案

这个错误是简单的比我第一个念头。您的所有线程都在做同样的事情，所以每个线程做更多的工作。为了使多线程程序的工作速度更快，你要瓜分了工作，这必须要同时进​​行。

The mistake is simpler than I first thought. All your threads are doing the same thing so each thread does more work. To make a multi-threaded program work faster you have to divide up the work, which has to be performed concurrently.

当你有一个线程访问的数据结构，它可以在一个核心的速度最快的高速缓存，使用多线程，他们需要协调他们的行动而且由于大部分的工作正在更新的数据结构，很多时间被丢失的开销。这就是即使你的数据结构不是线程安全的情况下，有可能有一个损坏的结果。

When you have one thread accessing a data structure, it can be in the fastest cache of one core, use multiple threads and they need to co-ordinate their actions and since most of the work is updating the data structure, a lot of time is lost as overhead. This is the case even though your data structure is not thread safe and is likely to have a corrupted result.

BTW更新一个ArrayList是非常昂贵的，并使用一个集合的对象也是一个负担。

BTW updating an ArrayList is very expensive and using a collection objects is also an overhead.

您将获得使用位集合，只是一个线程更快的结果。

You will get a much faster result using a BitSet and just one thread.

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，211，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， 1019，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}

87 micro-seconds to perform {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, 211, 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, 1019, 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}