CodingGyan

Parallel Word Count per Line

medium Multithreading and Concurrency

Problem

Each input line is a task. Count the words of every line in parallel with a pool of worker threads (ExecutorService in Java, ThreadPoolExecutor in Python; JavaScript has one thread, so its version only shows the same result with map). Print the counts in the original line order, one per line, not in the order in which the tasks finish.

Constraints

  • 1 <= lines <= 1000

Examples

Input

hello world
a b c d
single

Output

2
4
1

Solutions

Best approachTime O(total words)Space O(n)

The results are read in submission order, so the output is the same on every run, even though the tasks may finish in any order. The JavaScript version is concurrent (one thread, many promises), the Java and Python versions use real worker threads.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Word counts.
 * Input   : Lines of text.
 * Output  : One count per line.
 * Approach: Worker pool.
 * Time    : O(total words)
 * Space   : O(n)
 * 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(String[] lines) {
        // Step 1: A fixed pool of 4 worker threads runs the tasks.
        java.util.concurrent.ExecutorService pool = java.util.concurrent.Executors.newFixedThreadPool(4);
        try {
            // Step 2: Submit one task per line. Each task counts the words of its own line.
            java.util.List<java.util.concurrent.Future<Integer>> futures = new java.util.ArrayList<>();
            for (String line : lines) {
                futures.add(pool.submit(() -> line.split(" ").length));
            }
            // Step 3: Read the futures in the order we created them. get() waits when a result is not ready.
            String[] output = new String[lines.length];
            for (int i = 0; i < futures.size(); i++) {
                output[i] = String.valueOf(futures.get(i).get());
            }
            return output;
        } catch (InterruptedException | java.util.concurrent.ExecutionException error) {
            // Step 4: get() can fail. We turn the checked error into an unchecked one.
            throw new IllegalStateException(error);
        } finally {
            // Step 5: Always shut the pool down, or the program may never end.
            pool.shutdown();
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (1)
  1. Why is the output order always the same?

Try these next