ios – 慢速快速字符串性能

概述我正在尝试解决Palindrome分区问题.你可以在 https://leetcode.com/problems/palindrome-partitioning/找到问题. 我想出了解决方案： func partition(_ s: String) -> [[String]] { var result: [[String]] = [] func dfs(string: Stri 我正在尝试解决palindrome分区问题.你可以在 https://leetcode.com/problems/palindrome-partitioning/找到问题.

我想出了解决方案：

func partition(_ s: String) -> [[String]] {    var result: [[String]] = []    func dfs(string: String,partiton: [String]) {        if string.characters.count == 0 {            result.append(partiton)            return        }        for length in 1...string.characters.count {            let endindex =  string.index(string.startIndex,offsetBy: length-1)            let part = string[string.startIndex...endindex]            if ispalindrome(part) {                let leftPart = string[string.index(after: endindex)..<string.endindex]                print("string: \(string) part: \(part) leftpart: \(leftPart)")                dfs(string: leftPart,partiton: partiton + [part])            }        }    }    func ispalindrome(_ s: String) -> Bool {        if String(s.characters.reversed()) == s {            return true        } else {            return false        }    }    dfs(string: s,partiton: [])    return result}

但表现不好.超出时限.

但是Python实现的相同想法可以通过：

def partition(self,s):    res = []    self.dfs(s,[],res)    return resdef dfs(self,s,path,res):    if not s:        res.append(path)        return    for i in range(1,len(s)+1):        if self.isPal(s[:i]):            self.dfs(s[i:],path+[s[:i]],res)def isPal(self,s):    return s == s[::-1]

这让我想知道如何改进swift实现以及为什么swift实现比python慢​​.

解决方法 Swift String是Characters的集合,Character表示单个扩展的Grapheme集群,可以是一个或多个
Unicode标量.这使得一些索引 *** 作如“跳过前N个字符”变慢.

但第一个改进是“短路”ispalindrome()
功能.而不是完全构建反向字符串,比较
具有相反顺序的字符序列并尽快停止
找到差异：

func ispalindrome(_ s: String) -> Bool {    return !zip(s.characters,s.characters.reversed()).contains { 
let string = String(repeating: "Hello world",count: 10)
 !=  }}

s.characters.reversed()不会反向创建新集合
顺序,它只是从后到前枚举字符.
但是,在您的方法中使用String(s.characters.reversed()),
你强制为反向字符串创建一个新集合,
这让它变慢了.

对于110个字符的字符串

let endindex = string.index(string.startIndex,offsetBy: length-1)

在我的测试中,这将计算时间从大约6秒减少到1.2秒.

接下来,避免索引计算

func partition(_ s: String) -> [[String]] {    var result: [[String]] = []    func dfs(string: String,partiton: [String]) {        if string.isEmpty {            result.append(partiton)            return        }        var IDx = string.startIndex        repeat {            string.characters.formIndex(after: &IDx)            let part = string.substring(to: IDx)            if ispalindrome(part) {                let leftPart = string.substring(from: IDx)                dfs(string: leftPart,partiton: partiton + [part])            }        } while IDx != string.endindex    }    func ispalindrome(_ s: String) -> Bool {        return !zip(s.characters,s.characters.reversed()).contains { 
func partition(_ s: String) -> [[String]] {    var result: [[String]] = []    func dfs(chars: ArraySlice<Character>,partiton: [String]) {        if chars.isEmpty {            result.append(partiton)            return        }        for length in 1...chars.count {            let part = chars.prefix(length)            if ispalindrome(part) {                let leftPart = chars.dropFirst(length)                dfs(chars: leftPart,partiton: partiton + [String(part)])            }        }    }    func ispalindrome(_ c: ArraySlice<Character>) -> Bool {        return !zip(c,c.reversed()).contains { 
func partition(_ s: String) -> [[String]] {    var result: [[String]] = []    func dfs(chars: ArraySlice<UInt16>,partiton: [String]) {        if chars.isEmpty {            result.append(partiton)            return        }        for length in 1...chars.count {            let part = chars.prefix(length)            if ispalindrome(part) {                let leftPart = chars.dropFirst(length)                part.withUnsafeBufferPointer {                    dfs(chars: leftPart,partiton: partiton + [String(utf16CodeUnits: .baseAddress!,count: length)])                }            }        }    }    func ispalindrome(_ c: ArraySlice<UInt16>) -> Bool {        return !zip(c,c.reversed()).contains {  !=  }    }    dfs(chars: ArraySlice(s.utf16),partiton: [])    return result}
 !=  }    }    dfs(chars: ArraySlice(s.characters),partiton: [])    return result}
 !=  }    }    dfs(string: s,partiton: [])    return result}

并迭代字符索引本身：

计算时间现在是0.7秒.

下一步是完全避免字符串索引,并使用
一个字符数组,因为数组索引很快.更好的是,
使用快速创建和引用原始数组的数组切片
数组元素：

计算时间现在是0.08秒.

如果您的字符串仅包含“基本多语言平面”中的字符(即< = U FFFF),那么您可以使用UTF-16代码点：

110字符测试字符串的计算时间现在为0.04秒.

因此,在使用Swift字符串时可能会提高性能的一些技巧是

>按顺序迭代字符/索引.避免“跳跃”
到了第n个位置.
>如果您需要“随机”访问所有字符,请转换字符串
先到一个数组.
>使用字符串的UTF-16视图比工作更快
用角色视图.

当然这取决于实际的用例.在这个应用程序,我们能够将计算时间从6秒减少到0.04秒,这是150的因素.

总结

以上是内存溢出为你收集整理的ios – 慢速快速字符串性能全部内容，希望文章能够帮你解决ios – 慢速快速字符串性能所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。