Friday, April 27, 2012

Concurrency in Java

Concurrent programming is currently the most talked about and the most important feature of java.
It was released with java 7 and will only work with a java7 compiler.
Concurrent programming includes threading or creating a thread pool and distributing our work among the threads to complete the work faster and use less cpu time.
This is very important because by using a single thread we may require about a day to get the output for this problem but with concurrency it takes about 1 second to get the output.

PROBLEM STATEMENT:

Randomly generate one million (x, y) points, where 0.0 <= x < 1.0 and 0.0 <= y 1.0, and x and y are of type double. Then find and print out the two closest points, along with the distance between them.
Do this as quickly as possible, and print out the time required in seconds, as a floating point number.
Use ForkJoin. If you have a dual-core or quad-core computer, this should make your program about 2x or 4x faster. If you don't, using ForkJoin will slow things down slightly--but use it anyway!

My code consist of 3 parts, it is always advisable to make different classes and then merge them together so that we dont have 1 code going upto thousands of lines, it makes debugging easier.

Pointset class:
This class creates an object of a point having 2 co-ordinates x and y.
This helps us in storing and creating more than a million objects of this kind.

package jointFork;

import java.util.Comparator;

/**
 * @author Arpit Jain
 * @version April 17,2012
 * This class creates the objects for the 2 coordinates of a point.
 *
 */
public class PointSet implements Comparable<PointSet>{

double x;
double y;

public PointSet(double x, double y) {
this.x = x;
this.y = y;
}

public double getX() {
return this.x;
}

public double getY() {
return this.y;
}

@Override
public String toString(){
String output = "x = " + this.x + ", y = " + this.y; //$NON-NLS-1$ //$NON-NLS-2$
return output;
}

@Override
public int compareTo(PointSet point1) {
return (int)(this.x - point1.x);
}
/**
* Creates duplicate of the same PointSet
*/
public PointSet clone(){
PointSet cloneSet = new PointSet(x, y);
return cloneSet;
}
/**
* This function is used within Array Sort.
* It sorts the array according to only x points.
*/
public static final Comparator<PointSet> PointSetComparatorX = new Comparator<PointSet>() {
@Override
public int compare(PointSet point1, PointSet point2) {
if (point1.x < point2.x) {
return -1;
}
if (point1.x > point2.x) {
return 1;
}
return 0;
}
};
/**
* This function is used within Array Sort.
* It sorts the array according to only y points.
*/
public static final Comparator<PointSet> PointSetComparatorY = new Comparator<PointSet>() {
@Override
public int compare(PointSet point1, PointSet point2) {
if (point1.y < point2.y) {
return -1;
}
if (point1.y > point2.y) {
return 1;
}
return 0;
}
};
}

forkjoin class:
This class only creates the fork pool and given threshold values and set the starting parameters.
Its only job is to take the seed from user, calculate the time and calculate the distance between 2 closest points it receives.


package jointFork;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;

/**
 *
 * @author Arpit Jain
 * @version April 17,2012
 *
 */
public class ForkJoinPoints {

public static ForkJoinPool forkPool = new ForkJoinPool();
private static Random rand;
static PointSet[] xSorted;
public static BufferedReader br;
static final int numberOfPoints = 1000000;

/**
* Takes the seed to generate random numbers as a user input
* Sort all the generated xSorted with respect to x coordinates
* Displays the time take (in secs) to find the closest xSorted
* @param args
*/
public static void main(String[] args) {

float time;

System.out.println("Enter the Seed value:");

br = new BufferedReader(new InputStreamReader(System.in));
String inputEntry = null;
try {
inputEntry = br.readLine();
}
catch(IOException ioe) {
System.out.println("IO error trying to read your entry!"); //$NON-NLS-1$
System.exit(1);
}
catch(NumberFormatException i) {
System.out.println("invalid entry "); //$NON-NLS-1$
System.exit(1);
}
int intValue = Integer.parseInt(inputEntry);
rand =  new Random(intValue);
int numbers = 0;
xSorted = new PointSet[numberOfPoints];


while(numbers < numberOfPoints) {
double Xvalue = rand.nextDouble();
double Yvalue = rand.nextDouble();
xSorted [numbers] = new PointSet(Xvalue,Yvalue);
numbers++;
}

long start_time = System.currentTimeMillis();

Arrays.sort(xSorted,PointSet.PointSetComparatorX);


PointSet[] pairs;

pairs = forkPool.invoke(new SplitWork(xSorted,0, numberOfPoints - 1));
// print value of closest xSorted
System.out.println("The Closest Pairs are : " );
System.out.println(pairs[0] + "\n" + pairs[1]);
double dist1 = distance(pairs[0],pairs[1]);
System.out.println("Distance between the 2 closest points is : " + dist1);
time = (System.currentTimeMillis() - start_time)/1000;
System.out.println("Time taken = " + time + " seconds");
}

public static double distance(PointSet p1, PointSet p2) {
double powerX = Math.pow(p1.x - p2.x, 2);
double powerY = Math.pow(p1.y - p2.y, 2);
double finalDistance = Math.sqrt(powerX + powerY);
return finalDistance;
}
}


