Cocoa/Objective-Cの検索を最適化する

Question

私は辞書を含む大規模なplistファイルを検索しています。数十万件あり、それぞれに2つのキー/文字列のペアがあります。私の検索アルゴリズムは辞書を通過し、辞書内のいずれかの文字列に一致するテキストが見つかると、辞書の内容が挿入されます。ここではそれがどのように動作するかです：

NSDictionary *eachEntry; 
NSArray *rawGlossaryArray = [[NSArray alloc] initWithContentsOfFile:thePath]; // this contains the contents of the plist 

for (eachEntry in rawGlossaryArray) 
    { 
     GlossaryEntry *anEntry = [[GlossaryEntry alloc] initWithDictionary:eachEntry]; 


     NSRange titleResultsRange = [anEntry.title rangeOfString:filterString options:NSCaseInsensitiveSearch]; 
     NSRange defResultsRange = [anEntry.definition rangeOfString:filterString options:NSCaseInsensitiveSearch]; 

     if (titleResultsRange.length > 0 || defResultsRange.length > 0) { 
      // store that item in the glossary dictionary with the name as the key 
      [glossaryDictionary setObject:anEntry forKey:anEntry.title]; 

     } 
     [anEntry release]; 
    } 

検索が実行されるたびに、私のiPhoneアプリで約3-4秒の遅延がある（少なくとも、デバイス上の、すべてのものは、シミュレータでかなり迅速に実行されます）。どのように私はこの検索を最適化するかもしれないかアドバイスできますか？

Answer 1

いくつかの提案：

1. あなたはallocing、そのループにリリースをたくさんやっています。ループの前に単一のGlossaryEntryを作成して、ループの内容をリロードするだけですか？これはalloc/releaseの束を避けるでしょう。

2. ファイルを毎回読み込むのではなく、一度読み込みを遅延させてメモリにキャッシュしておくことができますか？一般的にこれはiPhone上では良い考えではありませんが、問題が発生した場合にキャッシュを解放するコードを "didReceiveMemoryWarning"ハンドラに追加することができます。

Answer 2

アプリケーションを実行して、ボトルネックが本当に何であるかを確認してください。盲人のパフォーマンスの最適化は本当に難しいですし、我々はそれらを明確にするツールを持っており、ツールも良いです！

これは最適化できない可能性もあります。私はそれが実際にあなたのアプリにUIをぶら下げているか、ちょうど長い時間を取っているかどうかはわかりません。 UIをブロックしている場合は、この作業を行うためにメインスレッドから抜け出す必要があります。アプリの応答性を維持するための重要な作業と同じです。

Answer 3

データセットを見ないと確信が持てませんが、プロファイルすると膨大な時間を-rangeOfString：options：に費やしています。この場合、データの格納に使用するデータ構造を根本的に変更することなく、パフォーマンスを向上させることはできません。

オブジェクトを指す文字列と部分文字列を使用してソートトライを作成したい場合があります。それは設定するのがはるかに複雑なことです、そして、それへの挿入はより高価ですが、検索は非常に速くなります。とにかく高価なインサートが大した問題ではないはずです。

Answer 4

は、次のことを試してください、そしてあなたが任意の改善を得るかどうかを確認：

1）値NSLiteralSearchを渡し、

- (NSRange)rangeOfString:(NSString *)aString options:(NSStringCompareOptions)mask 

とマスクとして使用します。 Appleのドキュメント（CocoaのString Programming Guide）に記載されているように検索が大幅にスピードアップする可能性があります。

NSLiteralSearchバイトごとの比較を実行します。等価とみなされる異なる文字列（合成文字列など）は、一致しないとみなされます。このオプションを使用すると、操作が大幅に高速化されます。詳しくは

BOOL match = [myPredicate evaluateWithObject:myString]; 

：あなたは、単に文字列が与えられたパターンが含まれているかどうかを確認したい場合は

は、あなたが述語を使用することができます。ドキュメントココアのための（文字列プログラミングガイド）から

2）述語については、「述語プログラミングガイド」を参照してください。

Answer 5

これはあらかじめデータベースに格納しておき、アプリケーションに組み込むだけのものです。

Answer 6

ボトルネックが実際にどこにあるかを見つけるために、計測器でプロファイルする必要があります。私が推測しなければならないことは、ボトルネックは[[NSArray alloc] initWithContentsOfFile：thePath]と言うでしょう。

plistを使用する代わりに、sqliteデータベース（SQLで検索する）にデータを保存すると、おそらく最高のパフォーマンスが得られるはずです。

Answer 7

現在のデータ構造では、おそらく最高のパフォーマンスが得られるでしょう。パフォーマンスを向上させるには、データへのアクセス方法を変更する必要があります。順不同

提案、：あなたがそれらをフィルタリングしている間

1. は、ループ内であなたのGlossaryEntryオブジェクトを作成しないでください。プロパティリストにデータを格納するのではなく、GlossaryEntryオブジェクトの配列をアーカイブするだけです。 NSCodingのドキュメントを参照してください。

2. キーストロークごとに数万の文字列を検索するのではなく、共通の部分文字列（多分2文字または3文字）のインデックスを生成し、その共通部分文字列から次のように使用する一連の結果にマップするNSDictionaryを作成します。インデックス。実行時ではなく、ビルド時に索引を作成できます。データセットを複数の小さな部分に分割することができれば、一致する文字列の線形検索はかなり高速になります。

3. SQLiteデータベースにデータを格納し、SQLを使用してクエリを実行します。おそらくこの問題だけでは不十分ですが、将来的にはより洗練された検索が可能です。

4. 単純なインデックスの作成が十分に機能しない場合は、検索ツリースタイルのデータ構造を作成する必要があります。