- PVSM.RU - https://www.pvsm.ru -
Что является основным инструментом, который использует руководитель при управлении проектом? Принято считать, что основным инструментом руководителя проекта является календарный план, в основе которого лежит сетевая модель работ по проекту. Однажды мне довелось реализовать сетевую модель работ на языке Python (код и описание здесь [1]). Ниже приведены уроки, извлеченные по результатам проделанной работы.
При построении сетевой модели часто возникает вопрос, в каком порядке создавать работы и устанавливать связи между ними? Наиболее очевидным является двухэтапный подход – сначала создаются все работы модели, затем между ними устанавливаются связи. Такой подход позволяет избежать ошибок типа KeyError: '101', возникающих при параллельном выполнении этих двух операций, когда система пытается установить связь с работой, которая еще не была создана.
Конечно, суммарное время выполнения двух последовательных операций по созданию работ и установке связей между ними может быть оптимизировано за счет использования алгоритма, в котором эти операции выполняются параллельно. Однако даже на больших моделях с десятком тысяч работ последовательные алгоритмы работают достаточно быстро. Поэтому в условиях временных ограничений на реализацию проекта вполне можно обойтись классическим двухэтапным подходом.
Стоит ли выполнять пересчет всякий раз, когда происходит установка связи между работами при построении сетевой модели? С одной стороны, постоянный пересчет позволяет держать модель в актуальном состоянии. С другой, пересчет увеличивает время ее построения.
Для сравнения были реализованы две функции:
После чего проведено сравнение времени их выполнения на моделях из 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. Однако алгоритмы, зашитые в них остаются доступными только вендерам соответствующего программного обеспечения.
Настоящая статья написана на основе опыта разработки открытого модуля по построению и пересчету сетевых моделей проектов. Я надеюсь, что приведенные в статье извлеченные уроки будут полезны читателю как с теоретической, так и с чисто практической точки зрения. Если настоящая статья вызовет интерес, то я поделюсь новыми знаниями, которые возникнут в дальнейшем, по мере развития модуля.
Автор: alobzov
Источник [2]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/188361
Ссылки в тексте:
[1] здесь: https://github.com/AleksLobzov/predict
[2] Источник: https://habrahabr.ru/post/310216/?utm_source=habrahabr&utm_medium=rss&utm_campaign=sandbox
Нажмите здесь для печати.