2

リスト内にオブジェクトが既に存在するかどうかを確認するには、どちらがより迅速で安価です。オブジェクトを含む NSArray を使用するか、NSDictionary のキーが既に存在するかどうかを確認しますか?

また、NSArrayのcontainObjectセレクターは配列要素全体を反復しますか? また、キーが辞書内に既に存在するかどうかを確認するのはどうですか? すべてのキーを反復処理する必要がありますか。

最後に、(同じクラスの) オブジェクトの大きなリスト内にオブジェクトが既に存在するかどうかを確認する最善かつ最速の方法は何ですか?

前もって感謝します

4

3 に答える 3

5

Collection Classes のドキュメントによると、NSDictionary は HashTables に基づいています。つまり、辞書でキーを検索する場合、必要な時間は配列を反復処理するよりもはるかに短くなります。

したがって、キーの検索は o(1+衝突の数) である必要があります。配列の反復処理は o(n) です。配列をすばやく並べ替えてからバイナリ検索を実行すると、コストが大幅に削減されます。ただし、費用を考えると、NSDictionary (ハッシュ テーブル) は非常に安価に検索できます。

アップルのドキュメントから

内部的には、ディクショナリはハッシュ テーブルを使用してストレージを整理し、対応するキーが指定された値に迅速にアクセスできるようにします。ただし、辞書用に定義されたメソッドを使用すると、ハッシュ テーブル、ハッシュ関数、またはキーのハッシュ値を操作する複雑さから解放されます。メソッドは、ハッシュ形式ではなく、キーを直接受け取ります。

于 2012-06-12T15:22:08.893 に答える
1

あなたはいくつの価値について話しているのですか？速度の違いは関係ない場合があるため、コード内で最も意味のあるものを選択してください。実際、速度の問題があることがわかっていない限り、それがわかるまでは、おそらくそれが最優先事項です。

短いバージョン: 特別な必要がない限り、NSDictionary を使用してください。

于 2012-10-03T21:12:58.163 に答える
0

オブジェクトを挿入するときに配列をソートするのが最も速い方法だと思います。

NSMutableArray *myArray;

[myArray addObject:someCustomObject];
[myArray sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
    // custom compare code here
}];

これにより、オブジェクトの挿入のパフォーマンスが低下しますが、ルックアップ時間が大幅に増加します。

NSArray でバイナリ検索を実行するには:

BOOL binarySearchContains(NSArray *sortedArray, id object, NSComparator comparisonBlock)
{
    // simple recursive helper function
    __block BOOL (^_binaryRecurse)(NSArray *, id, int lo, int hi) = ^BOOL(NSArray *array, id object, int lo, int hi)
    {
        int middleIndex = ((hi - lo) / 2) + lo;

        if (hi == lo || middleIndex < 0 || middleIndex >= [array count])
            return NO;

        int compareResult = (comparisonBlock(object, [array objectAtIndex:middleIndex]));

        if (compareResult < 0)
            return _binaryRecurse(array, object, lo, middleIndex - 1);
        if (compareResult > 0)
            return _binaryRecurse(array, object, middleIndex + 1, hi);

        return YES;
    };

    return _binaryRecurse(sortedArray, object, 0, [sortedArray count]);
}

私のテストでは、bsearchは より約 15 倍高速です-containsObject:。

于 2012-06-12T14:57:06.863 に答える