JavaBeat

  • Home
  • Java
    • Java 7
    • Java 8
    • Java EE
    • Servlets
  • Spring Framework
    • Spring Tutorials
    • Spring 4 Tutorials
    • Spring Boot
  • JSF Tutorials
  • Most Popular
    • Binary Search Tree Traversal
    • Spring Batch Tutorial
    • AngularJS + Spring MVC
    • Spring Data JPA Tutorial
    • Packaging and Deploying Node.js
  • About Us
    • Join Us (JBC)
  • Privacy

Merge Sort implementation using Fork-Join Framework in Java 7

June 13, 2012 by Mohamed Sanaulla Leave a Comment

In our previous post we went through the basics of Fork-Join Framework introduced as part of Java 7. In this post lets apply the same Fork-Join to implement Merge sort algorithm. The pseudo code for Merge sort can be found here.

also read:

  • Java 7.0 Tutorials
  • New Features in Java 7.0
  • G1 Garbage Collector in Java 7.0

In summary the Merge sort algorithm:

  1. Divides the array into 1 parts
  2. Sort each part individually and merge them to form a smaller sorted array.
  3. Merge individual sorted arrays to get the complete sorted array.

We create a task for dividing the array into 2 parts and then merge the arrays in the same task (i.e we dont spawn a new task for merging the arrays).
[code lang=”java”]
class DivideTask extends RecursiveTask<int[]> {

int[] arrayToDivide;

public DivideTask(int[] arrayToDivide) {
this.arrayToDivide = arrayToDivide;
}

@Override
protected int[] compute() {
List<RecursiveTask> forkedTasks = new ArrayList<>();

/*
* We divide the array till it has only 1 element.
* We can also custom define this value to say some
* 5 elements. In which case the return would be
* Arrays.sort(arrayToDivide) instead.
*/
if (arrayToDivide.length > 1) {

List<int[]> partitionedArray = partitionArray();

DivideTask task1 = new DivideTask(partitionedArray.get(0));
DivideTask task2 = new DivideTask(partitionedArray.get(1));
invokeAll(task1, task2);

//Wait for results from both the tasks
int[] array1 = task1.join();
int[] array2 = task2.join();

//Initialize a merged array
int[] mergedArray =
new int[array1.length + array2.length];

mergeArrays(task1.join(), task2.join(), mergedArray);

return mergedArray;
}
return arrayToDivide;
}

private List<int[]> partitionArray(){

int [] partition1 = Arrays.copyOfRange(arrayToDivide, 0,
arrayToDivide.length / 2);

int [] partition2 = Arrays.copyOfRange(arrayToDivide,
arrayToDivide.length / 2,
arrayToDivide.length);
return Arrays.asList(partition1,partition2);

}

private void mergeArrays(
int[] array1,
int[] array2,
int[] mergedArray) {

int i = 0, j = 0, k = 0;

while ((i < array1.length) && (j < array2.length)) {

if (array1[i] < array2[j]) {
mergedArray[k] = array1[i++];
} else {
mergedArray[k] = array2[j++];
}

k++;
}

if (i == array1.length) {

for (int a = j; a < array2.length; a++) {
mergedArray[k++] = array2[a];
}

} else {

for (int a = i; a < array1.length; a++) {
mergedArray[k++] = array1[a];
}

}
}
}
[/code]

In the above declared task, we override the compute method to partition the array given to be sorted:
[code lang=”java”]
int[] arrayPart1 = null;
int[] arrayPart2 = null;
partitionArray(arrayToDivide, arrayPart1, arrayPart2);
[/code]

if the array given to the task cannot be divided further i.e has only one element, then return that array
[code lang=”java”]
return arrayToDivide;
[/code]

If the partitions were created, then assign each partition to a new task and invoke the tasks created:
[code lang=”java”]
DivideTask task1 = new DivideTask(arrayPart1);
DivideTask task2 = new DivideTask(arrayPart2);
invokeAll(task1, task2);
[/code]

We would then have to wait for the results from both the tasks spawned and then merge their results to create a smaller sorted array:
[code lang=”java”]
//Wait for results from both the tasks
int[] array1 = task1.join();
int[] array2 = task2.join();

//Initialize a merged array
int[] mergedArray =
new int[array1.length + array2.length];

mergeArrays(task1.join(), task2.join(), mergedArray);

return mergedArray;
[/code]

This way each of the task which spawns more sub tasks would wait for their sub tasks to return a sorted array and then return back the sorted array to the parent task. This operation can be invoked as:
[code lang=”java”]
public class ForkJoinTest {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

int totalNumbers = scanner.nextInt();

int[] numbers = new int[totalNumbers];

for (int i = 0; i < totalNumbers; i++) {
numbers[i] = scanner.nextInt();
}

System.out.println("Unsorted array: "
+ Arrays.toString(numbers));

DivideTask task = new DivideTask(numbers);
ForkJoinPool forkJoinPool = new ForkJoinPool();
forkJoinPool.invoke(task);

System.out.println("Sorted array: "
+ Arrays.toString(task.join()));

}
}
[/code]

Output:
[code]
run:
8
8 3 2 9 7 1 5 4
Unsorted array: [8, 3, 2, 9, 7, 1, 5, 4]
Sorted array: [1, 2, 3, 4, 5, 7, 8, 9]
BUILD SUCCESSFUL (total time: 2 seconds)
[/code]

Another useful variant of Merge sort algorithm can be found here.

Filed Under: Java Tagged With: Fork Join, java 7, Merge Sort

Simple introduction to Fork-Join Framework in Java 7

June 12, 2012 by Mohamed Sanaulla Leave a Comment

