反復中に NSMutableArray から削除する最良の方法は?

https://stackoverflow.com/questions/111866

02-07-2019
|

質問

Cocoa で、NSMutableArray をループして、特定の基準を満たす複数のオブジェクトを削除したい場合、オブジェクトを削除するたびにループを再開せずにこれを行う最善の方法は何ですか?

ありがとう、

編集：明確にするために、私は最善の方法を探していました。インデックスを手動で更新するよりもエレガントな方法です。たとえば、C++ では次のことができます。

iterator it = someList.begin();

while (it != someList.end())
{
    if (shouldRemove(it))   
        it = someList.erase(it);
}

解決

わかりやすくするために、削除する項目を収集する最初のループを作成したいと思います。それからそれらを削除します。以下は、Objective-C 2.0 構文を使用したサンプルです。

NSMutableArray *discardedItems = [NSMutableArray array];

for (SomeObjectClass *item in originalArrayOfItems) {
    if ([item shouldBeDiscarded])
        [discardedItems addObject:item];
}

[originalArrayOfItems removeObjectsInArray:discardedItems];

そうすれば、インデックスが正しく更新されているかどうか、またはその他の簿記の詳細については疑問の余地がありません。

編集して以下を追加しました:

他の回答では、逆定式化を高速化する必要があることが指摘されています。つまり配列を反復処理し、破棄するオブジェクトではなく、保持するオブジェクトの新しい配列を作成する場合。それは真実かもしれません (ただし、新しい配列を割り当て、古い配列を破棄するためのメモリと処理コストはどうなるのでしょうか?) しかし、たとえ高速であっても、単純な実装ほど大したことではないかもしれません。「通常の」配列のように動作しません。彼らはよく話しますが、違う道を歩きます。ここで優れた分析を参照してください。

逆定式化の方が速いかもしれませんが、上記の定式化は常に私のニーズにとって十分に高速であるため、逆定式化が速いかどうかを気にする必要はありませんでした。

私にとっての教訓は、自分にとって最も明確な処方を使用することです。必要な場合にのみ最適化してください。私は個人的に上記の公式が最も明確であると感じているため、これを使用しています。しかし、逆定式化の方が明確であれば、それを使ってください。

他のヒント

もう一つのバリエーション。したがって、読みやすさと優れたパフォーマンスが得られます。

NSMutableIndexSet *discardedItems = [NSMutableIndexSet indexSet];
SomeObjectClass *item;
NSUInteger index = 0;

for (item in originalArrayOfItems) {
    if ([item shouldBeDiscarded])
        [discardedItems addIndex:index];
    index++;
}

[originalArrayOfItems removeObjectsAtIndexes:discardedItems];

これは非常に単純な問題です。逆方向に反復するだけです。

for (NSInteger i = array.count - 1; i >= 0; i--) {
   ElementType* element = array[i];
   if ([element shouldBeRemoved]) {
       [array removeObjectAtIndex:i];
   }
}

これは非常に一般的なパターンです。

他の回答の中には、次のようなメソッドがあるため、非常に大きな配列ではパフォーマンスが低下するものもあります。 removeObject: そして removeObjectsInArray: 受信機の線形検索を実行する必要がありますが、オブジェクトがどこにあるかはすでにわかっているため、これは無駄です。また、どのような通話でも、 removeObjectAtIndex: インデックスから配列の末尾まで値を一度に 1 スロットずつコピーする必要があります。

より効率的なのは次のとおりです。

NSMutableArray *array = ...
NSMutableArray *itemsToKeep = [NSMutableArray arrayWithCapacity:[array count]];
for (id object in array) {
    if (! shouldRemove(object)) {
        [itemsToKeep addObject:object];
    }
}
[array setArray:itemsToKeep];

の容量を設定しているため、 itemsToKeep, サイズ変更中に値をコピーするのに時間を無駄にすることはありません。配列をその場で変更しないため、高速列挙を自由に使用できます。使用する setArray: の内容を置き換える array と itemsToKeep 効率的になります。コードによっては、最後の行を次のように置き換えることもできます。

