缓慢的 Swift 数组和字符串性能

Question

这是两个非常相似的Levenshtein Distance algorithms。

Swift实施：https://gist.github.com/bgreenlee/52d93a1d8fa1b8c1f38b

Objective-C实施：https://gist.github.com/boratlibre/1593632

swift的比

ObjC实施慢得多我已经发送了几个小时以使其更快，但是...似乎Swift数组和Strings操作不如objC快.

在 2000 年random Strings计算Swift实现比 ObjC 慢约 100（!!） 倍。

老实说，我不知道可能出了什么问题，因为即使是 swift 的这一部分

func levenshtein(aStr: String, bStr: String) -> Int {
// create character arrays
let a = Array(aStr)
let b = Array(bStr)
...

比整个算法慢几倍Objective C

有谁知道如何加快swift计算？

提前谢谢你！

附加

在所有建议的改进之后，swift 代码如下所示。在发布配置中，它比 ObjC 慢 4 倍。

import Foundation
class Array2D {
    var cols:Int, rows:Int
    var matrix:UnsafeMutablePointer<Int>

    init(cols:Int, rows:Int) {
        self.cols = cols
        self.rows = rows
        matrix = UnsafeMutablePointer<Int>(malloc(UInt(cols * rows) * UInt(sizeof(Int))))
        for i in 0...cols*rows {
            matrix[i] = 0
        }
    }
    subscript(col:Int, row:Int) -> Int {
        get {
            return matrix[cols * row + col] as Int
        }
        set {
            matrix[cols*row+col] = newValue
        }
    }
    func colCount() -> Int {
        return self.cols
    }
    func rowCount() -> Int {
        return self.rows
    }
}
extension String {
    func levenshteinDistanceFromStringSwift(comparingString: NSString) -> Int {
        let aStr = self
        let bStr = comparingString
//        let a = Array(aStr.unicodeScalars)
//        let b = Array(bStr.unicodeScalars)
        let a:NSString = aStr
        let b:NSString = bStr
        var dist = Array2D(cols: a.length + 1, rows: b.length + 1)

        for i in 1...a.length {
            dist[i, 0] = i
        }
        for j in 1...b.length {
            dist[0, j] = j
        }
        for i in 1...a.length {
            for j in 1...b.length {
                if a.characterAtIndex(i-1) == b.characterAtIndex(j-1) {
                    dist[i, j] = dist[i-1, j-1]  // noop
                } else {
                    dist[i, j] = min(
                        dist[i-1, j] + 1,  // deletion
                        dist[i, j-1] + 1,  // insertion
                        dist[i-1, j-1] + 1  // substitution
                    )
                }
            }
        }
        return dist[a.length, b.length]
    }
    func levenshteinDistanceFromStringObjC(comparingString: String) -> Int {
        let aStr = self
        let bStr = comparingString
        //It is really strange, but I should link Objective-C coz dramatic slow swift performance
        return aStr.compareWithWord(bStr, matchGain: 0, missingCost: 1)
    }
}

马洛克？？NSString？？最后速度降低4倍？有人需要斯威夫特了吗？

Answer 1

Swift 代码

比 Objective-C 代码慢的原因有很多。我通过比较两个固定字符串 100 次来制作一个非常简单的测试用例。

• 目标-C 代码：0.026 秒
• 快速代码：3.14 秒

第一个原因是 Swift Character代表一个"扩展的字形簇"，可以包含多个 Unicode 代码点（例如"标志"）。这使得将字符串分解为字符的速度很慢。另一方面，Objective-C NSString将字符串存储为 UTF-16 码位序列。

如果替换

let a = Array(aStr)
let b = Array(bStr)

由

let a = Array(aStr.utf16)
let b = Array(bStr.utf16)

这样 Swift 代码也适用于 UTF-16 序列，然后时间就会下降到 1.88 秒。

二维数组的分配也很慢。分配速度更快单个一维数组。我在这里找到了一个简单的Array2D类：http://blog.trolieb.com/trouble-multidimensional-arrays-swift/

class Array2D {
    var cols:Int, rows:Int
    var matrix: [Int]

    init(cols:Int, rows:Int) {
        self.cols = cols
        self.rows = rows
        matrix = Array(count:cols*rows, repeatedValue:0)
    }
    subscript(col:Int, row:Int) -> Int {
        get {
            return matrix[cols * row + col]
        }
        set {
            matrix[cols*row+col] = newValue
        }
    }
    func colCount() -> Int {
        return self.cols
    }
    func rowCount() -> Int {
        return self.rows
    }
}

在代码中使用该类

func levenshtein(aStr: String, bStr: String) -> Int {
    let a = Array(aStr.utf16)
    let b = Array(bStr.utf16)
    var dist = Array2D(cols: a.count + 1, rows: b.count + 1)
    for i in 1...a.count {
        dist[i, 0] = i
    }
    for j in 1...b.count {
        dist[0, j] = j
    }
    for i in 1...a.count {
        for j in 1...b.count {
            if a[i-1] == b[j-1] {
                dist[i, j] = dist[i-1, j-1]  // noop
            } else {
                dist[i, j] = min(
                    dist[i-1, j] + 1,  // deletion
                    dist[i, j-1] + 1,  // insertion
                    dist[i-1, j-1] + 1  // substitution
                )
            }
        }
    }
    return dist[a.count, b.count]
}

测试用例中的时间减少到 0.84 秒。

我在 Swift 代码中发现的最后一个瓶颈是 min() 函数。Swift 库有一个内置的min()函数，速度更快。所以只是删除来自 Swift 代码的自定义函数将测试用例的时间减少到0.04秒，几乎和Objective-C版本一样好。

附录：使用 Unicode 标量似乎稍微快一点：

let a = Array(aStr.unicodeScalars)
let b = Array(bStr.unicodeScalars)

并且具有与代理对正确工作的优点，例如作为表情符号。