Floyd-Warshall 在 Swift 3 上的表现

Question

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

我在 Java 中实现了与此非常相似的代码，并且该算法在具有 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的表现可以"interesting"。让我们试一试，看看我们发现了什么，其中 none 是 "definitive"，但希望它会有所帮助。所有测试均使用 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 中的二维数组实际上是一维数组的一维数组。

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

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

结果（YMMV）：

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

HTH

Floyd-Warshall 在 Swift 3 上的表现

Floyd-Warshall performance on Swift 3

algorithm

swift3

graph-theory

floyd-warshall