[Из песочницы] Тонкости построения сетевых моделей в Python
Что является основным инструментом, который использует руководитель при управлении проектом? Принято считать, что основным инструментом руководителя проекта является календарный план, в основе которого лежит сетевая модель работ по проекту. Однажды мне довелось реализовать сетевую модель работ на языке Python (код и описание здесь). Ниже приведены уроки, извлеченные по результатам проделанной работы.
При построении сетевой модели часто возникает вопрос, в каком порядке создавать работы и устанавливать связи между ними? Наиболее очевидным является двухэтапный подход — сначала создаются все работы модели, затем между ними устанавливаются связи. Такой подход позволяет избежать ошибок типа KeyError: '101', возникающих при параллельном выполнении этих двух операций, когда система пытается установить связь с работой, которая еще не была создана.
Стоит ли выполнять пересчет всякий раз, когда происходит установка связи между работами при построении сетевой модели? С одной стороны, постоянный пересчет позволяет держать модель в актуальном состоянии. С другой, пересчет увеличивает время ее построения.
После чего проведено сравнение времени их выполнения на моделях из 100, 1000 и 10000 работ.
Результаты сравнения:
Как видно, чем больше работ, тем медленнее работает функция построения сетевой модели с использованием пересчета по сравнению с функцией, в которой пересчет не используется.
Сетевая модель проекта состоит из работ и связей между ними. В отсутствии дополнительной информации о сети для ее пересчета используются рекурсивные алгоритмы. Такие алгоритмы состоят в последовательном проходе по работам сети и пересчете их параметров (например, длительности, дат начала и окончания). Чем больше работ в сети, тем больше глубина рекурсии.
При работе с большими сетями, число работ в которых измеряется десятками тысяч, обычной ситуацией является превышение глубины рекурсии и, как следствие, возникновение ошибки типа RecursionError: maximum recursion depth exceeded in comparison. Ошибка приводит к остановке построения либо пересчета модели и падению системы.
До какого значения требуется увеличить глубину рекурсии? Ответ на этот вопрос зависит от структуры сетевой модели. Если структура неизвестна или достаточно сложна, рекомендую устанавливать ограничение в значение, равное количеству работ в сети. Рекурсивный алгоритм проходится либо по всем либо по части работ. Поэтому глубина рекурсии не должна превысить количество работ в сети.
Управление проектами — это модно. Но модно еще не значит эффективно. На рынке существуют программные решения по пересчету сетевых моделей, такие как Microsoft Project. Однако алгоритмы, зашитые в них остаются доступными только вендерам соответствующего программного обеспечения.
Сначала создай работы, потом устанавливай связи
При построении сетевой модели часто возникает вопрос, в каком порядке создавать работы и устанавливать связи между ними? Наиболее очевидным является двухэтапный подход — сначала создаются все работы модели, затем между ними устанавливаются связи. Такой подход позволяет избежать ошибок типа KeyError: '101', возникающих при параллельном выполнении этих двух операций, когда система пытается установить связь с работой, которая еще не была создана.
Конечно, суммарное время выполнения двух последовательных операций по созданию работ и установке связей между ними может быть оптимизировано за счет использования алгоритма, в котором эти операции выполняются параллельно. Однако даже на больших моделях с десятком тысяч работ последовательные алгоритмы работают достаточно быстро. Поэтому в условиях временных ограничений на реализацию проекта вполне можно обойтись классическим двухэтапным подходом.
Пересчитывай модель после её построения
Стоит ли выполнять пересчет всякий раз, когда происходит установка связи между работами при построении сетевой модели? С одной стороны, постоянный пересчет позволяет держать модель в актуальном состоянии. С другой, пересчет увеличивает время ее построения.
Для сравнения были реализованы две функции:
- build_model_by_method () — построение с пересчетом модели;
- build_model_by_assignment () — построение без пересчета модели.
После чего проведено сравнение времени их выполнения на моделях из 100, 1000 и 10000 работ.
# network.py
from predict import Activity
import xml.etree.ElementTree as ET
import sys
import timeit
from timeit import Timer
def build_model_by_method(filename):
sys.setrecursionlimit(10000)
f = open(filename,'r')
tree = ET.parse(f)
root = tree.getroot()
schedule = {}
next = {}
for child in root.findall('Activity'):
id = None if child.find('id').text == None else child.find('id').text
start_date = None if child.find('start_date').text == None else int(child.find('start_date').text)
finish_date = None if child.find('finish_date').text == None else int(child.find('finish_date').text)
duration = None if child.find('duration').text == None else int(child.find('duration').text)
not_early_date = None if child.find('not_early_date').text == None else int(child.find('not_early_date').text)
a = Activity(id, start_date, finish_date, duration, not_early_date)
schedule[id] = a
next_activity = '' if child.find('next_activity').text == None else child.find('next_activity').text
next[id] = next_activity
for key in schedule:
if next[key] != '':
for next_id in next[key].split(';'):
schedule[key].append_next(schedule[next_id])
sys.setrecursionlimit(1000)
def build_model_by_assignment(filename):
f = open(filename,'r')
tree = ET.parse(f)
root = tree.getroot()
schedule = {}
next = {}
for child in root.findall('Activity'):
id = None if child.find('id').text == None else child.find('id').text
start_date = None if child.find('start_date').text == None else int(child.find('start_date').text)
finish_date = None if child.find('finish_date').text == None else int(child.find('finish_date').text)
duration = None if child.find('duration').text == None else int(child.find('duration').text)
not_early_date = None if child.find('not_early_date').text == None else int(child.find('not_early_date').text)
a = Activity(id, start_date, finish_date, duration, not_early_date)
schedule[id] = a
next_activity = '' if child.find('next_activity').text == None else child.find('next_activity').text
next[id] = next_activity
for key in schedule:
if next[key] != '':
for next_id in next[key].split(';'):
schedule[key].next_activity.append(schedule[next_id])
print('Test for 100 activities:')
t1 = Timer("build_model_by_method('data/activity_100.xml')", "from __main__ import build_model_by_method")
print("build_model_by_method", t1.timeit(number = 1000))
t2 = Timer("build_model_by_assignment('data/activity_100.xml')", "from __main__ import build_model_by_assignment")
print("build_model_by_assignment", t2.timeit(number = 1000))
print('Test for 1000 activities')
t3 = Timer("build_model_by_method('data/activity_1000.xml')", "from __main__ import build_model_by_method")
print("build_model_by_method", t3.timeit(number = 1000))
t4 = Timer("build_model_by_assignment('data/activity_1000.xml')", "from __main__ import build_model_by_assignment")
print("build_model_by_assignment", t4.timeit(number = 1000))
print('Test for 10000 activities')
t5 = Timer("build_model_by_method('data/activity_10000.xml')", "from __main__ import build_model_by_method")
print("build_model_by_method", t5.timeit(number = 1000))
t6 = Timer("build_model_by_assignment('data/activity_10000.xml')", "from __main__ import build_model_by_assignment")
print("build_model_by_assignment", t6.timeit(number = 1000))
Результаты сравнения:
$ python network.py
Test for 100 activities:
build_model_by_method 2.057662970000365
build_model_by_assignment 1.6769063530000494
Test for 1000 activities
build_model_by_method 20.991429905000132
build_model_by_assignment 15.460541659000228
Test for 10000 activities
build_model_by_method 237.38402411000015
build_model_by_assignment 154.51985708500024
Как видно, чем больше работ, тем медленнее работает функция построения сетевой модели с использованием пересчета по сравнению с функцией, в которой пересчет не используется.
Контролируй глубину рекурсии
Сетевая модель проекта состоит из работ и связей между ними. В отсутствии дополнительной информации о сети для ее пересчета используются рекурсивные алгоритмы. Такие алгоритмы состоят в последовательном проходе по работам сети и пересчете их параметров (например, длительности, дат начала и окончания). Чем больше работ в сети, тем больше глубина рекурсии.
Известно, что в Python по умолчанию установлено ограничение на глубину рекурсии — не больше 1000 рекурсивных вызовов. Для получения этого ограничения предназначен метод getrecursionlimit () модуля sys.
>>> import sys
>>> sys.getrecursionlimit()
1000При работе с большими сетями, число работ в которых измеряется десятками тысяч, обычной ситуацией является превышение глубины рекурсии и, как следствие, возникновение ошибки типа RecursionError: maximum recursion depth exceeded in comparison. Ошибка приводит к остановке построения либо пересчета модели и падению системы.
Чтобы предотвратить ошибку, построить и пересчитать большую сеть, необходимо увеличить ограничение на глубину рекурсии. И в этом нам поможет метод setrecursionlimit () модуля sys.
>>> import sys
>>> sys.setrecursionlimit(10000)
>>> sys.getrecursionlimit()
10000До какого значения требуется увеличить глубину рекурсии? Ответ на этот вопрос зависит от структуры сетевой модели. Если структура неизвестна или достаточно сложна, рекомендую устанавливать ограничение в значение, равное количеству работ в сети. Рекурсивный алгоритм проходится либо по всем либо по части работ. Поэтому глубина рекурсии не должна превысить количество работ в сети.
И напоследок…
Управление проектами — это модно. Но модно еще не значит эффективно. На рынке существуют программные решения по пересчету сетевых моделей, такие как Microsoft Project. Однако алгоритмы, зашитые в них остаются доступными только вендерам соответствующего программного обеспечения.
Настоящая статья написана на основе опыта разработки открытого модуля по построению и пересчету сетевых моделей проектов. Я надеюсь, что приведенные в статье извлеченные уроки будут полезны читателю как с теоретической, так и с чисто практической точки зрения. Если настоящая статья вызовет интерес, то я поделюсь новыми знаниями, которые возникнут в дальнейшем, по мере развития модуля.