split work class:
This class does all the calculation and creates objects of pointset class and uses shortest distance algorithm to find the value of the closest points. if we use brute force to find closest distance between a million points then it will take almost a day to calculate it. hence we dont make use of brute force.

package jointFork;

import java.util.Arrays;
import java.util.concurrent.RecursiveTask;

/**
 * @author Arpit Jain
 * @version April 17,2012
 * The class extends the Recursive task i.e every thread is
 * given its own set of work by the compute function and 
 * work is done by recursively calling the function.
 * 
 */
class SplitWork extends RecursiveTask<PointSet[]> {
private static final long serialVersionUID = 1L;
int startIndex;
int endIndex;
private static PointSet[] xSorted;
static final int thresholdValue = 5000;
/**
* This constructor is used by to get the values of the set containing the
* points and to get the start and the end index initially when it is called
* by the fork join pool.
* @param p - Array of objects(x & y coordinates)
* @param startIndex - initial index of the size of array i.e 0
* @param endIndex - last index of the array
*/

SplitWork(PointSet[]p,int startIndex, int endIndex) {
this.startIndex = startIndex;
this.endIndex = endIndex;
SplitWork.setxSorted(p);
}
/**
* This constructor is used to call recursively
* @param startIndex- current startIndex
* @param endIndex - current End index
*/
SplitWork(int startIndex, int endIndex) {
this.startIndex = startIndex;
this.endIndex = endIndex;
}
/**
*Compute function provides each thread with its set of work 
*/
public PointSet[] compute() {
return closestPoints(startIndex,endIndex);
}

/**
*  Calculating the distance between 2 points
* @param p1 -First point
* @param p2 - second point
* @return -distance between them
*/
public static double distance(PointSet p1, PointSet p2) {
double powerX = Math.pow(p1.x - p2.x, 2);
double powerY = Math.pow(p1.y - p2.y, 2);
double finalDistance = Math.sqrt(powerX + powerY);
return finalDistance;
}
/**
* This function computes the closest pairs of xSorted by dividing 
* the array of xSorted recursively
* @param startIndex - starting index of the array of xSorted
* @param endIndex - last index of the array of xSorted
* @return - the closest pairs of xSorted
*/
static PointSet[] closestPoints(final int startIndex, final int endIndex) {
PointSet[]  pairs = new PointSet[2];
if(endIndex - startIndex == 0) {
return null;
}

else if(endIndex - startIndex == 1) {
pairs[0] = getxSorted()[startIndex];
pairs[1] = getxSorted()[endIndex];
return pairs;
}

// else if(endIndex- startIndex+1 == 3 ) {
//
// double minimumDistance= -1;
// for(int i = 0; i<3;i++) {
// for(int j = i+1;j<3;j++) {
// double dist = distance(xSorted[i],xSorted[j]);
// if(i == 0 && j == i+1) 
// minimumDistance = dist;
//
// if(minimumDistance > dist) {
// minimumDistance = dist;
// pairs[0] = xSorted[i];
// pairs[1] = xSorted[j];
// }
// }
// }
// return pairs;
// }
else if(endIndex - startIndex == 2) {
           int number = getClosestPoints(getxSorted()[startIndex],getxSorted()[startIndex+1],getxSorted()[endIndex]);
         if(number == 0) {
         return null;
         }
         else if(number == 1) {
          pairs[0] = getxSorted()[startIndex];
          pairs[1] = getxSorted()[startIndex + 1];
         }
         else if(number == 2) {
          pairs[0] = getxSorted()[startIndex+1];
          pairs[1] = getxSorted()[endIndex];
         }
         else if(number == 3) {
          pairs[0] = getxSorted()[startIndex];
  pairs[1] = getxSorted()[endIndex];
         }
           return pairs;
}

final int midIndex = (startIndex + endIndex) / 2;
int leftValue = midIndex - startIndex +1;
int rightValue = endIndex - midIndex;
PointSet[] leftSet = null;
PointSet[] rightSet = null;
SplitWork leftSide = null, rightSide = null;

if (leftValue < thresholdValue) {
leftSet = closestPoints(startIndex, midIndex);

} else {
leftSide = new SplitWork(startIndex, midIndex);
leftSide.fork();
}

if (rightValue < thresholdValue) {
rightSet = new PointSet[2];
rightSet = closestPoints(midIndex + 1, endIndex);


} else {
rightSide = new SplitWork(midIndex + 1, endIndex);
rightSide.fork();
}

if (leftSide != null) {
leftSet = leftSide.join();
}
if (rightSide != null) {
rightSet = rightSide.join();
}

//finding the minimum distance on left and right
double minLeft = distance(leftSet[0], leftSet[1]);
double minRight = distance(rightSet[0], rightSet[1]);
double minRL;
minRL = Math.min(minLeft, minRight);

if (minRL == minLeft) {
pairs[0] = leftSet[0];
pairs[1] = leftSet[1];
} else {
pairs[0] = rightSet[0];
pairs[1] = rightSet[1];

}

double minDist= minRL;

int leftMiddle= midIndex;
int rightMiddle = midIndex;
double middleX = getxSorted()[midIndex].x;
double middleLeftX = middleX - minRL;
double middleRightX = middleX + minRL;

while (leftMiddle> startIndex && getxSorted()[leftMiddle- 1].x > middleLeftX) {
leftMiddle--;
}

while (rightMiddle < endIndex && getxSorted()[rightMiddle + 1].x < middleRightX) {
rightMiddle++;
}

/*
*Array of elements which might have the shortest 
*distance but are divided by the midpoint.
*
*/
PointSet []Ystrip = new PointSet[rightMiddle - leftMiddle+ 1];

for (int index = 0; index < Ystrip.length; index++) {
Ystrip[index] = getxSorted()[index + leftMiddle].clone();
}

Arrays.sort(Ystrip,PointSet.PointSetComparatorY);


// Calculating the distance of all the xSorted in Ystrip with each other
for (int i = 0; i < Ystrip.length - 1; i++) {
for (int j = i+1; j < Ystrip.length && (Ystrip[j].getY() -  Ystrip[i].getY() < minRL); j++) {
double d = distance(Ystrip[i],Ystrip[j]);
if (d < minDist) {
minDist= d;
pairs[0] = Ystrip[i];
pairs[1] = Ystrip[j];
}
}
}

return pairs;
}
/**
* For the array of size 3 we calculate the smallest distance by using 
* brute force.
* @param p1- first point
* @param p2- second point
* @param p3- third point
* @return- the point whose distance is the shortest
*/
public static  int getClosestPoints(PointSet p1, PointSet p2, PointSet p3) {
       double distance1 = distance(p1,p2);
       double distance2  = distance(p2,p3);
       double distance3 = distance(p1,p3);
       if(distance1 <= distance2 && distance1 <= distance3) {
        return 1;
       }
       else if(distance2 <= distance1 && distance2 <= distance3) {
        return 2;
       }
       else if(distance3 <= distance1 && distance3<=distance2) {
        return 3;
       }
       return 0;
   }

public static PointSet[] getxSorted() {
return xSorted;
}

public static void setxSorted(PointSet[] xSorted) {
SplitWork.xSorted = xSorted;
}
}


