22. Вычислительные процессы: Например, для приведённой таблицы это 13 мс (процесс 5 может…
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение $0$.
Типовой пример организации данных в файле:
| ID процесса $B$ | Время выполнения процесса $B$ (мс) | ID процесса(-ов) $A$ |
|---|---|---|
| $1$ | $3$ | $0$ |
| $2$ | $4$ | $1$ |
| $3$ | $2$ | $2$; $4$ |
| $4$ | $5$ | $0$ |
| $5$ | $8$ | $1$; $4$ |
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Например, для приведённой таблицы это $13$ мс (процесс $5$ может выполниться только после окончания процесса $4$, их общая продолжительность $5 + 8 = 13$ мс).
Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $106$, $107$ и $112$ завершатся на $3$, $5$ и $6$ мс соответственно. Процесс $105$ зависит от $107$, значит завершится на $5+1=6$ мс. Процесс $102$ тоже зависит от $107$ и завершится на $5+5=10$ мс, а процесс $119$ зависит от $112$ и $106$: позже заканчивается $112$ (на $6$ мс), поэтому $119$ завершится на $6+4=10$ мс.
Дальше процесс $101$ зависит от $102$ и $119$, оба заканчиваются на $10$ мс, значит $101$ завершится на $10+1=11$ мс. Процесс $109$ зависит от $112$ и завершится на $6+5=11$ мс, процесс $118$ зависит от $101$ и $109$ — оба на $11$ мс, поэтому $118$ завершится на $11+3=14$ мс. Процесс $110$ зависит от $118$ и $119$, позже заканчивается $118$, значит $110$ завершится на $14+6=20$ мс. Процесс $111$ зависит от $110$ и завершится на $20+4=24$ мс, а процесс $117$ зависит от $111$, следовательно, выполнится на $24+5=29$ мс.
Таким образом, вся совокупность процессов завершится на $29$ мс.
| Время, мс | ID процесса |
|---|---|
| $3$ | $106$ |
| $5$ | $107$ |
| $6$ | $105$, $112$ |
| $10$ | $102$, $119$ |
| $11$ | $101$, $104$, $109$ |
| $12$ | $123$ |
| $13$ | $124$ |
| $14$ | $103$, $116$, $118$ |
| $15$ | $113$, $121$ |
| $16$ | $108$ |
| $17$ | $125$ |
| $19$ | $114$ |
| $20$ | $110$, $115$, $122$ |
| $23$ | $120$ |
| $24$ | $111$ |
| $29$ | $117$ |
Приведём другое решение на языке Python.
import sys
d = {'0': 0}
for elem in sys.stdin:
num, dur, *subs = elem.replace(';', ' ').split()
d[num] = max([d[i] for i in subs]) + int(dur)
print(max(d.values()))
Запустив программу, вводим данные из таблицы построчно, цифры в строках разделяем пробелом. Закончив ввод всех строк таблицы, необходимо нажать CTRL+D.
Примечание. Способ работает при условии, что процессы в файле идут в таком порядке, что каждый встречается уже после всех тех, от которых он зависит. Если порядок произвольный, надёжнее читать файл целиком и считать время завершения рекурсией с кэшированием:
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-01.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]).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)
print(max(finish(p) for p in t)) # 29