这是两个非常相似的Levenshtein Distance 算法
。
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)
}
}
分配?字符串??最后速度降低了 4 倍?还有人需要 swift 吗?
最佳答案
Swift 代码比 Objective-C 代码慢的原因有很多。 我通过比较两个固定字符串 100 次做了一个非常简单的测试用例。
- Objective-C 代码:0.026 秒
- Swift代码: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)
并且它的优点是它可以正确地与代理对一起工作,例如 作为表情符号。
关于objective-c - 缓慢的 Swift 数组和字符串性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26990394/