Four in a Row game using C

This game is similar to the Connect 4 game, Here we make use of signals and pipes to communicate between M children and a parent and play the game of connect 4.
The child is Intelligent to an extent and will not make just random moves, whereas the parent will make random moves.Here 1 or B stand for child and 2 or R stands for the parent.
The size of the board is N which is currently fixed to be 5 but can be changed.
I have made use of two c files, 1 is the header and the other is the c file. The header file contains all of the headers and non calculating functions. Also i made this program in Linux, if you are building it on windows you might wanna include conio.h as the header file as well and use getch().
I will be putting up the code and some of its outputs as well

this is the header file called as header.h


#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/types.h>
#include <unistd.h>
#include <time.h>
#include <signal.h>
#define M 3 //number of players
#define N 5 //board size

int count = 0;
int isDone[M];
pid_t array[M];

union BoardGame{
int board[N][N];
pid_t childpid;
int hasCompleted;
int boardNumber;
int signal;
};
typedef union BoardGame game;


void initializeBoard(game *board,int id){
board-> hasCompleted = 0;
board -> boardNumber = id;
board -> signal = 0;
int i,j;
for(i = 0; i<N;i++){
for(j = 0;j<N;j++){
board-> board[i][j] = 0;
}
}
}

int isBoardEmpty(game *board){
int column;
for(column = 0; column < N ; column++){
if(board->board[0][column] == 0)
return 0;
}

printf(" Board %d is full ", board->boardNumber);
return 1;
}

