Карточки
Тесты
Главная
Курсы
Подписка
22. Вычислительные процессы: #298254
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы – время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение $0$.
Пример организации данных в файле:
| ID процесса $B$ | Время выполнения процесса $B$ (мс) | ID процесса(ов) $A$ |
|---|---|---|
| $1$ | $4$ | $0$ |
| $2$ | $3$ | $0$ |
| $3$ | $1$ | $1$; $2$ |
| $4$ | $7$ | $3$ |
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $10$, $4$, $1$, $14$ и $2$ завершатся на $16$, $17$, $22$, $22$ и $24$ мс соответственно.
Процесс $5$ зависит от $1$ и $2$: позже заканчивается $2$ (на $24$ мс), значит $5$ завершится на $24+18=42$ мс. Процесс $16$ зависит от $14$ и тоже завершится на $22+20=42$ мс. Процесс $3$ зависит от $1$ и $2$ и завершится на $24+24=48$ мс.
Процесс $6$ зависит от $4$ и $5$, позже заканчивается $5$, поэтому $6$ завершится на $42+15=57$ мс. Процесс $7$ зависит от $1$, $4$ и $6$: позже всех $6$, значит $7$ завершится на $57+17=74$ мс. Процесс $9$ зависит от $2$ и $6$ и завершится на $57+19=76$ мс, процесс $11$ зависит от $4$ и $7$ и завершится на $74+18=92$ мс.
Процесс $8$ зависит от $3$, $5$ и $7$: позже всех заканчивается $7$ (на $74$ мс), поэтому $8$ завершится на $74+22=96$ мс. От него зависят $13$ и $12$. Процесс $13$ зависит от $5$, $8$ и $10$ и завершится на $96+19=115$ мс, процесс $12$ зависит от $8$ и завершится на $96+22=118$ мс. Процесс $17$ зависит от $12$ и завершится на $118+15=133$ мс.
Наконец, процесс $15$ зависит от $13$ и $14$: позже заканчивается $13$ (на $115$ мс), значит $15$ завершится на $115+21=136$ мс. Это позже, чем процесс $17$, поэтому именно $15$ и определяет ответ.
Таким образом, вся совокупность процессов завершится на $136$ мс.
| Время, мс | ID процесса |
|---|---|
| $16$ | $10$ |
| $17$ | $4$ |
| $22$ | $1$, $14$ |
| $24$ | $2$ |
| $42$ | $5$, $16$ |
| $48$ | $3$ |
| $57$ | $6$ |
| $74$ | $7$ |
| $76$ | $9$ |
| $92$ | $11$ |
| $96$ | $8$ |
| $115$ | $13$ |
| $118$ | $12$ |
| $133$ | $17$ |
| $136$ | $15$ |
Приведём другое решение на языке Python.
import pandas as pd
from functools import lru_cache
df = pd.read_excel('22-21.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)
print(max(finish(p) for p in t)) # 136
Здесь две длинные ветки расходятся после процесса $8$: одна идёт через $12$ и $17$ и заканчивается на $133$ мс, другая через $13$ и $15$ — на $136$ мс. Поэтому нужен максимум по всем процессам, а не по какой-то одной цепочке. Обратите внимание и на разбор третьего столбца: зависимости в файле записаны с разными пробелами, их надо убрать перед разбиением по «;».
20
