交替打印字符串

难度: Medium

编写一个可以从 1 到 n 输出代表这个数字的字符串的程序，但是：

如果这个数字可以被 3 整除，输出 "fizz"。
如果这个数字可以被 5 整除，输出 "buzz"。
如果这个数字可以同时被 3 和 5 整除，输出 "fizzbuzz"。

例如，当 n = 15，输出： 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz。

假设有这么一个类：

class FizzBuzz {
  public FizzBuzz(int n) { ... }               // constructor
  public void fizz(printFizz) { ... }          // only output "fizz"
  public void buzz(printBuzz) { ... }          // only output "buzz"
  public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
  public void number(printNumber) { ... }      // only output the numbers
}

请你实现一个有四个线程的多线程版 FizzBuzz，同一个 FizzBuzz 实例会被如下四个线程使用：

线程A将调用 fizz() 来判断是否能被 3 整除，如果可以，则输出 fizz。
线程B将调用 buzz() 来判断是否能被 5 整除，如果可以，则输出 buzz。
线程C将调用 fizzbuzz() 来判断是否同时能被 3 和 5 整除，如果可以，则输出 fizzbuzz。
线程D将调用 number() 来实现输出既不能被 3 整除也不能被 5 整除的数字。

提示：

本题已经提供了打印字符串的相关方法，如 printFizz() 等，具体方法名请参考答题模板中的注释部分。

Submission

运行时间: 26 ms

内存: 16.6 MB

from threading import Thread, Lock, Condition

class FizzBuzz:
    def __init__(self, n: int):
        self.n = n
        self.lock = Lock()
        self.cv = Condition(self.lock)
        self.current = 1

    # printFizz() outputs "fizz"
    def fizz(self, printFizz: 'Callable[[], None]') -> None:
        with self.lock:
            while self.current <= self.n:
                if self.current % 3 == 0 and self.current % 5 != 0:  # Only divisible by 3
                    printFizz()
                    self.current += 1
                    self.cv.notify_all()
                else:
                    self.cv.wait()

    # printBuzz() outputs "buzz"
    def buzz(self, printBuzz: 'Callable[[], None]') -> None:
        with self.lock:
            while self.current <= self.n:
                if self.current % 5 == 0 and self.current % 3 != 0:  # Only divisible by 5
                    printBuzz()
                    self.current += 1
                    self.cv.notify_all()
                else:
                    self.cv.wait()

    # printFizzBuzz() outputs "fizzbuzz"
    def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
        with self.lock:
            while self.current <= self.n:
                if self.current % 3 == 0 and self.current % 5 == 0:  # Divisible by both 3 and 5
                    printFizzBuzz()
                    self.current += 1
                    self.cv.notify_all()
                else:
                    self.cv.wait()

    # printNumber(x) outputs "x", where x is an integer.
    def number(self, printNumber: 'Callable[[int], None]') -> None:
        with self.lock:
            while self.current <= self.n:
                if self.current % 3 != 0 and self.current % 5 != 0:  # Not divisible by 3 or 5
                    printNumber(self.current)
                    self.current += 1
                    self.cv.notify_all()
                else:
                    self.cv.wait()

def print_fizz():
    print("fizz")

def print_buzz():
    print("buzz")

def print_fizzbuzz():
    print("fizzbuzz")

def print_number(x):
    print(x)

n = 15
fizz_buzz = FizzBuzz(n)

threads = [
    Thread(target=fizz_buzz.fizz, args=(print_fizz,)),
    Thread(target=fizz_buzz.buzz, args=(print_buzz,)),
    Thread(target=fizz_buzz.fizzbuzz, args=(print_fizzbuzz,)),
    Thread(target=fizz_buzz.number, args=(print_number,))
]

for thread in threads:
    thread.start()

for thread in threads:
    thread.join()

Explain

这个题解使用了四个线程来并发处理从1到n的数字，每个线程根据数字的特性（能否被3、5整除）来执行特定的打印任务。利用锁（Lock）和条件变量（Condition）来同步不同的线程，确保在任意时刻只有一个线程能够执行并修改共享资源current的值。每个方法（fizz, buzz, fizzbuzz, number）对应一个线程，它们在内部循环中检查当前数字（self.current）是否符合打印条件，如果符合则打印并通知其他线程，否则等待其他线程的通知。

