Pattern: Data Parallelism — Partition, Map, Reduce (Problems 1–6)

The pattern behind half these problems

Problems 1–6 (parallel linear search, MinMaxSum, Pi, odd-even sort) are the same shape: a big input, an independent computation per element, and a result. The pattern is partition → map → reduce: split the input into chunks, give each chunk to a worker, then combine the partial results. It scales to cores and is the foundation of every parallel-data framework (parallel streams, MapReduce, Spark).

Worked: parallel MinMaxSum (Problem 4)

Each worker scans its slice and returns (min, max, sum); the reduce step combines them — min of mins, max of maxes, sum of sums. The combine op must be associative so order doesn't matter.

record R(long min, long max, long sum) {}
int parts = Runtime.getRuntime().availableProcessors();
ExecutorService pool = Executors.newFixedThreadPool(parts);
List<Future<R>> fs = new ArrayList<>();
for (int[] slice : partition(data, parts))
    fs.add(pool.submit(() -> scan(slice)));      // map: each slice -> partial R
R total = new R(MAX, MIN, 0);
for (Future<R> f : fs) {                          // reduce: combine partials
    R p = f.get();
    total = new R(min(total.min, p.min), max(total.max, p.max), total.sum + p.sum);
}
pool.shutdown();

Same pattern in Go

partials := make(chan R, parts)
var wg sync.WaitGroup
for _, slice := range partition(data, parts) {
    wg.Add(1)
    go func(s []int){ defer wg.Done(); partials <- scan(s) }(slice)   // map
}
go func(){ wg.Wait(); close(partials) }()
total := R{min: MAX, max: MIN}
for p := range partials { total = combine(total, p) }                 // reduce

How each problem maps to it

• P1–3 Linear search (one / all / with indices): map = "scan my slice for matches"; reduce = merge index lists. Find-one adds an early-exit flag (a volatile / atomic "found") so workers stop once any thread succeeds.
• P4 MinMaxSum: the worked example above.
• P5 Pi (numerical integration): map = sum of terms in my interval; reduce = add partial sums. A pure parallel reduce.
• P6 Odd-even sort: a phased variant — each phase compares disjoint pairs in parallel, with a barrier between phases (see the Coordination patterns page).

Pitfalls

• Non-associative combine → wrong answer under reordering. Verify min/max/sum/count are associative (averages are not — carry sum & count).
• Too-small inputs: thread/goroutine overhead exceeds the work — have a sequential cutoff.
• Shared accumulator instead of per-worker partials → the counter++ race. Keep state per-worker, combine at the end.
• Uneven chunks starve cores; split by work, not just by index, for skewed costs.

Takeaways

• Partition → map (per-worker partial) → reduce (associative combine). No shared mutable accumulator.
• Early-exit searches need an atomic "found" flag; phased algorithms need a barrier between phases.
• Java: ExecutorService+Future (or parallel streams). Go: goroutines + a partials channel.

---

Re-authored for this guide; partition/reduce diagram hand-authored as SVG. Covers concurrency Problems 1–6. See also: Thread Pools & Executors, Go Concurrency, and the Coordination & Barriers patterns.

I just read a lesson on **Pattern: Data Parallelism — Partition, Map, Reduce (Problems 1–6)** (Concurrency) and want to truly understand it. Explain Pattern: Data Parallelism — Partition, Map, Reduce (Problems 1–6) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Pattern: Data Parallelism — Partition, Map, Reduce (Problems 1–6)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Pattern: Data Parallelism — Partition, Map, Reduce (Problems 1–6)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Pattern: Data Parallelism — Partition, Map, Reduce (Problems 1–6)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.