pythonadvanced15 minutes

Fix Bug in Parallel Fibonacci Computation with Memoization

Debug and fix the given Python code that aims to compute Fibonacci numbers efficiently using recursion with memoization and parallel execution. The current implementation has subtle bugs causing incorrect results and inefficient execution.

Challenge prompt

You are given a Python function designed to calculate a list of Fibonacci numbers for multiple input values concurrently using recursion, memoization, and multiprocessing. However, the code contains bugs that lead to wrong results and runtime errors. Your task is to identify and fix these bugs so that the function returns correct Fibonacci numbers for each input and utilizes multiprocessing properly without errors.

Guidance

• Check the proper use and sharing of memoization cache among concurrent processes.
• Ensure the multiprocessing part initializes and collects results correctly.
• Review recursive Fibonacci logic for correctness under memoization.

Hints

• Memoization dictionary should not be shared across processes by passing it as a function argument.
• Python multiprocessing pools require careful handling of function arguments and return values.
• Check base cases of the Fibonacci function and how recursion results are combined.

Starter code

import multiprocessing

memo = {0: 0, 1: 1}

def fib(n, memo=memo):
    if n in memo:
        return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

def parallel_fib(numbers):
    with multiprocessing.Pool() as pool:
        results = pool.map(fib, numbers)
    return results

inputs = [35, 36, 37]
print(parallel_fib(inputs))

Expected output

[9227465, 14930352, 24157817]

Core concepts

recursionmemoizationmultiprocessingdebugging

Challenge a Friend

Send this duel to someone else and see if they can solve it.