Python多线程经典问题之乘客做公交车算法实例

下面是详细讲解“Python多线程经典问题之乘客做公交车算法实例”的完整攻略。

1. 算法说明

这个算法的思路是：有一辆定容量的公交车，有多个乘客要乘坐这辆公交车。每个乘客到达车站的时间和想要乘坐的公交车到达车站的时间都是随机的。如果乘客到达车站的时间早于或等于公交车到站时间，则该乘客可以乘坐这辆公交车。公交车的容量有限，如果乘客已经坐满了，则其他乘客只能等待下一班公交车。

2. 代码实现

这个算法可以用Python的多线程来实现，我们可以将每个乘客看成一个线程，公交车看成一个线程锁。具体实现逻辑如下：

import threading
import time
import random

class Bus(threading.Thread):
    def __init__(self, capacity):
        threading.Thread.__init__(self)
        self.capacity = capacity
        self.passengers = []
        self.lock = threading.Lock()

    def run(self):
        while True:
            with self.lock:
                if len(self.passengers) == 0:
                    print("Bus is waiting for passengers.")
                else:
                    print("Bus is leaving with passengers:", self.passengers)
                    self.passengers.clear()
            time.sleep(2)

    def get_on(self, passenger):
        with self.lock:
            if len(self.passengers) == self.capacity:
                print("Passenger %d is waiting for another bus." % passenger.id)
                return False
            else:
                self.passengers.append(passenger)
                print("Passenger %d gets on the bus." % passenger.id)
                return True

class Passenger(threading.Thread):
    def __init__(self, id, bus_stop):
        threading.Thread.__init__(self)
        self.id = id
        self.arrive_time = random.randint(1, 5)
        self.bus_stop = bus_stop

    def run(self):
        time.sleep(self.arrive_time)
        print("Passenger %d arrives at bus stop at %ds." % (self.id, self.arrive_time))
        if self.bus_stop.get_on(self):
            print("Passenger %d gets on the bus at %ds." % (self.id, time.time()))
        else:
            print("Passenger %d could not get on the bus at %ds." % (self.id, time.time()))

上面代码中，Bus类表示公交车，Passenger类表示乘客。公交车的容量由capacity属性表示，passengers属性表示当前已经上车的乘客列表，lock属性是线程锁。在run方法中，公交车会等待所有乘客上完车后再出发。在get_on方法中，如果公交车已经坐满了，乘客会等待下一辆公交车。

乘客到达车站后，会等待一个随机时间，然后调用get_on方法上车。如果能上车，则打印输出相应信息；否则，等待另一辆公交车。

3. 示例说明

下面给出两个示例，分别演示了算法的运行情况：

示例一：乘客能全部上车

bus_stop = Bus(5)
bus_stop.start()

for i in range(10):
    passenger = Passenger(i, bus_stop)
    passenger.start()
    time.sleep(1)

输出结果如下：

Bus is waiting for passengers.
Passenger 0 arrives at bus stop at 3s.
Passenger 0 gets on the bus at 3.0059287548065186s.
Passenger 1 arrives at bus stop at 1s.
Passenger 1 gets on the bus at 3.0095062255859375s.
Passenger 2 arrives at bus stop at 4s.
Passenger 2 could not get on the bus at 4.0111541748046875s.
Passenger 3 arrives at bus stop at 5s.
Bus is leaving with passengers: [<_MainThread.Passenger object at 0x113d7fd90>, <_MainThread.Passenger object at 0x113d7fd30>, <_MainThread.Passenger object at 0x113d7fdd0>, <_MainThread.Passenger object at 0x113d7fe70>, <_MainThread.Passenger object at 0x113d7fd50>]
Passenger 1 arrives at bus stop at 6s.
Passenger 1 gets on the bus at 6.005651473999023s.
Passenger 4 arrives at bus stop at 5s.
Passenger 4 could not get on the bus at 6.009340763092041s.
Bus is waiting for passengers.
Bus is waiting for passengers.
Passenger 5 arrives at bus stop at 1s.
Passenger 5 gets on the bus at 8.01107406616211s.
Passenger 6 arrives at bus stop at 4s.
Passenger 6 gets on the bus at 8.013095140457153s.
Passenger 7 arrives at bus stop at 3s.
Passenger 7 gets on the bus at 8.015398979187012s.
Passenger 8 arrives at bus stop at 1s.
Passenger 8 gets on the bus at 8.018211364746094s.
Passenger 9 arrives at bus stop at 3s.
Passenger 9 could not get on the bus at 8.021400213241577s.
Bus is leaving with passengers: [<_MainThread.Passenger object at 0x113d860d0>, <_MainThread.Passenger object at 0x113d86110>, <_MainThread.Passenger object at 0x113d86150>, <_MainThread.Passenger object at 0x113d7fdd0>, <_MainThread.Passenger object at 0x113d86190>]
Bus is waiting for passengers.

这个示例中，有10个乘客，公交车容量为5。所有乘客都能成功上车。

示例二：乘客无法全部上车

bus_stop = Bus(5)
bus_stop.start()

for i in range(10):
    passenger = Passenger(i, bus_stop)
    passenger.start()
    time.sleep(1)
    if i == 4:
        time.sleep(3)