-1

配列に NSStrings があります。

i[0] = axxx
i[1] = axyz
i[2] = axxy
i[3] = abcd

検索文字列を渡して、必要なすべての文字列を見つけたいと考えています。たとえば、「ax」を渡すと 3 つの文字列が返され、「axx」を渡すと 2 つの文字列が返されます。

ここでもパフォーマンスが重要です。メソッドは次のようになります。

- (NSArray *)searchString:(NSString *)search;

通常は を使用NSPredicateしますが、今回はおそらくプレフィックス ツリーまたはバイナリ ツリーを使用する必要があります。実装への提案またはリンク。

4

3 に答える 3

3

このソリューションがあなたを満足させることを願っています。

- (NSArray *)searchString:(NSString *)search{

    NSIndexSet *indexes = [dataArray indexesOfObjectsPassingTest:
                           ^BOOL (id obj, NSUInteger i, BOOL *stop) {
                               NSString *myObj = obj;
                               return [myObj containsString:search];
                           }];
    NSArray *results = [dataArray objectsAtIndexes:indexes];

    return results;

}
于 2016-02-07T14:07:12.813 に答える
0

これはかなり単純な問題です。

Avi がコメントで示唆しているように、それには 2 つの部分があります。マッチングに使用する方法と、それらの一致を検索するために使用する方法です。

配列がソートされていて、単一の完全な一致を探している場合は、バイナリ検索を使用できます。O(log(n)) のパフォーマンスが得られると思います。（要素数の対数で時間が上がります。）

ただし、単一の完全な一致を探しているわけではありません。部分一致を探しています。それらが常に文字列の先頭と一致する必要がある場合でも、バイナリ検索を使用して最初の一致を見つけ、最初の不一致まで配列内を直線的に上下に検索できる場合があります。これにより、O(log(n)) よりもわずかにパフォーマンスが低下しますが、O(n) ほどではありません。

エントリ内の任意の場所で部分文字列を一致させる場合は、配列内のすべての要素をテストする必要があると思います。すべての要素をテストするだけで、O(n) のパフォーマンスが得られます。

一般に、O(n) のパフォーマンスは良好と見なされることに注意してください。大規模なデータセットに適しています。(O(n^2) のパフォーマンスを回避したい。それがあなたを殺します。)

問題の 2 番目の部分は、マッチング速度です。完全一致基準用にハードコーディングされた独自の文字列一致ルーチンを作成することで、おそらく述語よりもわずかに優れたパフォーマンスを得ることができますが、パフォーマンスの向上はそれほど大きくない可能性があります。私たちがこの部分を支援するためには、何が一致を構成するかについての詳細を提供する必要があります.

于 2016-02-07T12:35:52.527 に答える