This repository was archived by the owner on Dec 2, 2021. It is now read-only.
Repository navigation
Expand file tree
/
Copy pathtaxi_sim0.py
More file actions
257 lines (200 loc) · 9.88 KB
/
Copy pathtaxi_sim0.py
File metadata and controls
257 lines (200 loc) · 9.88 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
"""
Taxi simulator
Sample run with two cars, random seed 10. This is a valid doctest.
>>> main(num_taxis=2, seed=10)
taxi: 0 Event(time=0, proc=0, action='leave garage')
taxi: 0 Event(time=4, proc=0, action='pick up passenger')
taxi: 1 Event(time=5, proc=1, action='leave garage')
taxi: 1 Event(time=9, proc=1, action='pick up passenger')
taxi: 0 Event(time=10, proc=0, action='drop off passenger')
taxi: 1 Event(time=12, proc=1, action='drop off passenger')
taxi: 0 Event(time=17, proc=0, action='pick up passenger')
taxi: 1 Event(time=19, proc=1, action='pick up passenger')
taxi: 1 Event(time=21, proc=1, action='drop off passenger')
taxi: 1 Event(time=24, proc=1, action='pick up passenger')
taxi: 0 Event(time=28, proc=0, action='drop off passenger')
taxi: 1 Event(time=28, proc=1, action='drop off passenger')
taxi: 0 Event(time=29, proc=0, action='going home')
taxi: 1 Event(time=30, proc=1, action='pick up passenger')
taxi: 1 Event(time=61, proc=1, action='drop off passenger')
taxi: 1 Event(time=62, proc=1, action='going home')
*** end of events ***
See explanation and longer sample run at the end of this module.
"""
import sys
import random
import collections
import queue
import argparse
DEFAULT_NUMBER_OF_TAXIS = 3
DEFAULT_END_TIME = 80
SEARCH_DURATION = 4
TRIP_DURATION = 10
DEPARTURE_INTERVAL = 5
Event = collections.namedtuple('Event', 'time proc action')
def compute_delay(interval):
"""Compute action delay using exponential distribution"""
return int(random.expovariate(1/interval)) + 1
# BEGIN TAXI_PROCESS
def taxi_process(ident, trips, start_time=0): # <1>
"""Yield to simulator issuing event at each state change"""
time = yield Event(start_time, ident, 'leave garage') # <2>
for i in range(trips): # <3>
prowling_ends = time + compute_delay(SEARCH_DURATION) # <4>
time = yield Event(prowling_ends, ident, 'pick up passenger') # <5>
trip_ends = time + compute_delay(TRIP_DURATION) # <6>
time = yield Event(trip_ends, ident, 'drop off passenger') # <7>
yield Event(time + 1, ident, 'going home') # <8>
# end of taxi process # <9>
# END TAXI_PROCESS
# BEGIN TAXI_SIMULATOR
class Simulator:
def __init__(self, procs_map):
self.events = queue.PriorityQueue()
self.procs = dict(procs_map)
def run(self, end_time): # <1>
"""Schedule and display events until time is up"""
# schedule the first event for each cab
for _, proc in sorted(self.procs.items()): # <2>
first_event = next(proc) # <3>
self.events.put(first_event) # <4>
# main loop of the simulation
time = 0
while time < end_time: # <5>
if self.events.empty(): # <6>
print('*** end of events ***')
break
# get and display current event
current_event = self.events.get() # <7>
print('taxi:', current_event.proc, # <8>
current_event.proc * ' ', current_event)
# schedule next action for current proc
time = current_event.time # <9>
proc = self.procs[current_event.proc] # <10>
try:
next_event = proc.send(time) # <11>
except StopIteration:
del self.procs[current_event.proc] # <12>
else:
self.events.put(next_event) # <13>
else: # <14>
msg = '*** end of simulation time: {} events pending ***'
print(msg.format(self.events.qsize()))
# END TAXI_SIMULATOR
def main(end_time=DEFAULT_END_TIME, num_taxis=DEFAULT_NUMBER_OF_TAXIS,
seed=None):
"""Initialize random generator, build procs and run simulation"""
if seed is not None:
random.seed(seed) # get reproducible results
taxis = {i: taxi_process(i, (i+1)*2, i*DEPARTURE_INTERVAL)
for i in range(num_taxis)}
sim = Simulator(taxis)
sim.run(end_time)
if __name__ == '__main__':
parser = argparse.ArgumentParser(
description='Taxi fleet simulator.')
parser.add_argument('-e', '--end-time', type=int,
default=DEFAULT_END_TIME,
help='simulation end time; default = %s'
% DEFAULT_END_TIME)
parser.add_argument('-t', '--taxis', type=int,
default=DEFAULT_NUMBER_OF_TAXIS,
help='number of taxis running; default = %s'
% DEFAULT_NUMBER_OF_TAXIS)
parser.add_argument('-s', '--seed', type=int, default=None,
help='random generator seed (for testing)')
args = parser.parse_args()
main(args.end_time, args.taxis, args.seed)
"""
Notes for the ``taxi_process`` coroutine::
<1> `taxi_process` will be called once per taxi, creating a generator
object to represent its operations. `ident` is the number of the taxi
(eg. 0, 1, 2 in the sample run); `trips` is the number of trips this
taxi will make before going home; `start_time` is when the taxi
leaves the garage.
<2> The first `Event` yielded is `'leave garage'`. This suspends the
coroutine, and lets the simulation main loop proceed to the next
scheduled event. When it's time to reactivate this process, the main
loop will `send` the current simulation time, which is assigned to
`time`.
<3> This block will be repeated once for each trip.
<4> The ending time of the search for a passenger is computed.
<5> An `Event` signaling passenger pick up is yielded. The coroutine
pauses here. When the time comes to reactivate this coroutine,
the main loop will again `send` the current time.
<6> The ending time of the trip is computed, taking into account the
current `time`.
<7> An `Event` signaling passenger drop off is yielded. Coroutine
suspended again, waiting for the main loop to send the time of when
it's time to continue.
<8> The `for` loop ends after the given number of trips, and a final
`'going home'` event is yielded, to happen 1 minute after the current
time. The coroutine will suspend for the last time. When reactivated,
it will be sent the time from the simulation main loop, but here I
don't assign it to any variable because it will not be useful.
<9> When the coroutine falls off the end, the coroutine object raises
`StopIteration`.
Notes for the ``Simulator.run`` method::
<1> The simulation `end_time` is the only required argument for `run`.
<2> Use `sorted` to retrieve the `self.procs` items ordered by the
integer key; we don't care about the key, so assign it to `_`.
<3> `next(proc)` primes each coroutine by advancing it to the first
yield, so it's ready to be sent data. An `Event` is yielded.
<4> Add each event to the `self.events` `PriorityQueue`. The first
event for each taxi is `'leave garage'`, as seen in the sample run
(ex_taxi_process>>).
<5> Main loop of the simulation: run until the current `time` equals
or exceeds the `end_time`.
<6> The main loop may also exit if there are no pending events in the
queue.
<7> Get `Event` with the smallest `time` in the queue; this is the
`current_event`.
<8> Display the `Event`, identifying the taxi and adding indentation
according to the taxi id.
<9> Update the simulation time with the time of the `current_event`.
<10> Retrieve the coroutine for this taxi from the `self.procs`
dictionary.
<11> Send the `time` to the coroutine. The coroutine will yield the
`next_event` or raise `StopIteration` it's finished.
<12> If `StopIteration` was raised, delete the coroutine from the
`self.procs` dictionary.
<13> Otherwise, put the `next_event` in the queue.
<14> If the loop exits because the simulation time passed, display the
number of events pending (which may be zero by coincidence,
sometimes).
Sample run from the command line, seed=24, total elapsed time=160::
# BEGIN TAXI_SAMPLE_RUN
$ python3 taxi_sim.py -s 24 -e 160
taxi: 0 Event(time=0, proc=0, action='leave garage')
taxi: 0 Event(time=5, proc=0, action='pick up passenger')
taxi: 1 Event(time=5, proc=1, action='leave garage')
taxi: 1 Event(time=6, proc=1, action='pick up passenger')
taxi: 2 Event(time=10, proc=2, action='leave garage')
taxi: 2 Event(time=11, proc=2, action='pick up passenger')
taxi: 2 Event(time=23, proc=2, action='drop off passenger')
taxi: 0 Event(time=24, proc=0, action='drop off passenger')
taxi: 2 Event(time=24, proc=2, action='pick up passenger')
taxi: 2 Event(time=26, proc=2, action='drop off passenger')
taxi: 0 Event(time=30, proc=0, action='pick up passenger')
taxi: 2 Event(time=31, proc=2, action='pick up passenger')
taxi: 0 Event(time=43, proc=0, action='drop off passenger')
taxi: 0 Event(time=44, proc=0, action='going home')
taxi: 2 Event(time=46, proc=2, action='drop off passenger')
taxi: 2 Event(time=49, proc=2, action='pick up passenger')
taxi: 1 Event(time=70, proc=1, action='drop off passenger')
taxi: 2 Event(time=70, proc=2, action='drop off passenger')
taxi: 2 Event(time=71, proc=2, action='pick up passenger')
taxi: 2 Event(time=79, proc=2, action='drop off passenger')
taxi: 1 Event(time=88, proc=1, action='pick up passenger')
taxi: 2 Event(time=92, proc=2, action='pick up passenger')
taxi: 2 Event(time=98, proc=2, action='drop off passenger')
taxi: 2 Event(time=99, proc=2, action='going home')
taxi: 1 Event(time=102, proc=1, action='drop off passenger')
taxi: 1 Event(time=104, proc=1, action='pick up passenger')
taxi: 1 Event(time=135, proc=1, action='drop off passenger')
taxi: 1 Event(time=136, proc=1, action='pick up passenger')
taxi: 1 Event(time=151, proc=1, action='drop off passenger')
taxi: 1 Event(time=152, proc=1, action='going home')
*** end of events ***
# END TAXI_SAMPLE_RUN
"""