Fork-Join Framework was added as part of Java 7 which makes use of the ExecutorService interface to distribute tasks to the worker threads in the thread pool. The difference in Fork-Join is that the ideal worker threads can steal queued subtasks from the other tasks and execute them.

also read:

  • Java 7.0 Tutorials
  • New Features in Java 7.0
  • G1 Garbage Collector in Java 7.0

There are a few important classes you should be aware of:

  • ForkJoinPool
  • RecursiveTask
  • ForkJoinTask
  • RecursiveAction

ForkJoinTask:
This represents the abstract task which runs within the ForkJoinPool. They are lightweight threads in the sense quite a lot of tasks can run withing few threads with some restrictions. There are two methods: fork() and join(). fork() is used to spawn new tasks, where as join() waits for the completion of the task. There are two extensions of ForkJoinTask- RecursiveTask and RecursiveAction. RecursiveTask is used when the task is expected to return some value, while RecursiveAction is used when the task preforms some action but doesn’t return any value. It is recommended to extend either RecursiveAction or RecursiveTask and not directly extend ForkJoinTask.

RecursiveTask:
This is a subclass of ForkJoinTask whose compute method returns some value.

RecursiveAction:
This is a subclass of ForkJoinTask whose compute method doesn’t return any value.

ForkJoinPool:
It is an ExecutorService for running ForkJoinTasks and also managing and monitoring the tasks. It employs worker-stealing algorithm where in idle threads can pick subtasks created by other active tasks and execute them. In this way there is efficient execution of tasks spawned by other tasks.

Lets see how we can find sum of some 1000 integers using ForkJoin framework. This is quite a trivial example and not worthy of being implemented as ForkJoin. The main motive behind this is to throw some light of the implementation aspects of ForkJoin.

In this example we will divide the array of integers into half and assign each half to a RecursiveTask. If the array size is less than 20 elements then we assign it to another RecursiveTask which would return the computed sum of those array elements.

RecursiveTask for computing the sum

[code lang=”java”]
//Task for computing the sum of array elements.
class SumCalculatorTask extends RecursiveTask<Integer>{
int [] numbers;
SumCalculatorTask(int[] numbers){
this.numbers = numbers;
}

@Override
protected Integer compute() {
int sum = 0;
for (int i : numbers){
sum += i;
}
return sum;
}
}
[/code]

The compute method has to be overridden with the actual task to be performed. In the above case its iterate through the elements of the array and return the computed sum.

RecursiveTask for dividing the array

We create a RecursiveTask for dividing the array into two parts and assign each part to another RecursiveTask for further dividing. We continue dividing the array and stop dividing when the array has less than 20 elements.
[code lang=”java”]
class NumberDividerTask extends RecursiveTask<Integer>{

int [] numbers;
NumberDividerTask(int [] numbers){
this.numbers = numbers;
}
/*
* If the array has less than 20 elements, then
* just compute the sum, else split the array further.
*/
@Override
protected Integer compute() {
int sum = 0;
List<RecursiveTask<Integer>> forks = new ArrayList<>();
if ( numbers.length > 20){
NumberDividerTask numberDividerTaskFirst =
new NumberDividerTask(Arrays
.copyOfRange(numbers, 0, numbers.length/2));
NumberDividerTask numberDividerTaskSecond =
new NumberDividerTask(Arrays
.copyOfRange(numbers, numbers.length/2, numbers.length));
forks.add(numberDividerTaskFirst);
forks.add(numberDividerTaskSecond);
numberDividerTaskFirst.fork();
numberDividerTaskSecond.fork();

}
else{

SumCalculatorTask sumCalculatorTask = new SumCalculatorTask(numbers);
forks.add(sumCalculatorTask);
sumCalculatorTask.fork();
}

//Combine the result from all the tasks
for ( RecursiveTask<Integer> task : forks){
sum += task.join();
}
return sum;

}
}
[/code]
Each of the above task spawns either 2 other NumberDividerTask or a SumCalculatorTask. Each task keeps a track of the sub tasks it has spawned in the forks. At the end of the task we wait for all the tasks in the forks list to finish by invoking join() method and add the return values from each of the subtasks.

To invoke the above defined tasks we make use of ForkJoinPool and create a NumberDividerTask task by giving it the array whose sum we wish to compute.
[code lang=”java”]
public class ForkJoinTest {

static ForkJoinPool forkJoinPool = new ForkJoinPool();
public static final int LENGTH = 1000;
public static void main(String[] args) {
int [] numbers = new int[LENGTH];
//Create an array with some values.
for(int i=0; i<LENGTH; i++){
numbers[i] = i * 2;
}
/*
* Invoke the NumberDividerTask with the array
* which in turn creates multiple sub tasks.
*/
int sum = forkJoinPool.invoke(new NumberDividerTask(numbers));

System.out.println("Sum: "+sum);
}
}
[/code]

The output: Sum: 999000.

This is just a basic, trivial example of using ForkJoin framework. I know this sum computation could have been implemented sequentially, but the idea here is to understand the working of the ForkJoin. In future I would try and post a ForkJoin version of some Divide and Conquer algorithm.

Filed Under: Java Tagged With: Fork Join, java 7

Follow Us

  • Facebook
  • Pinterest

As a participant in the Amazon Services LLC Associates Program, this site may earn from qualifying purchases. We may also earn commissions on purchases from other retail websites.

JavaBeat

FEATURED TUTORIALS

Answered: Using Java to Convert Int to String

What is new in Java 6.0 Collections API?

The Java 6.0 Compiler API

Copyright © by JavaBeat · All rights reserved