Что является основным инструментом, который использует руководитель при управлении проектом? Принято считать, что основным инструментом руководителя проекта является календарный план, в основе которого лежит сетевая модель работ по проекту. Однажды мне довелось реализовать сетевую модель работ на языке Python (код и описание здесь). Ниже приведены уроки, извлеченные по результатам проделанной работы.
При построении сетевой модели часто возникает вопрос, в каком порядке создавать работы и устанавливать связи между ними? Наиболее очевидным является двухэтапный подход – сначала создаются все работы модели, затем между ними устанавливаются связи. Такой подход позволяет избежать ошибок типа KeyError: '101', возникающих при параллельном выполнении этих двух операций, когда система пытается установить связь с работой, которая еще не была создана.
Конечно, суммарное время выполнения двух последовательных операций по созданию работ и установке связей между ними может быть оптимизировано за счет использования алгоритма, в котором эти операции выполняются параллельно. Однако даже на больших моделях с десятком тысяч работ последовательные алгоритмы работают достаточно быстро. Поэтому в условиях временных ограничений на реализацию проекта вполне можно обойтись классическим двухэтапным подходом.
Стоит ли выполнять пересчет всякий раз, когда происходит установка связи между работами при построении сетевой модели? С одной стороны, постоянный пересчет позволяет держать модель в актуальном состоянии. С другой, пересчет увеличивает время ее построения.
Для сравнения были реализованы две функции:
После чего проведено сравнение времени их выполнения на моделях из 100, 1000 и 10000 работ.
Результаты сравнения:
Как видно, чем больше работ, тем медленнее работает функция построения сетевой модели с использованием пересчета по сравнению с функцией, в которой пересчет не используется.
Сетевая модель проекта состоит из работ и связей между ними. В отсутствии дополнительной информации о сети для ее пересчета используются рекурсивные алгоритмы. Такие алгоритмы состоят в последовательном проходе по работам сети и пересчете их параметров (например, длительности, дат начала и окончания). Чем больше работ в сети, тем больше глубина рекурсии.
Известно, что в Python по умолчанию установлено ограничение на глубину рекурсии – не больше 1000 рекурсивных вызовов. Для получения этого ограничения предназначен метод getrecursionlimit() модуля sys.
При работе с большими сетями, число работ в которых измеряется десятками тысяч, обычной ситуацией является превышение глубины рекурсии и, как следствие, возникновение ошибки типа RecursionError: maximum recursion depth exceeded in comparison. Ошибка приводит к остановке построения либо пересчета модели и падению системы.
Чтобы предотвратить ошибку, построить и пересчитать большую сеть, необходимо увеличить ограничение на глубину рекурсии. И в этом нам поможет метод setrecursionlimit() модуля sys.
До какого значения требуется увеличить глубину рекурсии? Ответ на этот вопрос зависит от структуры сетевой модели. Если структура неизвестна или достаточно сложна, рекомендую устанавливать ограничение в значение, равное количеству работ в сети. Рекурсивный алгоритм проходится либо по всем либо по части работ. Поэтому глубина рекурсии не должна превысить количество работ в сети.
Управление проектами – это модно. Но модно еще не значит эффективно. На рынке существуют программные решения по пересчету сетевых моделей, такие как 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 get_child(child, activity_field):
text = child.find(activity_field).text
if text is None:
return None
return int(text)
# строим модель с использованием метода пересчета
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 = child.find('id').text
start_date = get_child(child,'start_date')
finish_date = get_child(child,'finish_date')
duration = get_child(child,'duration')
not_early_date = get_child(child,'not_early_date')
a = Activity(id, start_date, finish_date, duration, not_early_date)
schedule[id] = a
next_activity = '' if child.find('next_activity').text is 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 = child.find('id').text
start_date = get_child(child,'start_date')
finish_date = get_child(child,'finish_date')
duration = get_child(child,'duration')
not_early_date = get_child(child,'not_early_date')
a = Activity(id, start_date, finish_date, duration, not_early_date)
schedule[id] = a
next_activity = '' if child.find('next_activity').text is 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 1.7820062519999738
build_model_by_assignment 1.426311435999878
Test for 1000 activities
build_model_by_method 18.998158786999966
build_model_by_assignment 14.216093206999858
Test for 10000 activities
build_model_by_method 249.93449528199994
build_model_by_assignment 148.85600239800033
Как видно, чем больше работ, тем медленнее работает функция построения сетевой модели с использованием пересчета по сравнению с функцией, в которой пересчет не используется.
Контролируй глубину рекурсии
Сетевая модель проекта состоит из работ и связей между ними. В отсутствии дополнительной информации о сети для ее пересчета используются рекурсивные алгоритмы. Такие алгоритмы состоят в последовательном проходе по работам сети и пересчете их параметров (например, длительности, дат начала и окончания). Чем больше работ в сети, тем больше глубина рекурсии.
Известно, что в 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. Однако алгоритмы, зашитые в них остаются доступными только вендерам соответствующего программного обеспечения.
Настоящая статья написана на основе опыта разработки открытого модуля по построению и пересчету сетевых моделей проектов. Я надеюсь, что приведенные в статье извлеченные уроки будут полезны читателю как с теоретической, так и с чисто практической точки зрения. Если настоящая статья вызовет интерес, то я поделюсь новыми знаниями, которые возникнут в дальнейшем, по мере развития модуля.