[array release];
array = [itemsToKeep retain];

したがって、値をコピーする必要さえなく、ポインタを交換するだけです。

NSpredicate を使用すると、可変配列から項目を削除できます。これには for ループは必要ありません。

たとえば、名前の NSMutableArray がある場合、次のような述語を作成できます。

NSPredicate *caseInsensitiveBNames = 
[NSPredicate predicateWithFormat:@"SELF beginswith[c] 'b'"];

次の行では、b で始まる名前のみを含む配列が作成されます。

[namesArray filterUsingPredicate:caseInsensitiveBNames];

必要な述語の作成に問題がある場合は、これを使用してくださいアップル開発者リンク.

4 つの異なる方法を使用してパフォーマンステストを実行しました。各テストでは、100,000 要素の配列内のすべての要素を反復処理し、5 番目ごとに項目を削除しました。最適化の有無にかかわらず、結果はあまり変わりませんでした。これらは iPad 4 で実行されました。

(1) removeObjectAtIndex: -- 271ミリ秒

(2) removeObjectsAtIndexes: -- 1010ミリ秒 (インデックスセットの構築には約 700 ミリ秒かかるため。それ以外の場合、これは基本的に、removeObjectAtIndex を呼び出すことと同じです。項目ごとに）

(3) removeObjects: -- 326ミリ秒

(4) テストに合格したオブジェクトを含む新しい配列を作成します -- 17ミリ秒

したがって、新しい配列を作成する方がはるかに高速です。他のメソッドは、removeObjectsAtIndexes を使用する点を除いて、すべて同等です。削除する項目が増えると、インデックスセットの構築に時間がかかるため、状況はさらに悪化します。

インデックスをカウントダウンするループを使用します。

for (NSInteger i = array.count - 1; i >= 0; --i) {

または、保持したいオブジェクトのコピーを作成します。

特に、 for (id object in array) ループまたは NSEnumerator.

iOS 4 以降または OS X 10.6 以降の場合、Apple は次のように追加しました passingTest の一連の API NSMutableArray, 、のように – indexesOfObjectsPassingTest:. 。このような API を使用したソリューションは次のようになります。

NSIndexSet *indexesToBeRemoved = [someList indexesOfObjectsPassingTest:
    ^BOOL(id obj, NSUInteger idx, BOOL *stop) {
    return [self shouldRemove:obj];
}];
[someList removeObjectsAtIndexes:indexesToBeRemoved];

現在では、逆ブロックベースの列挙を使用できるようになりました。簡単なコード例:

NSMutableArray *array = [@[@{@"name": @"a", @"shouldDelete": @(YES)},
                           @{@"name": @"b", @"shouldDelete": @(NO)},
                           @{@"name": @"c", @"shouldDelete": @(YES)},
                           @{@"name": @"d", @"shouldDelete": @(NO)}] mutableCopy];

[array enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    if([obj[@"shouldDelete"] boolValue])
        [array removeObjectAtIndex:idx];
}];

結果：

(
    {
        name = b;
        shouldDelete = 0;
    },
    {
        name = d;
        shouldDelete = 0;
    }
)

たった 1 行のコードを使用した別のオプション:

[array filterUsingPredicate:[NSPredicate predicateWithFormat:@"shouldDelete == NO"]];

より宣言的な方法では、削除する項目に一致する基準に応じて、次のものが使用できます。

[theArray filterUsingPredicate:aPredicate]

@Nathan は非常に効率的であるはずです

これが簡単できれいな方法です。私は高速列挙呼び出しの中で配列を複製するのが好きです。

for (LineItem *item in [NSArray arrayWithArray:self.lineItems]) 
{
    if ([item.toBeRemoved boolValue] == YES) 
    {
        [self.lineItems removeObject:item];
    }
}

この方法では、両方とも同じオブジェクトを保持している、削除対象の配列のコピーを列挙します。NSArray はオブジェクトポインターのみを保持するため、メモリ/パフォーマンスの観点からはまったく問題ありません。

削除するオブジェクトを 2 番目の配列に追加し、ループの後に -removeObjectsInArray: を使用します。

これで済むはずです:

    NSMutableArray* myArray = ....;

    int i;
    for(i=0; i<[myArray count]; i++) {
        id element = [myArray objectAtIndex:i];
        if(element == ...) {
            [myArray removeObjectAtIndex:i];
            i--;
        }
    }

お役に立てれば...

削除するオブジェクトを別の NSMutableArray に追加してみてはいかがでしょうか。反復が終了したら、収集したオブジェクトを削除できます。

削除したい要素を「n」番目の要素、「n-1」番目の要素などと入れ替えてみてはいかがでしょうか？

完了したら、配列のサイズを「前のサイズ - スワップ数」に変更します。

配列内のすべてのオブジェクトが一意である場合、またはオブジェクトが見つかったときにそのオブジェクトをすべて削除したい場合は、配列のコピーを高速に列挙し、[NSMutableArray deleteObject:] を使用して元のオブジェクトからオブジェクトを削除できます。

NSMutableArray *myArray;
NSArray *myArrayCopy = [NSArray arrayWithArray:myArray];

for (NSObject *anObject in myArrayCopy) {
    if (shouldRemove(anObject)) {
        [myArray removeObject:anObject];
    }
}

上記のbenzadoの回答は、preformaceのために行うべきことです。私のアプリケーションの 1 つでは、removeObjectsInArray の実行時間は 1 分かかりましたが、新しい配列に追加するだけで 0.023 秒かかりました。

次のように、ブロックを使用してフィルタリングできるカテゴリを定義します。

@implementation NSMutableArray (Filtering)

- (void)filterUsingTest:(BOOL (^)(id obj, NSUInteger idx))predicate {
    NSMutableIndexSet *indexesFailingTest = [[NSMutableIndexSet alloc] init];

    NSUInteger index = 0;
    for (id object in self) {
        if (!predicate(object, index)) {
            [indexesFailingTest addIndex:index];
        }
        ++index;
    }
    [self removeObjectsAtIndexes:indexesFailingTest];

    [indexesFailingTest release];
}

@end

これは次のように使用できます。

[myMutableArray filterUsingTest:^BOOL(id obj, NSUInteger idx) {
    return [self doIWantToKeepThisObject:obj atIndex:idx];
}];

より優れた実装は、NSMutableArray で以下の category メソッドを使用することです。

@implementation NSMutableArray(BMCommons)

- (void)removeObjectsWithPredicate:(BOOL (^)(id obj))predicate {
    if (predicate != nil) {
        NSMutableArray *newArray = [[NSMutableArray alloc] initWithCapacity:self.count];
        for (id obj in self) {
            BOOL shouldRemove = predicate(obj);
            if (!shouldRemove) {
                [newArray addObject:obj];
            }
        }
        [self setArray:newArray];
    }
}

@end

述語ブロックを実装すると、配列内の各オブジェクトに対して処理を実行できます。述語が true を返す場合、オブジェクトは削除されます。

過去の日付をすべて削除する日付配列の例:

NSMutableArray *dates = ...;
[dates removeObjectsWithPredicate:^BOOL(id obj) {
    NSDate *date = (NSDate *)obj;
    return [date timeIntervalSinceNow] < 0;
}];

逆方向に反復するのは長年私のお気に入りでしたが、長い間、「最も深い」(最もカウントが高い) オブジェクトが最初に削除されるケースに遭遇したことはありませんでした。ポインターが次のインデックスに移動する直前に何もなくなり、クラッシュします。

Benzado の方法は私が現在行っている方法に最も近いですが、削除するたびにスタックの再シャッフルがあるとは思いもしませんでした。

Xcode 6 ではこれは機能します

NSMutableArray *itemsToKeep = [NSMutableArray arrayWithCapacity:[array count]];

    for (id object in array)
    {
        if ( [object isNotEqualTo:@"whatever"]) {
           [itemsToKeep addObject:object ];
        }
    }
    array = nil;
    array = [[NSMutableArray alloc]initWithArray:itemsToKeep];

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow