Fizz Buzz Multithreaded

アルゴリズム概要

4つの異なるスレッドが協調して、1からnまでのFizzBuzz列を正しい順序で出力する問題です。各スレッドは特定の条件を満たす番号のみを処理します。

Input: n = 15
Output: [1, 2, "fizz", 4, "buzz", "fizz", 7, 8, "fizz", "buzz", 11, "fizz", 13, 14, "fizzbuzz"]

Input: n = 5
Output: [1, 2, "fizz", 4, "buzz"]

ステップバイステップ解説

Python実装

from threading import Lock
from typing import Callable


class FizzBuzz:
    """
    マルチスレッド FizzBuzz 実装（Lock ベース）

    Time Complexity: O(n)
    Space Complexity: O(1)
    """

    __slots__ = ('n', 'current', 'lock')

    def __init__(self, n: int) -> None:
        """
        初期化

        Args:
            n: 出力する数値の上限（1 <= n <= 50）
        """
        self.n: int = n
        self.current: int = 1
        self.lock: Lock = Lock()

    def fizz(self, printFizz: Callable[[], None]) -> None:
        """
        3の倍数（5の倍数を除く）で "fizz" を出力

        条件: i % 3 == 0 and i % 5 != 0
        """
        while True:
            with self.lock:
                # 終了条件チェック
                if self.current > self.n:
                    break

                # 自分の担当番号かチェック
                if self.current % 3 == 0 and self.current % 5 != 0:
                    printFizz()
                    self.current += 1

    def buzz(self, printBuzz: Callable[[], None]) -> None:
        """
        5の倍数（3の倍数を除く）で "buzz" を出力

        条件: i % 5 == 0 and i % 3 != 0
        """
        while True:
            with self.lock:
                if self.current > self.n:
                    break

                if self.current % 5 == 0 and self.current % 3 != 0:
                    printBuzz()
                    self.current += 1

    def fizzbuzz(self, printFizzBuzz: Callable[[], None]) -> None:
        """
        15の倍数で "fizzbuzz" を出力

        条件: i % 15 == 0（3と5の公倍数）
        """
        while True:
            with self.lock:
                if self.current > self.n:
                    break

                # 15で割る方が 3と5 両方チェックより高速
                if self.current % 15 == 0:
                    printFizzBuzz()
                    self.current += 1

    def number(self, printNumber: Callable[[int], None]) -> None:
        """
        3でも5でも割り切れない数値を出力

        条件: i % 3 != 0 and i % 5 != 0
        """
        while True:
            with self.lock:
                if self.current > self.n:
                    break

                if self.current % 3 != 0 and self.current % 5 != 0:
                    printNumber(self.current)
                    self.current += 1

フローチャート

フローの説明：
1. スレッド開始後、ロックを取得して共有状態にアクセス
2. current > n なら終了、そうでなければ次へ
3. 自分の担当番号でなければロックを解放して再試行
4. 担当番号なら printXXX() を実行し、current をインクリメント
5. ロックを解放して次の番号の処理へループバック

計算量分析