Карточки
Тесты
Главная
Курсы
Подписка
22. Вычислительные процессы: #298268
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение $0$.
Определите минимальное время (в мс), за которое завершатся $16$ процессов. Считать, что каждый процесс начинается в самое раннее допустимое время. Время отсчитывается непрерывно с первой миллисекунды. В ответе укажите только число – количество миллисекунд.
Типовой пример организации данных в файле:
| ID процесса $B$ | Время выполнения процесса $B$ (мс) | ID процесса(-ов) $A$ |
|---|---|---|
| $1$ | $3$ | $0$ |
| $2$ | $4$ | $1$ |
| $3$ | $2$ | $2$; $4$ |
| $4$ | $5$ | $0$ |
| $5$ | $8$ | $1$; $4$ |
| $6$ | $3$ | $1$ |
Для приведённой таблицы процесс $3$ начинается на $8$-й мс, заканчивается на $9$-й мс.
Составим таблицу, на какой мс завершится каждый из процессов, и будем накапливать их количество. Искомое время — момент завершения $16$-го по счёту процесса.
Независимые процессы $3$, $8$ и $13$ завершаются на $6$ мс — это сразу три процесса. Процесс $17$ зависит от $8$ и завершится на $6+1=7$ мс, процесс $23$ зависит от $3$ и тоже завершится на $7$ мс. Процесс $21$ зависит от $13$ и завершится на $8$ мс, процесс $20$ зависит от $21$ — на $9$ мс. К этому моменту завершено $7$ процессов.
Процесс $12$ зависит от $17$, $13$ и $8$: позже всех $17$ (на $7$ мс), значит $12$ завершится на $7+5=12$ мс. Процесс $19$ зависит от $12$ и завершится на $13$ мс, процесс $14$ зависит от $17$ и $8$ и тоже завершится на $7+6=13$ мс — всего $10$.
Процесс $2$ зависит от $19$, $12$ и $8$: позже всех $19$ (на $13$ мс), поэтому $2$ завершится на $13+2=15$ мс. Процесс $25$ зависит от $3$ и $14$ и завершится на $13+2=15$ мс — всего $12$.
Процесс $4$ зависит от $19$ и $17$ и завершится на $13+5=18$ мс, процесс $7$ зависит от $14$, $17$ и $2$: позже всех $2$ (на $15$ мс), значит $7$ завершится на $15+3=18$ мс — всего $14$.
И наконец на $19$ мс заканчиваются сразу два процесса: $16$ зависит от $2$ и завершается на $15+4=19$ мс, а $22$ зависит от $19$ и завершается на $13+6=19$ мс. Они и доводят счёт до $16$.
Значит минимальное время, за которое завершатся $16$ процессов, равно $19$ мс.
| Время, мс | ID процесса | Всего завершено |
|---|---|---|
| $6$ | $3$, $8$, $13$ | $3$ |
| $7$ | $17$, $23$ | $5$ |
| $8$ | $21$ | $6$ |
| $9$ | $20$ | $7$ |
| $12$ | $12$ | $8$ |
| $13$ | $14$, $19$ | $10$ |
| $15$ | $2$, $25$ | $12$ |
| $18$ | $4$, $7$ | $14$ |
| $19$ | $16$, $22$ | $16$ |
| $20$ | $9$ | $17$ |
| $21$ | $11$ | $18$ |
| $23$ | $1$ | $19$ |
| $24$ | $10$ | $20$ |
| $25$ | $24$ | $21$ |
| $26$ | $15$ | $22$ |
| $28$ | $5$ | $23$ |
| $29$ | $6$, $18$ | $25$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-28.ods', engine='odf', header=None, skiprows=1)
t, dep = {}, {}
for _, row in df.iterrows():
pid = int(row[0])
t[pid] = int(row[1])
s = str(row[2]).replace(' ', '').strip()
dep[pid] = [] if s == '0' else [int(x) for x in s.split(';')]
@lru_cache(None)
def finish(p): # момент завершения процесса p
return t[p] + max([finish(d) for d in dep[p]], default=0)
times = sorted(finish(p) for p in t)
print(times[15]) # 19 — время завершения 16-го по счёту процесса
Отсортировав времена завершения по возрастанию, достаточно взять элемент с индексом $15$. Обратите внимание, что на $19$-й мс заканчиваются сразу два процесса, поэтому счёт перескакивает с $14$ сразу до $16$.
20
