Учебная задача. Симулятор обработки сетевых пакетов. Дан буфер размера size и набор Npac пар чисел Ti-Di. В моменты Ti приходят пакеты, на обработку которых нужно Di времени. Di может быть 0. Несколько Ti подряд могут совпадать, но они гарантированно не убывают. Пришедший пакет добавляется в хвост буфера. Обрабатывается только пакет в голове, на 0-м месте, остальные ждут. Если подряд идут несколько пакетов длительностью 0, они обрабатываются в одном такте, в том же, когда первый из них дошёл до головы, и этот же такт засчитывается и в обработку следующего за ними ненулевого пакета. Когда буфер заполнен, приходящие пакеты сбрасываются.
Требуется выдать массив времён, когда началась обработка каждого пакета. Или «-1», если пакет был сброшен.
Я сделал предельно просто — счётчик тактов времени, на каждом такте пробегается вначале очередь, всем ждущим снижается время ожидания, если что-то доходит до головы — обрабатывается, затем пробегается массив пакетов от первого необработанного до первого со временем прибытия Ti больше текущего. Работает правильно, но долго.
Попробовал ускорить, двигать время не по 1 такту, а определять дельты до прихода ближайшего пакета или окончания обработки головы очереди, что раньше. Выигрыш получился несущественный. Оптимизации с заменой list на collections.deque и хранением длин массивов в отдельных переменных дали прирост 10-20%
Почитал советы — говорят, надо избавиться от цикла со счётчиком времени и работать с событиями. Какая принципиальная разница с дельтами? Попробовал, запутался в алгоритме, постоянно что-то теряется. Получилось гораздо быстрее, но возможно, потому, что неправильно.
Вариант с дельтами:
import time, sys, collections
ar = list(map(int, sys.stdin.read().split()))
size, npac = ar[0:2]
packets = [ar[lcv*2+2:lcv*2+4] for lcv in range(npac)]
packets = [{'arrival':arrival, 'duration':duration, 'start':-1, 'time':duration} for arrival, duration in packets]
maxtime = 1 + sum(p['arrival'] + p['duration'] for p in packets)
queue = collections.deque()
curp = 0 # номер первого необработанного пакета
t = 0
nextarrival = 0
nextqueue = 0
delta = 1
while t < maxtime:
# обработать очередь
if queue:
queue[0]['time'] -= 1
if queue[0]['time'] <= 0:
queue.popleft()
while queue and queue[0]['time'] <= 0:
queue[0]['start'] = t
queue.popleft()
if queue:
queue[0]['start'] = t
nextqueue = queue[0]['time']
# проверить прибытие пакетов
for i in range(curp, npac):
p = packets[i]
if t < p['arrival']:
nextarrival = p['arrival']
break
curp = i+1
if t == p['arrival']:
if not queue:
p['start'] = t
if p['duration'] > 0:
queue.append(p)
elif len(queue) < size:
queue.append(p)
else:
p['start'] = -1
# выход, всё закончилось
if len(queue) < 2 and curp >= npac:
break
# время следующего события
tlast = t
t = max(min(nextarrival, nextqueue), t+1)
delta = t - tlast
for p in packets:
print(p['start'])
Что и как здесь можно ускорить?
Или как делать иначе? Цикл по массиву пакетов, где в ожидании очередного прибытия прокручивается очередь, у меня получился слишком запутанным. Другие варианты есть?
Ответ: Свёл к следующему:
import sys, collections
ar = list(map(int, sys.stdin.read().split()))
size, npac = ar[0:2]
packets = [ar[lcv*2+2:lcv*2+4] for lcv in range(npac)]
queue = collections.deque()
log = [-1 for _ in range(npac)]
t0 = 0 # tc = 0
for pn in range(npac):
cparrival, cpduration = packets[pn]
# tc <= cparrival
while len(queue) > 0 and t0 + queue[0][0] <= cparrival :
d0, pn0 = queue.popleft()
t0 = t0 + d0 #tc
if queue:
log[queue[0][1]] = t0
#t0 = tc
#tc = cparrival
if len(queue) < size:
queue.append([cpduration, pn])
if len(queue) == 1:
log[pn] = cparrival
t0 = cparrival
#tc = t0
while queue:
d0, pn0 = queue.popleft()
print(log)
Вычислительная часть работает вдвое быстрее.