int isValidMove(game *board, int column) {
if (board->board[0][column] == 0) {
return 1;
}

else
return 0;
}

void print(game *board){
int i = 0 ;
int j;
int k;
int row = 0;
for(k =0; k<N;k++)
printf(" -------");
printf("\n");
for(i= 0 ; i<3*N; i++){
for(j = 0;j<=N;j++){

if (i% 3 == 1 && j!=N){
printf("|");
if( board->board[i/3][j] == 1){
printf("   B ");
}
else if( board->board[i/3][j] == 2){
printf("   R ");
}
else if( board->board[i/3][j] == 0){
printf("   %d ", board->board[i/3][j]);
}
}
else
printf("| ");
}

printf("\n");
if(i%3==2){
for(k =0; k<N;k++)
printf(" -------");
printf("\n");
}
}
}

The main file :


#include "four_header.h"


int randomNumber(){
int x1 = rand()%N;
return x1;
}

int calculateChild1(int column, game *board){        //(game *board){{
int i;
//int column = rand()%N;
for(i = N-1;i >= 0;i--){
//        printf("i = %d\n",i);
if(board->board[i][column] == 0){
board->board[i][column] = 1;
return i;
}
}  
}


int columnCalculate(game *board){
int column;
again:
column = randomNumber();
if(isValidMove(board, column) == 1)
return column;
else
goto again;
}

int calculateRow(int column, game *board){  
int i;
//int column = rand()%N;
for(i = N-1;i >= 0;i--){
//        printf("i = %d\n",i);
if(board->board[i][column] == 0){
return i;
}
}  
}

int calculateChild(game *board){
int column,row;
// srand(time(NULL));
for(column = 0; column < N; column++) {

if(board->board[0][column] != 0) {

continue;
}
row = calculateRow(column,board);

if((row - 1) >= 0){
if(board->board[row - 1][column] == 1) {
return column;
}
}
//check left
if((column - 1) >= 0){
if(board->board[row][column - 1] == 1) {
return column;
}
}

if((column + 1) <= N -1) {
if(board->board[row][column + 1] == 1){
return column;
}
}


if(((column + 1) <= (N - 1)) && ((row - 1) >= 0)){
if( board->board[row - 1][column + 1] == 1)
return column;
}

if(((column - 1) > -1) && ((row - 1) > -1)){
if(board->board[row - 1][column - 1] == 1)
return column;
}

if(((column + 1) < N) && ((row + 1) < N)){
if(board->board[row + 1][column + 1] == 1)
return column;
}
}
while(1) {
column = columnCalculate(board);
return column;
}

}


