Оптимизация кода с помощью dotTrace.
В предыдущем посте я описывал реализацию алгоритма поиска пути. Меня не устроила скорость работы этой реализации, значит придется оптимизировать.
dotTrace
Для оптимизации нужен профайлер. Я использовал dotTrace Performance Profiler. После установки в меню студии появится новая группа:
Перед запуском профайлера появится окно настроек:
Самое интересное здесь — Profiling Type. Я выбрал Line-by-line. Это самый медленный, но и самый точный вариант.
После запуска профилирования появляется окно профайлера:
После запуска программы нужно сделать те действия, которые выполняются слишком долго, а потом нажать кнопку «Get Snapshot». После этого откроется окно, в котором можно посмотреть, что же именно тормозит:
Видно, что метод поиска пути FindPath выполняется почти 2 секунды. Так же видно, что именно внутри него выполняется дольше всего.
Оптимизация
- Свойство EstimateFullPathLength я стал заполнять при создании объекта, так как на его динамическое вычисление уходило слишком много ресурсов.
- openSet стал списком
var openSet = new List<PathNode>();
Проверку
while (openSet.Count > 0)
переделал в
while (openSet.Any())
Получение проверяемой точки
var currentNode = openSet.OrderBy(node => node.EstimateFullPathLength).First();
Переделал так:
openSet.Sort(); var currentNode = openSet.First();
Для это реализовал в классе PathNode интерфейс IComparable<PathNode>
public int CompareTo(PathNode obj) { if (this.EstimateFullPathLength == obj.EstimateFullPathLength) return 0; return this.EstimateFullPathLength > obj.EstimateFullPathLength ? 1 : -1; }
- Список просмотренных точек closedSet стал словарем
var closedSet = new Dictionary<Point, PathNode>();
а проверка того, что точка уже просмотрена, стала выглядеть так:
if (closedSet.ContainsKey(neighbourNode.Position))
Результат оптимизации
В результате нахождение пути ускорилось в 3 с лишним раза.