Учебная задача. Симулятор обработки сетевых пакетов. Дан буфер размера 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'])
Что и как здесь можно ускорить?
Или как делать иначе? Цикл по массиву пакетов, где в ожидании очередного прибытия прокручивается очередь, у меня получился слишком запутанным. Другие варианты есть?
