How do I sort a list of records using multithreading in java?

I'm teaching myself multithreading in java. My dummy example is that I have a large list of records (a 2D array) that I want sorted. The single threaded approach is to use loop through the list of records and sort. I want to multithread my program to sort my list with a fixed number threads, in this case 2. One thread will sort the first half of the list and the second thread will sort the remaining half. Then I want to output the results, of the now sorted list of records.

How can I create a thread pool of workers and sort the list of records? Do I need to worry about data being a shared resource? How do I return the results from each thread back to the original list of records? Below is my code.

import java.util.*; class RunnableProcess implements Runnable { private int[] data; public RunnableProcess(int[] data) { this.data = data; } public void run() { try { // sort the records this thread has access to for (int i = 0; i < data.length; i++) { Arrays.sort(data[i]); } } catch(Exception ex) { ex.printStackTrace(); } } } class BigData { static int[][] data = new int[1000][1000]; public static void main(String [] args) { // Create records for (int i = 0; i < data.length; i++) { for (int j = 0; j < data[0].length; j++) { data[i][j] = new Random().nextInt(999); } } // Call on two threads to sort the data variable // ExecutorService executor = Executors.newFixedThreadPool(2); // Python type of idea: Pass half the records to each thread and start // java doesn't support this so what is the java way of doing this? // Thread thread = new Thread(new RunnableProcess(data[:499])); // thread.start(); // Thread thread = new Thread(new RunnableProcess(data[499:])); // thread.start(); } } 

I am open suggestions on the best way to tackle this problem.

1 Answer

Java does not support slicing native arrays in the same fashion as python. We can get close, using ArrayList.

First, an aside. You random data generation is very inefficient. You are creating a new Random number generator object for each random number you generate. You only need one generator, like this:

Random rnd = new Random(); // Only created once for (int i = 0; i < data.length; i++) { for (int j = 0; j < data[0].length; j++) { data[i][j] = rnd.nextInt(999); } } 

Once you have created the data, we can turn this native int[][] 2d-array into a List of records, where each record is an int[] 1d-array:

List<int[]> records = Arrays.asList(data); 

Note that this does not copy the values in the array. It creates a List view of the array. Any change to the values stored in data will be reflected in records and vice versa.

We do this, so we can use the List#subList() method, to split the list into two views.

List<int[]> first_half = records.subList(0, 500); List<int[]> second_half = records.subList(500, 1000); 

Again, these are views, backed by the original list (backed by the original array). Changes made through the view will be reflected in the original.

Since we now have the records stored in a List, instead of an array, we need to update the RunnableProcess to use this new format:

class RunnableProcess implements Runnable { private List<int[]> records; public RunnableProcess(List<int[]> records) { this.records = records; } @Override public void run() { // sort the records this thread has access to for (int[] record : records) { Arrays.sort(record); } } } 

We now have the data partitioned into two independent sets, and a RunnableProcess that can operate on each set. Now, we can start the multithreading.

ExecutorService executor = Executors.newFixedThreadPool(2); 

This executor service creates a pool of two threads, and will reuse these threads over and over again for subsequent tasks that are submitted to this executor. Because of this, you do NOT need to create and start your own threads. The executor will take care of this.

executor.submit(new RunnableProcess(first_half)); executor.submit(new RunnableProcess(second_half)); 

Since we want to know when these tasks are both finished, we need to save the Future returned from executor.submit():

Future<?> task1 = executor.submit(new RunnableProcess(first_half)); Future<?> task2 = executor.submit(new RunnableProcess(second_half)); 

Calling Future#get() waits for the task to complete, and retrieves the result of the task. (Note: Since our Runnable does not return a value, the null value will be returned.)

task1.get(); // Wait for first task to finish ... task2.get(); // ... as well as the second task to finish. 

Finally, you need to #shutdown() the executor, or your program may not terminate properly.

executor.shutdown(); 

Complete example:

List<int[]> records = Arrays.asList(data); List<int[]> first_half = records.subList(0, 500); List<int[]> second_half = records.subList(500, 1000); ExecutorService executor = Executors.newFixedThreadPool(2); try { Future<?> task1 = executor.submit(new RunnableProcess(first_half)); Future<?> task2 = executor.submit(new RunnableProcess(second_half)); task1.get(); // Wait for first task to finish ... task2.get(); // ... as well as the second task to finish. } catch (InterruptedException | ExecutionException e) { e.printStackTrace(); } executor.shutdown(); 

Do I need to worry about data being a shared resource?

In this case, no. Your data is an array of arrays. Each thread is only referencing the data array (as a List), to get references to the int[] records. The data array itself is not be modified; only the records are, but each one is modified only by one of the threads.

How do I return the results from each thread back to the original list of records?

Since the records are being sorted "in place", your data variable already contains your array of sorted records. The calls to Future#get() ensures that each Thread has finished its processing, so that the data can once again be safely accessed from the main thread.