Member 11807654 Ответов: 0

Как я могу улучшить производительность этой программы?

Здравствуйте, я написал код, который работает на графике, содержащем 36692 узла. программа должна найти все кратчайшие пути в графе. график неориентирован, невзвешен и разрежен. Я не могу использовать алгоритм Флойда-warshall-за сложности это составляет o(П^3). так, я Дейкстры и это повторять |в| время, поэтому сложность алгоритма o(ве+в^2LOGV).поскольку граф является разреженным |е|&ЛТ;&ЛТ;|в|, так Дейкстры лучше, чем Флойд-warshal АЛГ. но время работы снова длинное(более 4 часов). есть ли кто-нибудь, кто может предложить мне способ сократить время работы этой программы?
Func<Edge, double> edgeCost = e => 1;
TryFunc<TVertex, IEnumerable<Edge>> tryGetPaths = null;
Parallel.For(0, d.Count, i =>
  {
      Parallel.For(i+1, d.Count, j =>
     {
         tryGetPaths = graph.ShortestPathsDijkstra(edgeCost, i.ToString());
         TVertex target = j.ToString();
         IEnumerable<Edge> path;
         if (tryGetPaths(target, out path))

             apl[i,j] = path.Count();
     });
  });


Что я уже пробовал:

Я использовал "parallel. for", чтобы увеличить скорость его запуска, но для этого требуется много времени.

Richard Deeming

Я бы начал с перемещения декларации о tryGetPaths внутри первого Parallel.For, и назначьте его на той же строке, так как он, по-видимому, не зависит ни от чего внутри внутреннего цикла:

Parallel.For(0, d.Count, i =>
{
    TryFunc<TVertex, IEnumerable<Edge>> tryGetPaths = graph.ShortestPathsDijkstra(edgeCost, i.ToString());
    Parallel.For(i+1, d.Count, j =>
    {
        TVertex target = j.ToString();
        ...
    });
});

В нынешнем виде ваш код не является потокобезопасным. Каждая итерация внутреннего цикла перезаписывает общее состояние ( tryGetPaths делегат), а затем вызывая его, не зная, изменила ли его другая итерация внешнего цикла на что-то другое.

Member 11807654

большое спасибо

0 Ответов