打印零与奇偶数

标签: 多线程

难度: Medium

现有函数 printNumber 可以用一个整数参数调用，并输出该整数到控制台。

例如，调用 printNumber(7) 将会输出 7 到控制台。

给你类 ZeroEvenOdd 的一个实例，该类中有三个函数：zero、even 和 odd 。ZeroEvenOdd 的相同实例将会传递给三个不同线程：

线程 A：调用 zero() ，只输出 0
线程 B：调用 even() ，只输出偶数
线程 C：调用 odd() ，只输出奇数

修改给出的类，以输出序列 "010203040506..." ，其中序列的长度必须为 2n 。

实现 ZeroEvenOdd 类：

ZeroEvenOdd(int n) 用数字 n 初始化对象，表示需要输出的数。
void zero(printNumber) 调用 printNumber 以输出一个 0 。
void even(printNumber) 调用printNumber 以输出偶数。
void odd(printNumber) 调用 printNumber 以输出奇数。

示例 1：

输入：n = 2
输出："0102"
解释：三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 "0102"。

示例 2：

输入：n = 5
输出："0102030405"

提示：

1 <= n <= 1000

Submission

运行时间: 34 ms

内存: 17.2 MB

from threading import Lock

class ZeroEvenOdd:
    def __init__(self, n):
        self.n = n
        self.zero_lock = Lock()
        self.odd_lock = Lock()
        self.even_lock = Lock()
        self.odd_lock.acquire()
        self.even_lock.acquire()

    def zero(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1):
            self.zero_lock.acquire()
            printNumber(0)
            if i % 2 == 0:
                self.even_lock.release()
            else:
                self.odd_lock.release()

    def even(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(2, self.n + 1, 2):
            self.even_lock.acquire()
            printNumber(i)
            self.zero_lock.release()

    def odd(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1, 2):
            self.odd_lock.acquire()
            printNumber(i)
            self.zero_lock.release()

def printNumber(x):
    print(x, end='')

n = 5
zeo = ZeroEvenOdd(n)

import threading

threads = []
threads.append(threading.Thread(target=zeo.zero, args=(printNumber,)))
threads.append(threading.Thread(target=zeo.even, args=(printNumber,)))
threads.append(threading.Thread(target=zeo.odd, args=(printNumber,)))

for thread in threads:
    thread.start()

for thread in threads:
    thread.join()

Explain

该题解使用了三个线程和三个锁（zero_lock, odd_lock, even_lock）来协调输出序列。初始时，odd_lock 和 even_lock 被锁定，zero_lock 可用。zero 函数先获取 zero_lock，输出 0，然后根据当前数字的奇偶性释放 odd_lock 或 even_lock。odd 函数获取 odd_lock，输出奇数，然后释放 zero_lock。even 函数获取 even_lock，输出偶数，然后释放 zero_lock。通过这种方式，三个线程交替执行，按照题目要求输出序列。

时间复杂度: O(n)

空间复杂度: O(1)

from threading import Lock

class ZeroEvenOdd:
    def __init__(self, n):
        self.n = n
        self.zero_lock = Lock()  # 用于控制输出 0 的锁
        self.odd_lock = Lock()  # 用于控制输出奇数的锁
        self.even_lock = Lock()  # 用于控制输出偶数的锁
        self.odd_lock.acquire()  # 初始时锁定 odd_lock
        self.even_lock.acquire()  # 初始时锁定 even_lock

    def zero(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1):
            self.zero_lock.acquire()  # 获取 zero_lock
            printNumber(0)  # 输出 0
            if i % 2 == 0:
                self.even_lock.release()  # 释放 even_lock，允许输出偶数
            else:
                self.odd_lock.release()  # 释放 odd_lock，允许输出奇数

    def even(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(2, self.n + 1, 2):
            self.even_lock.acquire()  # 获取 even_lock
            printNumber(i)  # 输出偶数
            self.zero_lock.release()  # 释放 zero_lock，允许输出 0

    def odd(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1, 2):
            self.odd_lock.acquire()  # 获取 odd_lock
            printNumber(i)  # 输出奇数
            self.zero_lock.release()  # 释放 zero_lock，允许输出 0

Explore

在`ZeroEvenOdd`类的实现中，使用三个锁来确保打印序列的严格交替性，这是因为锁提供了一种简单直观的方式来保证在任意时刻只有一个线程可以执行特定的操作。虽然信号量和条件变量也可以用来控制线程同步，锁在这种特定的用例中提供了更为直接的控制方式。使用锁可以明确地阻塞和唤醒具体的线程，这在需要严格控制执行顺序的场景下非常有效。

在初始化时立即锁定`odd_lock`和`even_lock`是为了确保在开始时只有`zero`函数可以执行输出。如果在第一次调用`odd()`或`even()`方法时才进行锁定，那么在程序刚开始运行时，这两个锁将是未锁定状态，可能导致`odd()`或`even()`方法在`zero()`方法之前执行，这会违背题目要求的输出序列。因此，预先锁定这些锁是为了控制执行顺序，保证从0开始输出。

在此实现中，`zero`函数在释放`even_lock`或`odd_lock`后，不存在线程安全问题或race condition。每次`zero`函数输出0之后，它通过释放`even_lock`或`odd_lock`恰当地控制了下一个应当执行的线程（奇数或偶数），这样的设计确保了在任意时刻只有一个线程在执行输出操作。由于每个锁在释放之前都是由相应的线程持有的，并且在相应的`odd`或`even`函数完成输出后再次释放`zero_lock`，这保持了输出顺序的准确性和线程的同步执行。

使用`if i % 2 == 0`来决定释放哪一个锁是基于当前数字的奇偶性来决定下一个应当执行的线程（偶数或奇数），这是一个非常明确和直接的逻辑判断。这种方法并不会导致线程不同步，即使在处理器调度不均或系统负载较高的情况下。在这种实现中，每个线程的执行依赖于其对应的锁状态，因此只要锁的逻辑被正确维护，线程同步就能得到保证。线程调度和系统负载可能影响线程的响应时间和执行速度，但不会影响线程间的同步逻辑。