Оптимизация кода с помощью dotTrace.

13.04.2013 at 22:15

В предыдущем посте я описывал реализацию алгоритма поиска пути. Меня не устроила скорость работы этой реализации, значит придется оптимизировать.

dotTrace

Для оптимизации нужен профайлер. Я использовал dotTrace Performance Profiler. После установки в меню студии появится новая группа:

Перед запуском профайлера появится окно настроек:

Самое интересное здесь — Profiling Type. Я выбрал Line-by-line. Это самый медленный, но и самый точный вариант.
После запуска профилирования появляется окно профайлера:

После запуска программы нужно сделать те действия, которые выполняются слишком долго, а потом нажать кнопку «Get Snapshot». После этого откроется окно, в котором можно посмотреть, что же именно тормозит:

Видно, что метод поиска пути FindPath выполняется почти 2 секунды. Так же видно, что именно внутри него выполняется дольше всего.

Оптимизация

  1. Свойство EstimateFullPathLength я стал заполнять при создании объекта, так как на его динамическое вычисление уходило слишком много ресурсов.
  2. 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;
    }
    
  3. Список просмотренных точек closedSet стал словарем
    var closedSet = new Dictionary<Point, PathNode>();
    

    а проверка того, что точка уже просмотрена, стала выглядеть так:

    if (closedSet.ContainsKey(neighbourNode.Position))
    

Результат оптимизации

В результате нахождение пути ускорилось в 3 с лишним раза.