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

Question

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

6

这里有两个相似的Levenshtein距离算法。

Swift实现： https://gist.github.com/bgreenlee/52d93a1d8fa1b8c1f38b Objective-C实现: https://gist.github.com/boratlibre/1593632 Swift的实现比Objective-C实现慢得多。我花了几个小时来优化它，但是...似乎Swift数组和字符串操作不像objC那样快。

在2000个随机字符串的计算中，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)

    }

}

使用malloc和NSString导致最后速度降低4倍？还有人需要Swift吗？

- Alexey

其他用户证实Swift数组确实很慢。https://dev59.com/dYHba4cB1Zd3GeqPOTgV现在Swift已经不是Beta版本了，所以这对我来说看起来相当奇怪。 - Alexey

已经过去2年了，这段代码仍然很慢，没有办法修复吗？ - TomSawyer

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martin R · Accepted Answer

有多个原因导致Swift代码比Objective-C代码慢。我通过比较两个固定字符串100次来进行了一个非常简单的测试案例。

Objective-C 代码: 0.026秒
Swift 代码: 3.14秒

第一个原因是Swift Character 表示 "扩展字符簇"，这可能包含多个Unicode码位（例如 "flags"）。这使得将字符串分解为字符变慢。另一方面，Objective-C NSString 将字符串存储为UTF-16码点序列。

如果你替换

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

by

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)

它的优点在于能够正确处理代理对，例如表情符号。