时间复杂度: O(n)

空间复杂度: O(1)

from threading import Thread, Lock, Condition

class FizzBuzz:
    def __init__(self, n: int):
        self.n = n
        self.lock = Lock()
        self.cv = Condition(self.lock)
        self.current = 1

    def fizz(self, printFizz: 'Callable[[], None]') -> None:
        with self.lock:
            while self.current <= self.n:
                if self.current % 3 == 0 and self.current % 5 != 0:
                    printFizz()
                    self.current += 1
                    self.cv.notify_all()
                else:
                    self.cv.wait()

    def buzz(self, printBuzz: 'Callable[[], None]') -> None:
        with self.lock:
            while self.current <= self.n:
                if self.current % 5 == 0 and self.current % 3 != 0:
                    printBuzz()
                    self.current += 1
                    self.cv.notify_all()
                else:
                    self.cv.wait()

    def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
        with self.lock:
            while self.current <= self.n:
                if self.current % 3 == 0 and self.current % 5 == 0:
                    printFizzBuzz()
                    self.current += 1
                    self.cv.notify_all()
                else:
                    self.cv.wait()

    def number(self, printNumber: 'Callable[[int], None]') -> None:
        with self.lock:
            while self.current <= self.n:
                if self.current % 3 != 0 and self.current % 5 != 0:
                    printNumber(self.current)
                    self.current += 1
                    self.cv.notify_all()
                else:
                    self.cv.wait()

# 示例函数，用于打印字符串

def print_fizz():
    print('fizz')

def print_buzz():
    print('buzz')

def print_fizzbuzz():
    print('fizzbuzz')

def print_number(x):
    print(x)

# 初始化FizzBuzz实例，并启动线程

n = 15
fizz_buzz = FizzBuzz(n)

threads = [
    Thread(target=fizz_buzz.fizz, args=(print_fizz,)),
    Thread(target=fizz_buzz.buzz, args=(print_buzz,)),
    Thread(target=fizz_buzz.fizzbuzz, args=(print_fizzbuzz,)),
    Thread(target=fizz_buzz.number, args=(print_number,))
]

for thread in threads:
    thread.start()

for thread in threads:
    thread.join()

Explore

在FizzBuzz类中，使用了一个锁（Lock）和条件变量（Condition）来确保同一时间只有一个线程可以修改`self.current`的值。每个线程在尝试读取或修改`self.current`之前必须先获取锁。这是通过`with self.lock:`语句块实现的，该语句块确保了在该块内的代码执行期间，当前线程持有锁。这样，当一个线程在修改`self.current`时，其他线程会被阻塞，直到锁被释放，确保了对`self.current`的访问和修改是线程安全的。

调用`self.cv.notify_all()`而不是`self.cv.notify()`确保所有等待的线程都被通知并有机会获取锁来检查条件是否已经满足其需要。因为该问题设计四个线程分别负责不同的打印任务，如果使用`self.cv.notify()`，则只会随机唤醒一个等待中的线程，这可能导致必要的条件更新被延迟处理，比如当前数字适合多个打印条件但只唤醒了一个相关线程。使用`self.cv.notify_all()`可以减少这种情况的发生，确保程序的正确性和效率。

如果数字n非常大，多线程方法相比单线程可能会有一定的性能提升，但这种提升可能不如预期明显。这是因为虽然多线程可以并行处理不同的打印任务（如fizz、buzz、fizzbuzz和number），但由于所有线程共享访问和修改同一个变量`self.current`，频繁的锁操作和线程间的同步可能导致较大的开销。此外，线程调度和上下文切换也可能增加额外的开销。因此，性能提升的程度依赖于系统的多线程管理效率和具体实现方式。

在多线程环境下，`self.cv.wait()`会使调用它的线程挂起，直到其他线程通过`self.cv.notify()`或`self.cv.notify_all()`发出通知。这个操作涉及线程的挂起和唤醒，会导致线程上下文切换，这是一个相对昂贵的操作。频繁的使用`self.cv.wait()`和对应的唤醒操作会增加系统的负担，降低程序的整体效率。此外，如果不当使用（如在不适当的时机调用`wait()`），可能导致死锁或者程序逻辑错误。因此，虽然`self.cv.wait()`是线程同步中必要的工具，但需要谨慎使用，确保在合适的逻辑和条件下调用。