Division of a task to threads - multi threading

Question

I want to generate pairs from a given large pool of numbers. I am using two for loops and threads. My function getAllPairs() in the code generates apairs with a given array of numbers.

I have an array of length 1000. With one thread, output time is nearly 15 sec. Now I want to use 5-6 threads and reduce this output time.I am stuck at dividing this task equally to five threads.If not threads,how to decrease the output time?

Solution with threads is appreciated since I put a lot of time learning multithreading. I would like to implement it.

import java.util.*;


 class Pair {
 public int x, y;
 public Pair(int x, int y) {
  this.x = x;
  this.y = y;
 }
  @Override
    public String toString(){
        return " ( " + x + " ," + y + " ) " ;
    }
}


class selectPairs{
 private int[] array;
 private List<Pair> totalPairs ;

 public selectPairs(int[] arr){
     array = arr;
 }
 //set Method
 public void settotalPairs(List<Pair> pieces){
     totalPairs = pieces;
 }
 //get Method
 public List<Pair> gettotalPairs(){
     return totalPairs;
 }

 // Method to generate pairs
 public List<Pair> getAllPairs() {
  List<Pair> pairs = new ArrayList<Pair>();
  int total = array.length;
  for(int i=0; i < total; i++) {
  int num1 = array[i];
  for(int j=i+1; j < total; j++) {
   int num2 = array[j];
   pairs.add(new Pair(num1,num2));
   }
  }
  return pairs;
 } 
}


// Thread class
class ThreadPairs extends Thread {
   private Thread t;
   selectPairs SP;

   ThreadPairs(selectPairs sp){

        SP = sp;
   }
   public void run() {
      synchronized(SP) {
       List<Pair> PAIRS = SP.getAllPairs();
       SP.settotalPairs(PAIRS);
     }
   }
}

 public class TestThread {
   public static void main(String args[]) {

       int[] a = new int[1000]; 
       for (int i = 0; i < a.length; i++) { 
        a[i] = i ;
        }

      selectPairs ob = new selectPairs(a);
      ThreadPairs T = new ThreadPairs(  ob );
      T.start();

      while (true) {
        try {
         T.join(); 
         break;
        }
        catch(Exception e){
        }
      }

      List<Pair> Total = new ArrayList<Pair>() ;
      List<Pair> Temp1 = ob.gettotalPairs();
      Total.addAll(Temp1);
      System.out.println(Total);
   }
}

Answer 1

A solution with a thread-pool, a task split strategy and it collects all results:

public class SelectPairs {

    private static final int NUM_THREADS = 8;

    private int[] array;

    public SelectPairs(int[] arr) {
        array = arr;
    }

    // A splitting task strategy
    public List<Pair> getPartialPairs(int threadIndex, int numThreads) {
        List<Pair> pairs = new ArrayList<Pair>();
        int total = array.length;
        for (int i = threadIndex; i < total; i += numThreads) {
            int num1 = array[i];
            for (int j = i + 1; j < total; j++) {
                int num2 = array[j];
                pairs.add(new Pair(num1, num2));
            }
        }
        return pairs;
    }

    // To use Callables or Runnables are better than extends a Thread.
    public static class PartialPairsCall implements Callable<List<Pair>> {

        private int thread;
        private int totalThreads;
        private SelectPairs selectPairs;

        public PartialPairsCall(int thread, int totalThreads, SelectPairs selectPairs) {
            this.thread = thread;
            this.totalThreads = totalThreads;
            this.selectPairs = selectPairs;
        }

        @Override
        public List<Pair> call() throws Exception {
            return selectPairs.getPartialPairs(thread, totalThreads);
        }
    }


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

        int[] a = new int[1000];
        for (int i = 0; i < a.length; i++) {
            a[i] = i;
        }
        SelectPairs sp = new SelectPairs(a);

        // Create a thread pool 
        ExecutorService es = Executors.newFixedThreadPool(NUM_THREADS);
        List<Future<List<Pair>>> futures = new ArrayList<>(NUM_THREADS);

        // Submit task to every thread:
        for (int i = 0; i < NUM_THREADS; i++) {
            futures.add(es.submit(new PartialPairsCall(i, NUM_THREADS, sp)));
        }

        // Collect the results:
        List<Pair> result = new ArrayList<>(a.length * (a.length - 1));
        for (Future<List<Pair>> future : futures) {
            result.addAll(future.get());
        }

        // Shutdown thread pool
        es.shutdown();

        System.out.println("result: " + result.size());
    }
}

Answer 2

regarding the framework of multithreading, you can implement ThreadPoolExecutor as was suggested in a comment.
Regarding splitting the workload, it seems that the key is splitting the iteration on the array which is achievable if you give the Runnable task a start and end index to iterate over.