Question

Create a 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:

    public static void main( String[] args){
        long beginTime = System.nanoTime();
        Random gen = new Random();
        int[] data = new int[100000000];
        for(int i = 0; i < data.length; i++) {
            data[i] = gen.nextInt();
            if( data[i] < 0) {
                int foo = 1;
            }
            else {
                int foo = 1;
            }
        }
        long endTime = System.nanoTime();
        System.out.println("Done filling the array. That took " + (endTime - beginTime) + " nanoseconds.");
    }

Please submit your java source code along with a short summary of your design and results.

Answer 1

Output (Result vary on different systems)

Code with comments

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;

        }

        @Override

        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.");

    }

}

For indentation purpose