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);
   }
}

[ThreadPoolExecutor](http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ThreadPoolExecutor.html) — Apurva, Jul 20 '15 at 06:28
For example: `a[] = {1, 2}` the pairs are `{(1, 1), (1, 2), (2, 2)}` or only `{(1, 2)}`? In other words: Are the identities contained in the pair pool? — Flown, Jul 20 '15 at 07:06
@Flown only {(1,2)} is a pair. If a[] = {5,6,7} , pairs are {(5,6) ,(5,7),(6,7)} — Charan, Jul 20 '15 at 07:24

score 1 · Accepted Answer · answered Jul 20 '15 at 07:06

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());
    }
}

Hello sir, First of all , thank you for your awesome answer. I learnt how to divide a single task to multiple threads. — Charan, Jul 21 '15 at 08:21
I ran your code, but it is still taking the same amount of time, around 14 sec. But what I don't understand is, it is giving the size of the result list in 1 sec itself. I am thinking that extra 13-14 sec time is taken to print the ouput. Am I right, sir? — Charan, Jul 21 '15 at 08:24
I also tried this approach. Link => http://pastie.org/10303822 . I am creating multiple threads and giving them the same task . Am I doing it the right way? Are all the threads being utilized to speed up the task ? Because it is also taking the same amount of time. — Charan, Jul 21 '15 at 08:34
Link to code you wrote => http://pastie.org/10303817 . Please run it for testing. — Charan, Jul 21 '15 at 08:37
@Charan *I am thinking that extra 13-14 sec time is taken to print the ouput. Am I right, sir?* Yes, You're. *I also tried this approach. Link => pastie.org/10303822 . I am creating multiple threads and giving them the same task . Am I doing it the right way?* No, You don't, tasks must be splitted, Your threads don't need to repeat the same task! You must split task in sub-tasks and then distribute them! — David Pérez Cabrera, Jul 21 '15 at 15:39
Thank you sir! One last question . There are 2 arrays, one with coordinates of cities and one with population of those cities. The pairs (generated) are of coordinates. For each pair(from coordinates array), I will get the maximum of corresponding popoulations (from population array ) and then I will mulitiply this maximum value with absolute diffrence of that pair. So, ultimately workload is same as printing. My question is "Should I be using this approach?" . Because most of the test cases are terminated due to time out. — Charan, Jul 22 '15 at 07:50
For more insight : [Problem Link](https://www.hackerrank.com/challenges/direct-connections) — Charan, Jul 22 '15 at 07:50

score 0 · Answer 2 · answered Jul 20 '15 at 06:38

0

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.

answered Jul 20 '15 at 06:38

Sharon Ben Asher

13,849
5
33
47

Thanks for the suggestion, sir. With the help of above answer,and as you suggested, here is the code which implements Executor service and splitting of workload by splitting the iteration on array. Link=> http://pastie.org/10303817 – Charan Jul 21 '15 at 08:45
But it is still taking same amount of time when I try to print the pairs. Why isn't it speeding up? – Charan Jul 21 '15 at 08:46
I also tried this approach: http://pastie.org/10303822 . Please check once. I didn't split the workload by splitting array, instead I am using all the threads to work on it. Is my thinking right? It is also taking the same amount of time to print the pairs. – Charan Jul 21 '15 at 08:49

Division of a task to threads - multi threading

2 Answers2

Linked