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);
}
}
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));
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?
EDIT:
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:
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);
}
}
Now it uses HashMap and this is how it works:
- Fill HashMap with keys from 2 to n and false values.
- New thread goes into while loop which is based on
countervariable.Counterrepresents current key. - Increment counter on the begging so new threads doesn't operate on
counterof earlier started thread. - Put
countervalue into temporary variabletmpso we can work even when another thread incrementcounter - Iterate through the HashMap by incrementing
iwithtmp( it is actually jumping on the multiplies of i) and set their values totrue. - All keys which has
truevalue are ignored in print method. Alsocounterskips them when incremented.
The problem is that it still works slower with more threads. What's wrong now?