int calculateParent(int column,game *board){
int i;
for(i = N-1;i >= 0;i--){
//        printf("i = %d\n",i);
if(board->board[i][column] == 0){
board -> board[i][column] = 2;
return i;
}
}
}



int check1(game *board){
int row[N], column[N], diagonal1[N], diagonal2[N];
int i,j;
for(i = 0;i<N;i++){
row[i] = 0;
column[i] = 0;
diagonal1[i] = 0;
diagonal2[i] = 0;
}
for(i = 0;i<N;i++){
for(j = 0; j<N;j++){
if(board -> board[i][j] == 1){

row[i] = row[i]+1;
//                printf("row check of %d = %d\n",i,row[i]);
//                printf("----------------------------\n");
}
else row[i] = 0;
if(board-> board[j][i]==1){
column[i] = column[i]+1;
//                printf("column check of %d = %d\n",i,column[i]);
//                printf("----------------------------\n");
}
else column[i] = 0;
if(board -> board[i+j][j] == 1){
diagonal1[i] = diagonal1[i] + 1;
//                printf("diagonal1 check of player 1 = %d\n",diagonal1[i]);
//                printf("----------------------------\n");
}
else diagonal1[i] = 0;  
if(board->board[i+j][N-1-j] == 1){
//                printf("diag2 = %d\n i+j = %d \n n-1-j = %d\n",board[i+j][N-1-j][no],i+j,((N-1)-j));
diagonal2[i] = diagonal2[i] + 1;
//                printf("diagonal2 check of player 1 = %d\n",diagonal2[i]);
//                printf("----------------------------\n");
}
else diagonal2[i] = 0;
//if(row[i] == 4 || column[i] == 4|| diagonal1[i] == 4||diagonal2[i]==4)
//    return 1;
if(row[i] == 4){
printf ("\nChild won on row\n");
sleep(2);
return 1;
}
else if(column[i] == 4){
printf ("\nChild won on column\n");
sleep(2);
return 1;
}
else if(diagonal1[i] == 4){
printf ("\nChild won on diagonal\n");
sleep(2);
return 1;
}
else if(diagonal2[i] == 4){
printf ("\nChild won on anti-diagonal\n");
sleep(2);
return 1;
}
}
}  
return 0;
}

int check2(game *board){
int row[N], column[N], diagonal1[N], diagonal2[N];
int i,j;
for(i = 0;i<N;i++){
row[i] = 0;
column[i] = 0;
diagonal1[i] = 0;
diagonal2[i] = 0;
}
for(i = 0;i<N;i++){
for(j = 0; j<N;j++){
if(board -> board[i][j] == 2){

row[i] = row[i]+1;
//                printf("row check of %d = %d\n",i,row[i]);
//                printf("----------------------------\n");
}
else row[i] = 0;
if(board-> board[j][i] == 2){
column[i] = column[i]+1;
//                printf("column check of %d = %d\n",i,column[i]);
//                printf("----------------------------\n");
}
else column[i] = 0;
if(board -> board[i+j][j] == 2){
diagonal1[i] = diagonal1[i] + 1;
//                printf("diagonal1 check of player 1 = %d\n",diagonal1[i]);
//                printf("----------------------------\n");
}
else diagonal1[i] = 0;  
if(board->board[i+j][N-1-j] == 2){
//                printf("diag2 = %d\n i+j = %d \n n-1-j = %d\n",board[i+j][N-1-j][no],i+j,((N-1)-j));
diagonal2[i] = diagonal2[i] + 1;
//                printf("diagonal2 check of player 1 = %d\n",diagonal2[i]);
//                printf("----------------------------\n");
}
else diagonal2[i] = 0;
//if(row[i] == 4 || column[i] == 4|| diagonal1[i] == 4||diagonal2[i]==4)
//    return 1;
if(row[i] == 4){
printf ("\nParent won on row\n");
sleep(2);
return 1;
}
else if(column[i] == 4){
printf ("\nParent won on column\n");
sleep(2);
return 1;
}
else if(diagonal1[i] == 4){
printf ("\nParent won on diagonal\n");
sleep(2);
return 1;
}
else if(diagonal2[i] == 4){
printf ("\nParent won on anti-diagonal\n");
sleep(2);
return 1;
}
}
}  
return 0;
}


