Matrix Row Sums with Parallel Tasks
Problem
Print the sum of every row of the matrix, in row order, separated by spaces. Give each row to its own task in a thread pool, and collect the answers in the right order. Input: rows and columns, then the matrix.
Constraints
- 1 <= r, c <= 100
- |a[i][j]| <= 10^9
Examples
Input
2 3 1 2 3 4 5 6
Output
6 15
Solutions
Results come back in task order (invokeAll in Java, map in Python), so the output order never depends on which thread finishes first.
/*
* Problem : Row sums with tasks.
* Input : r and c, then the matrix.
* Output : Row sums.
* Approach: One task per row.
* Time : O(r * c / threads)
* Space : O(r)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String solve(int[][] m) {
// Step 1: One task for each row. Each task only reads its own row, so the tasks share nothing that changes.
java.util.concurrent.ExecutorService pool = java.util.concurrent.Executors.newFixedThreadPool(4);
try {
java.util.List<java.util.concurrent.Callable<Long>> tasks = new java.util.ArrayList<java.util.concurrent.Callable<Long>>();
for (int[] row : m) {
tasks.add(() -> {
long sum = 0;
for (int value : row) {
sum += value;
}
return sum;
});
}
// Step 2: invokeAll runs all tasks and returns the futures in the same order as the tasks.
StringBuilder result = new StringBuilder();
for (java.util.concurrent.Future<Long> future : pool.invokeAll(tasks)) {
result.append(result.length() == 0 ? "" : " ").append(future.get());
}
return result.toString();
} catch (Exception e) {
throw new RuntimeException(e);
} finally {
pool.shutdown();
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int rows = scanner.nextInt();
int cols = scanner.nextInt();
int[][] m = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
m[i][j] = scanner.nextInt();
}
}
System.out.println(solve(m));
}
}
Hints (2)
- Why is the order of the output safe?
- What does each task read?