Question

Create a Java program with threads that looks through a vary large array (100,000,000 elements) to find the smallest number in that array. You should track the current lowest value seen in a single, shared value. You should also track the time taken, comparing the amount of time for 1, 2, 4 and more threads. Fairly precise timing can be obtained by using the System.nanoTime() method. For example, it's taking my poor computer over 1 second to fill my array with random numbers:

Answer 1

Answer:

See explaination

Explanation:

import java.util.Random;

public class Sample{

static class MinMax implements Runnable{

int []arr;

int start,end,min,max;

MinMax(int[]arr, int start,int end){

this.start=start;

this.end=end;

min=Integer.MAX_VALUE;

max=Integer.MIN_VALUE;

this.arr=arr;

}

atOverride

public void run() {

for(int i=start;i<=end;i++){ //search min and max form strant to end index

min=Math.min(min,arr[i]);

max=Math.max(max, arr[i]);

}

}

}

public static void main(String[] args) throws Exception{

long beginTime = System.nanoTime();

Random gen = new Random();

int n=100000000;

int[] data = new int[n]; //generate and fill random numbers

for(int i = 0; i < data.length; i++) {

data[i] = gen.nextInt()%1000000;

}

long endTime = System.nanoTime();

System.out.println("Done filling the array. That took " + (endTime - beginTime)/1000000000f + " seconds.");

//-----------------------------------------

System.out.println("Using 1 thread"); //1 thread

MinMax m1=new MinMax(data,0,n-1); //class object

Thread t1=new Thread(m1); //new thread

beginTime=System.nanoTime(); //start timer

t1.start(); //start thread

t1.join(0); //wait until thread finishes

endTime=System.nanoTime(); //end timer

System.out.println("Min,Max: "+m1.min+","+m1.max); //print minimum and maximum

System.out.println("Time using 1 thread " + (endTime - beginTime)/1000000000f + " seconds."); //print time taken

//-----------------------------------------

System.out.println("Using 2 thread");

m1=new MinMax(data,0,n/2);

MinMax m2=new MinMax(data,n/2+1,n-1);

t1=new Thread(m1);

Thread t2=new Thread(m2);

beginTime=System.nanoTime();

t1.start();

t2.start();

t1.join(0);

t2.join(0);

endTime=System.nanoTime();

System.out.println("Min,Max: "+ Math.min(m1.min,m2.min)+","+Math.max(m1.max,m2.max));

System.out.println("Time using 2 thread " + (endTime - beginTime)/1000000000f + " seconds.");

//-----------------------------------------

System.out.println("Using 3 thread");

m1=new MinMax(data,0,n/3);

m2=new MinMax(data,n/3+1,2*n/3);

MinMax m3=new MinMax(data,2*n/3+1,n-1);

t1=new Thread(m1);

t2=new Thread(m2);

Thread t3=new Thread(m3);

beginTime=System.nanoTime();

t1.start();

t2.start();

t3.start();

t1.join(0);

t2.join(0);

t3.join(0);

endTime=System.nanoTime();

System.out.println("Min,Max: "+ Math.min(Math.min(m1.min,m2.min),m3.min)+","+Math.max(Math.max(m1.max,m2.max),m3.max));

System.out.println("Time using 3 thread " + (endTime - beginTime)/1000000000f + " seconds.");

//-----------------------------------------

System.out.println("Using 4 thread");

m1=new MinMax(data,0,n/4);

m2=new MinMax(data,n/4+1,2*n/4);

m3=new MinMax(data,2*n/4+1,3*n/4);

MinMax m4=new MinMax(data,3*n/4+1,n-1);

t1=new Thread(m1);

t2=new Thread(m2);

t3=new Thread(m3);

Thread t4=new Thread(m4);

beginTime=System.nanoTime();

t1.start();

t2.start();

t3.start();

t4.start();

t1.join(0);

t2.join(0);

t3.join(0);

t4.join(0);

endTime=System.nanoTime();

System.out.println("Min,Max: "+ Math.min(Math.min(m1.min,m2.min),Math.min(m3.min,m4.min))+","+Math.max(Math.max(m1.max,m2.max),Math.max(m3.max,m4.max)));

System.out.println("Time using 4 thread " + (endTime - beginTime)/1000000000f + " seconds.");

}

}