algorithm - Floyd-Warshall 在 Swift 3 上的表现

Question

我对 Swift 比较陌生，所以我可能做了一些愚蠢的事情。

我已经在 J​​ava 中实现了与此非常相似的代码，并且该算法在具有 800 个顶点的图上的执行时间不到 1 秒。然而，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]))
        }
    }
}

谢谢。

Answer 1

I'm relatively new to Swift so I have probably done something dumb.

您没有做任何愚蠢的事情，但 Swift 的性能可以“有趣”。让我们试一试，看看我们发现了什么，这些都不是“确定的”，但希望它会有所帮助。所有测试均使用 Xcode 8/Swift 3 完成，800 个节点图形成一个方向性圆圈 YMMV。

我没有将您的算法与 Java 进行比较，而是使用 C 语言将您的算法编码为 Objective-C，即使用标准 C 值数组。这可以直接从 Swift 调用，并提供最佳速度的基准。

接下来，我使用 Int 的 Swift 二维数组比较了上面的 Swift 代码。性能比 (Objective-)C 版本慢 80 倍。哎哟。

最后我把二维数组换成一维数组，直接在代码里计算索引，即换成:

myMatrix[i][j]

与:

myMatrix[i*n + j]

此版本比基线慢 15 倍。更好(相对!)。这种改进将归结为 Swift 中的二维数组实际上是一维数组的一维数组。

以上测试是在正常 Debug模式下完成的，即没有优化。通过快速优化，C 基线大约快 4 倍，但 Swift 版本变化很小。因此，在对 Swift 进行优化后，一维版本比 C 基线版本慢了大约 60 倍。

您报告的 Swift 与 Java 的比率约为 300:1，比我的任何结果都要差。他们在哪里在同一台机器上运行？此外，如果您的数组实际上是 NSArray，可能 会造成差异，但我还没有运行测试来验证这个假设(NSArray是基于对象的，比 C 数组慢一些(但更灵活)。

结果(YMMV):

1. 避免使用 Swift 多维数组，将它们映射到一维数组上并自行进行索引计算。
2. 如果可以，请使用 C 数组。需要从 Swift 调用 (Objective-)C 代码，这很简单，但您当然需要了解 (Objective-)C!

HTH