2

I want to find the maximum value of the two-dimensional array. I found this value without using multithreading. How do I find the maximum value of the two-dimensional array using multithreading? I want to compare the speed of finding the maximum value of the array in different ways.

public class Search {

    public int[][] fillMatrix(int matrix[][]) {
        for (int i = 0; i < matrix.length; i++){
            for (int j = 0; j < matrix[i].length; j++){
              matrix[i][j] = (int)(Math.random() * 1000);
            }
        }
        return matrix;
    }

    public int searchMaxValue(int[][] matrix, int row, int column) {
        int max = matrix[0][0];
        for (int a = 0; a < row; a++) {
            for (int b = 0; b < column; b++) {
                try {
                    Thread.sleep(1);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                if (matrix[a][b] > max) {
                    max = matrix[a][b];
                }
            }
        }
        return max;
    }


    public static void main(String[] args) {

        Search search = new Search();
        int[][] matrix = new int[4][100];
        search.fillMatrix(matrix);
        long start = System.currentTimeMillis();
        int max = search.searchMaxValue(matrix, 4, 100);
        long end = System.currentTimeMillis();
        System.out.println("Max value is " + max);
        System.out.println("Time for execution: " + (end - start));
    }
}
Improve this question
1
  • The idea is to start a new thread for each inner array (aka column) that looks for the max value, returns it and ends. The main thread will then look for the biggest value in all those values only, improving speed on multicore CPUs. Commented Jun 5, 2016 at 14:38

3 Answers 3

Reset to default
1

Here is the outline how you would go about implementing this. I am not providing code intentionally, so that you can have the joy of implementing it yourself.

create a method to findmax out of an array lets call it findMax(int[] input)

for each sub array in 2D array (can be accessed using matrix[i])
start a thread to findMax(matrix[i]) (hint: use ExecutorService) in the thread, once max is found, fill it in to ith position of a one dimensional array called results in the thread, indicate its completion(hint: use CountDownLatch)

In the main thread, wait till all threads finish ( hint: use CountDownLatch) Now call findMax(results) and you have the maxiumum from matrix.

Considerations: Do we need to fork as many threads as the rows in matrix? So do we use a FixedThreadPool with number of rows ?

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

We need to find the maximum value in the matrix MxN with M threads. We do not use a FixedThreadPool.
1

The simplest way would be to start a thread to calculate the maximum in each of the four rows in the matrix, have the main thread join all of these row threads and calculate the maximum of the four row maxima. You will likely need a much larger array to be able to see the time difference, though. Don't neglect the necessary synchronization.

If as I suspect you are looking for code, you should make an attempt at the solution and run it, then repost or elaborate this post with the problems you run into.

Improve this answer

Comments

1

Here is how to do it in java 8:

int[][] values = fillMatrix(new int[1000][1000]);
OptionalInt max = Arrays.stream(values)
    .parallel()
    .flatMapToInt(Arrays::stream)
    .parallel()
    .max();

But frankly speaking, I'm not sure that for such simple computation it makes sense to use several threads, indeed creating and orchestrating threads has a price which seems to be too high in this case.

Response Update

As it is your homework, I provide an answer without any comments on purpose in order to ensure that you will at least think about how it works, but the main idea is to provide chunk of data to each thread to avoid collisions as next:

int[][] matrix = fillMatrix(new int[100][100]);
int totalThreads = 10;
int[] results = new int[totalThreads];
int chunkSize = matrix.length / totalThreads;
CountDownLatch end = new CountDownLatch(totalThreads);
for (int i = 0; i < totalThreads; i++) {
    int threadIndex = i;
    new Thread(
        () -> {
            int max = -1;
            int startIndex = threadIndex * chunkSize;
            for (int j = startIndex; j < startIndex + chunkSize && j < matrix.length; j++) {
                for (int k = 0; k < matrix[j].length; k++) {
                    if (max == -1 || max <  matrix[j][k]) {
                        max = matrix[j][k];
                    }
                }
            }
            results[threadIndex] = max;
            end.countDown();
        }
    ).start();
}
end.await();
int max = results[0];
for (int k = 1; k < results.length; k++) {
    if (max < results[k]) {
        max = results[k];
    }
}
System.out.printf("Max found %d%n", max);
Improve this answer

4 Comments

It will allow him to get the answer to his homework question, thouguh.
Thanks, your method works fine, but I need to solve the problem using the method specified above in the answer. Warren Dew is right, it is my homework.
Lambdas are glue code. Please refrain from writing whole methods inside lambdas. Google lambdas are glue code and read some excellent insights from Venkat Subramaniam
@ringbearer this is meant to show the idea nothing more and lambdas are perfect for this

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.