Выступление Флойда-Уоршалла на Swift 3

Я относительно новичок в Swift, поэтому я, вероятно, сделал что-то глупое.

Я реализовал код, очень похожий на этот, на Java, и алгоритм выполняется менее чем за 1 секунду на графе с 800 вершинами. Однако версия Swift 3 занимает более 5 минут на том же графике!
Что я сделал не так?

var myMatrix = myGraph.getAdjMatr()   //  Returns adjacency matrix as 2d array.
let n = myGraph.vertexCount!

for i in 0..<n
{
    for j in 0..<n
    {
        if (myMatrix[i][j] == 0)
        {
            myMatrix[i][j] = Int.max/2
        }
    }
}

for i in 0..<n
{
    myMatrix[i][i] = 0;
}

for i in 0..<n
{
    for j in 0..<n
    {
        for k in 0..<n
        {
            myMatrix[j][k] = min(myMatrix[j][k], (myMatrix[i][k] + myMatrix[j][i]))
        }
    }
}

Спасибо.


swift3 algorithm graph-theory floyd-warshall
person GreenApples53    schedule 30.06.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я относительно новичок в Swift, поэтому я, вероятно, сделал что-то глупое.

Вы не сделали ничего глупого, но производительность Swift может быть «интересной». Давайте поиграем и посмотрим, что мы найдем, ничто из этого не является «окончательным», но, надеюсь, это поможет. Все тесты выполнены с помощью Xcode 8/Swift 3 и графа из 800 узлов, образующего единую направленную окружность, YMMV.

Вместо сравнения с Java я закодировал ваш алгоритм в C, завернутый как Objective-C, то есть с использованием стандартных массивов значений C. Это может быть вызвано непосредственно из Swift и обеспечивает базовый уровень для наилучшей скорости.

Затем я сравнил ваш код Swift выше, используя двумерный массив Swift Int. Производительность была примерно в 80 раз медленнее, чем у версии (Objective-)C. Ой.

Наконец я заменил двумерный массив на одномерный и сделал расчет индекса прямо в коде, т.е. заменив:

myMatrix[i][j]

с участием:

myMatrix[i*n + j]

Эта версия примерно в 15 раз медленнее, чем базовая версия. Лучше (относительно!). Это улучшение будет сводиться к двумерному массиву в Swift, фактически являющемуся одномерным массивом одномерных массивов.

Вышеуказанные тесты проводились в обычном режиме отладки, т.е. без оптимизации. С быстрой оптимизацией базовый уровень C был примерно в 4 раза быстрее, но версии Swift изменились незначительно. Таким образом, оптимизация в одномерной версии Swift была примерно в 60 раз медленнее, чем в базовой версии C.

Ваше заявленное соотношение Swift и Java составляет около 300: 1, что намного хуже, чем любой из моих результатов. Где они работают на одной машине? Кроме того, если ваш массив на самом деле представляет собой NSArray, это может объяснить разницу, но я не проводил тестов для проверки этой гипотезы (NSArray основан на объектах и ​​несколько медленнее (но более гибкий), чем массив С).

Результаты (YMMV):

  1. Избегайте многомерных массивов Swift, сопоставляйте их с одномерными массивами, выполняя вычисления индекса самостоятельно.
  2. Используйте массивы C, если можете. Требуется вызов кода (Objective-)C из Swift, что несложно, но вам, конечно, нужно знать (Objective-)C!

ХТН

person CRD    schedule 01.07.2017
comment
Да, они были сделаны на той же машине, и это было с Array, а не с NSArray — я не уверен, почему моя версия Swift была такой медленной. Я хотел написать чистую графическую программу Swift, но я понимаю, что язык все еще быстро развивается, поэтому сейчас я буду делать то, что вы рекомендовали, и использовать Objective-C. Спасибо за подробный ответ! - person GreenApples53; 19.07.2017