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

Best approachTime O(r * c / threads)Space O(r)

Results come back in task order (invokeAll in Java, map in Python), so the output order never depends on which thread finishes first.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * 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)
  1. Why is the order of the output safe?
  2. What does each task read?