Я хотел написать решето Эратосфена, которое будет работать с использованием определенного количества потоков. Я понял, что это будет работать следующим образом: Для 2 потоков до 17. Поток-1 берет 2 и начинает удалять кратные 2 из списка. Параллельный поток-2 берет 3 и делает то же самое. После этого Thread-1 берет 5 (потому что в списке нет 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 потоками. Может ли кто-нибудь объяснить мне, почему?
ИЗМЕНИТЬ:
В этом есть одна важная вещь. Мне не нужно, чтобы это было сделано так быстро, как это возможно. Мне нужно, чтобы он работал с потоками по одной причине. Мой учитель хочет сравнить время выполнения одной и той же программы с 1, 2 .. n потоками. Результаты должны выглядеть так, как показано на этом графике.
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, и вот как это работает:
- Заполните HashMap ключами от 2 до n и ложными значениями.
- Новый поток переходит в цикл while, основанный на переменной
counter
.Counter
представляет текущий ключ. - Увеличивайте счетчик при попрошайничестве, чтобы новые потоки не работали с
counter
ранее запущенным потоком. - Поместите значение
counter
во временную переменнуюtmp
, чтобы мы могли работать, даже когда другой поток увеличиваетcounter
- Переберите HashMap, увеличив
i
наtmp
(на самом деле это перескакивание на умножение i) и установите их значения наtrue
. - Все ключи, имеющие значение
true
, игнорируются в методе печати. Такжеcounter
пропускает их при увеличении.
Проблема в том, что он по-прежнему работает медленнее с большим количеством потоков. Что случилось сейчас?