Swiftで非常に遅い構文解析のテキスト

Question

私は46k文字のテキストドキュメントを解析しようとしています。ここで私は何をすべきかです：

申し訳

for i in 0..<html.length() - SEARCH_START.length() { 
     if html.substring(i, end: i+SEARCH_START.length()) == SEARCH_START { 
       start = i + SEARCH_START.length(); 
       break; 
     } 
     if i % 1000 == 0 { 
      NSLog("i = \(i)") 
     } 
    } 

extension String { 

    public func length() -> Int { 
     return self.characters.count 
    } 
    public func substring(_ start : Int, end : Int) -> String { 
     if self.characters.count <= 0 { 
      return "" 
     } 
     let realEnd = end>0 ? end : 0 
     return self.substring(with: self.index(self.startIndex, offsetBy: start)..<self.index(self.startIndex, offsetBy: realEnd)) 
    } 
} 

、アンドロイドからの書き換え以下を行うにはStringクラスを拡張する必要がありました。 したがって、次の千のためにログが6.5秒ごとにトリガーされています。ほぼ5分が終了します。プロセスはミリ秒かかるでしょう。どうしたんだ？それをスピードアップする方法はありますか？

Answer 1

Intインデックスの拡張が問題です。位置nに部分文字列を取得するには、すべての文字を処理する必要があります0..n。したがって、アルゴリズムはO(n)（線形）の複雑さではなく、O(n^2)（2次）の複雑さを持ちます。

この拡張子は使用しないでください。部分文字列を検索するに

、ネイティブメソッド

if let range = html.range(of: SEARCH_START) { 
    let integerIndex = html.distance(from: html.startIndex, to: range.upperBound) 
    print(integerIndex) 
} 

があり、あなたが本当に整数で作業する場合は、最初の文字の配列にあなたの文字列を変換する必要があります

let chars = Array(html.characters) 

サブストリングの代わりにサブアレイを処理します。

編集：

がより良いあなたの拡張機能で何が起こるかを理解するには、次のStringが配列であり、これは一定の（速い）の動作となり、ランダムなインデックスをサポートするJavaでは、

self.substring(with: self.index(self.startIndex, offsetBy: start)..<self.index(self.startIndex, offsetBy: realEnd)) 

。それは、インデックスstartで文字を見つけるまで、最初の文字から

1. self.index(self.startIndex, offsetBy: start)繰り返し処理：しかし、スウィフトにこれは3つの段階から構成されています。
2. self.index(self.startIndex, offsetBy: realEnd))は、インデックスの文字を見つけるまで、最初の文字から反復します。
3. ストリング（速い）要するに

を取得し、開始位置nのすべての部分文字列のために、アルゴリズムは2n文字以上を反復しなければなりません。インデックス20000の部分文字列を取得するには、40000操作が必要です。