void boardCheck(int ){
count += 1;
if(count == M){
printf("Game over\n");
exit(0);
}
}
void quit(int parentPipe[2],int childPipe[2],game *board, int player){

if(player == 1){
kill(getppid(), SIGUSR1);
close(parentPipe[0]);
close(childPipe[1]);
close(parentPipe[1]);
close(childPipe[0]);
}
else if(player == 2){
close(parentPipe[1]);
close(childPipe[0]);
close(parentPipe[0]);
close(childPipe[1]);      
}
}
void playChildGame(int parentPipe[2],int childPipe[2],game *board, int boardNum){
int i,j;
int parentMove = 0;
int childMove = 0;
int childMove1 = 0;
int check = 0;
int columnChild;
initializeBoard(board, boardNum);
for(i = 0; i< N*N;i++){
if(isBoardEmpty(board) == 1){
check = getpid();
write(childPipe[1], &check,sizeof(int));
goto quit;

}

do{
read(parentPipe[0],&parentMove,sizeof(int));
check = -1;
write(childPipe[1],&check,sizeof(int));
}while(isValidMove(board,parentMove) == 0);
calculateParent(parentMove, board);
printf("--------------------------------------------------------------------------\n");
printf("Parent is making the move on %d on board # %d \n",parentMove, boardNum);
printf("--------------------------------------------------------------------------\n");
print(board);
sleep(2);

if(check2(board) == 1 || isBoardEmpty(board) == 1){
check = getpid();
write(childPipe[1], &check, sizeof(int));
goto quit;

}
else{
check = -1;
write(childPipe[1], &check, sizeof(int));
}

check = 0;
do{
check++;
columnChild = randomNumber();
}while(isValidMove(board, columnChild) == 0 );

childMove = calculateChild(board);
childMove1 = calculateChild1(childMove,board);
printf("--------------------------------------------------------------------------\n");
printf("Child is making the move on %d on board # %d \n",columnChild, boardNum);
printf("--------------------------------------------------------------------------\n");
print(board);
sleep(2);
if(check1(board) == 1 || isBoardEmpty(board) == 1){
check = getpid();
write(childPipe[1], &check, sizeof(int));
goto quit;

}
else{
check = -1;
write(childPipe[1], &check, sizeof(int));
}
}
goto quit;
quit:  
kill(getppid(), SIGUSR1);
close(parentPipe[0]);
close(childPipe[1]);
close(parentPipe[1]);
close(childPipe[0]);

}

int playParentGame(int parentPipe[2],int childPipe[2], int boardNum){
int childMove = 0;
int random = 0;
int parentMove;
while(1){
random = randomNumber();
srand(time(NULL) - random*6);
random = randomNumber();
write(parentPipe[1], &random , sizeof(int));
read(childPipe[0], &childMove, sizeof(int));
if( childMove != -1){
if(array[boardNum] == childMove){
goto quit;

}
}
}
quit:
close(parentPipe[1]);
close(childPipe[0]);
close(parentPipe[0]);
close(childPipe[1]);
return 1;
}

int main(int argc, char **argv){
game boardGame[M];
int i, j, boardNum, k;
int pipe1[M][2];
int pipe2[M][2];
int flag = 0;
int index = 0;
pid_t pid;
srand(time(0));
signal(SIGUSR1, boardCheck);
for (i  = 0; i < M; i++) {
initializeBoard(&boardGame[i],i);
isDone[i] = 0;
}

for(i = 0; i < M; i++) {
pipe(pipe1[i]);
pipe(pipe2[i]);
pid = fork();

if (pid == 0) { //CHILD

if (!flag) {
boardNum = i;
flag = 1;
}
i += M;

playChildGame(pipe1[boardNum],pipe2[boardNum], &boardGame[boardNum], boardNum);

}

else {  //PARENT

array[index] = pid;
index++;
if(index == M) {
for(j = 0; j < M; j++)  
playParentGame(pipe1[j],pipe2[j], j);
}        
}
}
return 0;
}  

some sample out put: