Parallel Algorithms
Parallel Algorithms#
Parallel algorithms split work into smaller pieces that execute simultaneously across multiple CPU cores. Think of assembling furniture—instead of one person doing everything sequentially, a team can work on different parts at the same time, dramatically reducing completion time.
The key is identifying which work can happen independently. For example, when sorting a large array, you can divide it into chunks, sort each chunk in parallel, then merge the results—much faster than sorting the entire array sequentially.
Common Approaches#
Divide and Conquer#
Divide-and-conquer naturally lends itself to parallelization. Split the problem into independent subproblems, solve them in parallel, then combine the results. Merge sort is a classic example—divide the array in half, sort both halves concurrently, then merge them back together.
import java.util.concurrent.*;
import java.util.Arrays;
public class ParallelMergeSort {
private final ForkJoinPool pool;
public ParallelMergeSort() {
this.pool = ForkJoinPool.commonPool();
}
public int[] parallelMergeSort(int[] array) {
return pool.invoke(new MergeSortTask(array, 0, array.length - 1));
}
private class MergeSortTask extends RecursiveTask<int[]> {
private final int[] array;
private final int left, right;
MergeSortTask(int[] array, int left, int right) {
this.array = array;
this.left = left;
this.right = right;
}
@Override
protected int[] compute() {
if (right - left < 2) {
return Arrays.copyOfRange(array, left, right + 1);
}
int mid = (left + right) / 2;
MergeSortTask leftTask = new MergeSortTask(array, left, mid);
MergeSortTask rightTask = new MergeSortTask(array, mid + 1, right);
leftTask.fork();
int[] rightResult = rightTask.compute();
int[] leftResult = leftTask.join();
return merge(leftResult, rightResult);
}
private int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result[k++] = left[i++];
} else {
result[k++] = right[j++];
}
}
while (i < left.length) result[k++] = left[i++];
while (j < right.length) result[k++] = right[j++];
return result;
}
}
}
// Usage
ParallelMergeSort sorter = new ParallelMergeSort();
int[] unsorted = {5, 2, 8, 1, 9, 3, 7, 4, 6};
int[] sorted = sorter.parallelMergeSort(unsorted);
System.out.println("Sorted: " + Arrays.toString(sorted));
// Output: Sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9]
import java.util.concurrent.*
class ParallelMergeSort {
private val pool = ForkJoinPool.commonPool()
fun parallelMergeSort(array: IntArray): IntArray {
return pool.invoke(MergeSortTask(array, 0, array.size - 1))
}
private inner class MergeSortTask(
private val array: IntArray,
private val left: Int,
private val right: Int
) : RecursiveTask<IntArray>() {
override fun compute(): IntArray {
if (right - left < 2) {
return array.sliceArray(left..right)
}
val mid = (left + right) / 2
val leftTask = MergeSortTask(array, left, mid)
val rightTask = MergeSortTask(array, mid + 1, right)
leftTask.fork()
val rightResult = rightTask.compute()
val leftResult = leftTask.join()
return merge(leftResult, rightResult)
}
private fun merge(left: IntArray, right: IntArray): IntArray {
val result = IntArray(left.size + right.size)
var i = 0; var j = 0; var k = 0
while (i < left.size && j < right.size) {
if (left[i] <= right[j]) {
result[k++] = left[i++]
} else {
result[k++] = right[j++]
}
}
while (i < left.size) result[k++] = left[i++]
while (j < right.size) result[k++] = right[j++]
return result
}
}
}
// Usage
val sorter = ParallelMergeSort()
val unsorted = intArrayOf(5, 2, 8, 1, 9, 3, 7, 4, 6)
val sorted = sorter.parallelMergeSort(unsorted)
println("Sorted: ${sorted.contentToString()}")
// Output: Sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9]
TypeScript/JavaScript doesn't support traditional threading or parallel algorithms. JavaScript runs in a single-threaded event loop model.
Dart doesn't support traditional threading or parallel algorithms. Dart uses isolates with separate memory spaces that communicate via message passing.
import Foundation
// Swift: Using parallel algorithms with proper synchronization
class ParallelMergeSort {
func parallelMergeSort(_ array: [Int]) -> [Int] {
if array.count <= 1 {
return array
}
let mid = array.count / 2
let left = Array(array[0..<mid])
let right = Array(array[mid..<array.count])
let leftSorted = parallelMergeSort(left)
let rightSorted = parallelMergeSort(right)
return merge(leftSorted, rightSorted)
}
private func merge(_ left: [Int], _ right: [Int]) -> [Int] {
var result: [Int] = []
var i = 0, j = 0
while i < left.count && j < right.count {
if left[i] <= right[j] {
result.append(left[i])
i += 1
} else {
result.append(right[j])
j += 1
}
}
while i < left.count {
result.append(left[i])
i += 1
}
while j < right.count {
result.append(right[j])
j += 1
}
return result
}
}
// Usage
let sorter = ParallelMergeSort()
let unsorted = [5, 2, 8, 1, 9, 3, 7, 4, 6]
let sorted = sorter.parallelMergeSort(unsorted)
print("Sorted: \(sorted)")
// Output: Sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9]
import multiprocessing
from concurrent.futures import ProcessPoolExecutor
# Python: Using parallel algorithms with multiprocessing
class ParallelMergeSort:
def parallel_merge_sort(self, array):
if len(array) <= 1:
return array
mid = len(array) // 2
left = array[:mid]
right = array[mid:]
with ProcessPoolExecutor() as executor:
left_future = executor.submit(self.parallel_merge_sort, left)
right_future = executor.submit(self.parallel_merge_sort, right)
left_sorted = left_future.result()
right_sorted = right_future.result()
return self.merge(left_sorted, right_sorted)
def merge(self, left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Usage
sorter = ParallelMergeSort()
unsorted = [5, 2, 8, 1, 9, 3, 7, 4, 6]
sorted_array = sorter.parallel_merge_sort(unsorted)
print(f"Sorted: {sorted_array}")
# Output: Sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Map-Reduce#
Map-reduce provides a simple pattern for large-scale parallel processing. The map phase applies a function to each input element in parallel, producing intermediate results. The reduce phase combines those results, also in parallel. This pattern handles massive datasets efficiently—think counting word frequencies in millions of documents.
import java.util.concurrent.*;
import java.util.stream.*;
import java.util.List;
import java.util.Map;
public class MapReduceExample {
public Map<String, Integer> wordCount(List<String> documents) {
return documents.parallelStream()
.flatMap(doc -> Arrays.stream(doc.split("\\s+")))
.collect(Collectors.groupingByConcurrent(
word -> word.toLowerCase(),
Collectors.summingInt(word -> 1)
));
}
public int sumOfSquares(List<Integer> numbers) {
return numbers.parallelStream()
.mapToInt(n -> n * n)
.sum();
}
public double average(List<Double> values) {
return values.parallelStream()
.mapToDouble(Double::doubleValue)
.average()
.orElse(0.0);
}
}
// Usage
MapReduceExample mapReduce = new MapReduceExample();
// Word count example
List<String> documents = Arrays.asList("hello world", "hello java", "world of java");
Map<String, Integer> wordCounts = mapReduce.wordCount(documents);
System.out.println("Word counts: " + wordCounts);
// Output: Word counts: {hello=2, world=2, java=2, of=1}
// Sum of squares
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
int sumSquares = mapReduce.sumOfSquares(numbers);
System.out.println("Sum of squares: " + sumSquares);
// Output: Sum of squares: 55
// Average
List<Double> values = Arrays.asList(10.0, 20.0, 30.0, 40.0, 50.0);
double avg = mapReduce.average(values);
System.out.println("Average: " + avg);
// Output: Average: 30.0
import java.util.concurrent.*
class MapReduceExample {
fun wordCount(documents: List<String>): Map<String, Int> {
return documents.parallelStream()
.flatMap { doc -> doc.split("\\s+").stream() }
.collect(Collectors.groupingByConcurrent(
{ it.lowercase() },
Collectors.summingInt { 1 }
))
}
fun sumOfSquares(numbers: List<Int>): Int {
return numbers.parallelStream()
.mapToInt { it * it }
.sum()
}
fun average(values: List<Double>): Double {
return values.parallelStream()
.mapToDouble { it }
.average()
.orElse(0.0)
}
}
// Usage
val mapReduce = MapReduceExample()
// Word count example
val documents = listOf("hello world", "hello kotlin", "world of kotlin")
val wordCounts = mapReduce.wordCount(documents)
println("Word counts: $wordCounts")
// Output: Word counts: {hello=2, world=2, kotlin=2, of=1}
// Sum of squares
val numbers = listOf(1, 2, 3, 4, 5)
val sumSquares = mapReduce.sumOfSquares(numbers)
println("Sum of squares: $sumSquares")
// Output: Sum of squares: 55
// Average
val values = listOf(10.0, 20.0, 30.0, 40.0, 50.0)
val avg = mapReduce.average(values)
println("Average: $avg")
// Output: Average: 30.0
TypeScript/JavaScript doesn't support traditional threading or parallel algorithms. JavaScript runs in a single-threaded event loop model.
Dart doesn't support traditional threading or parallel algorithms. Dart uses isolates with separate memory spaces that communicate via message passing.
import Foundation
// Swift: Using parallel algorithms with proper synchronization
class MapReduceExample {
func wordCount(documents: [String]) -> [String: Int] {
var wordCounts: [String: Int] = [:]
for document in documents {
let words = document.components(separatedBy: .whitespaces)
for word in words {
let lowercaseWord = word.lowercased()
wordCounts[lowercaseWord, default: 0] += 1
}
}
return wordCounts
}
func sumOfSquares(_ numbers: [Int]) -> Int {
return numbers.map { $0 * $0 }.reduce(0, +)
}
func average(_ values: [Double]) -> Double {
return values.reduce(0, +) / Double(values.count)
}
}
// Usage
let mapReduce = MapReduceExample()
// Word count example
let documents = ["hello world", "hello swift", "world of swift"]
let wordCounts = mapReduce.wordCount(documents: documents)
print("Word counts: \(wordCounts)")
// Output: Word counts: ["hello": 2, "world": 2, "swift": 2, "of": 1]
// Sum of squares
let numbers = [1, 2, 3, 4, 5]
let sumSquares = mapReduce.sumOfSquares(numbers)
print("Sum of squares: \(sumSquares)")
// Output: Sum of squares: 55
// Average
let values = [10.0, 20.0, 30.0, 40.0, 50.0]
let avg = mapReduce.average(values)
print("Average: \(avg)")
// Output: Average: 30.0
import multiprocessing
from concurrent.futures import ProcessPoolExecutor
from collections import Counter
# Python: Using parallel algorithms with multiprocessing
class MapReduceExample:
def word_count(self, documents):
word_counts = Counter()
for document in documents:
words = document.split()
for word in words:
word_counts[word.lower()] += 1
return dict(word_counts)
def sum_of_squares(self, numbers):
return sum(x * x for x in numbers)
def average(self, values):
return sum(values) / len(values) if values else 0
def parallel_word_count(self, documents):
with ProcessPoolExecutor() as executor:
futures = [executor.submit(self.word_count, [doc]) for doc in documents]
results = [future.result() for future in futures]
# Combine results
final_counts = Counter()
for result in results:
final_counts.update(result)
return dict(final_counts)
# Usage
map_reduce = MapReduceExample()
# Word count example
documents = ["hello world", "hello python", "world of python"]
word_counts = map_reduce.word_count(documents)
print(f"Word counts: {word_counts}")
# Output: Word counts: {'hello': 2, 'world': 2, 'python': 2, 'of': 1}
# Sum of squares
numbers = [1, 2, 3, 4, 5]
sum_squares = map_reduce.sum_of_squares(numbers)
print(f"Sum of squares: {sum_squares}")
# Output: Sum of squares: 55
# Average
values = [10.0, 20.0, 30.0, 40.0, 50.0]
avg = map_reduce.average(values)
print(f"Average: {avg}")
# Output: Average: 30.0