Der beste Weg, um während der Iteration aus NSMutableArray zu entfernen?

194

Wenn ich in Cocoa ein NSMutableArray durchlaufen und mehrere Objekte entfernen möchte, die bestimmten Kriterien entsprechen, wie kann ich dies am besten tun, ohne die Schleife jedes Mal neu zu starten, wenn ich ein Objekt entferne?

Vielen Dank,

Bearbeiten: Nur zur Verdeutlichung - Ich habe nach dem besten Weg gesucht, z. B. nach etwas Eleganterem, als den Index, an dem ich mich befinde, manuell zu aktualisieren. Zum Beispiel in C ++ kann ich tun;

iterator it = someList.begin();

while (it != someList.end())
{
    if (shouldRemove(it))   
        it = someList.erase(it);
}
Andrew Grant
quelle
9
Schleife von hinten nach vorne.
Hot Licks
Niemand antwortet auf das "WARUM"
onmyway133
1
@HotLicks Einer meiner absoluten Favoriten und die am meisten unterschätzte Lösung in der Programmierung im Allgemeinen: D
Julian F. Weinert

Antworten:

388

Aus Gründen der Klarheit möchte ich eine erste Schleife erstellen, in der ich die zu löschenden Elemente sammle. Dann lösche ich sie. Hier ist ein Beispiel mit der Objective-C 2.0-Syntax:

NSMutableArray *discardedItems = [NSMutableArray array];

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

[originalArrayOfItems removeObjectsInArray:discardedItems];

Dann gibt es keine Frage, ob die Indizes korrekt aktualisiert werden oder andere kleine Buchhaltungsdetails.

Bearbeitet, um hinzuzufügen:

In anderen Antworten wurde festgestellt, dass die inverse Formulierung schneller sein sollte. dh wenn Sie das Array durchlaufen und ein neues Array von Objekten erstellen, die beibehalten werden sollen, anstatt Objekte, die verworfen werden sollen. Das mag wahr sein (obwohl was ist mit den Speicher- und Verarbeitungskosten für das Zuweisen eines neuen Arrays und das Verwerfen des alten Arrays?), Aber selbst wenn es schneller ist, ist es möglicherweise nicht so wichtig wie für eine naive Implementierung, weil NSArrays Verhalten Sie sich nicht wie "normale" Arrays. Sie reden, aber sie gehen einen anderen Weg. Eine gute Analyse finden Sie hier:

Die inverse Formulierung mag schneller sein, aber ich musste mich nie darum kümmern, ob dies der Fall ist, da die obige Formulierung für meine Bedürfnisse immer schnell genug war.

Für mich ist die Botschaft zum Mitnehmen, die für Sie klarste Formulierung zu verwenden. Nur bei Bedarf optimieren. Ich persönlich finde die obige Formulierung am klarsten, weshalb ich sie verwende. Aber wenn Ihnen die umgekehrte Formulierung klarer ist, machen Sie es.

Christopher Ashworth
quelle
47
Beachten Sie, dass dies zu Fehlern führen kann, wenn sich Objekte mehr als einmal in einem Array befinden. Alternativ können Sie ein NSMutableIndexSet und - (void) removeObjectsAtIndexes verwenden.
Georg Schölly
1
Es ist tatsächlich schneller, das Gegenteil zu tun. Der Leistungsunterschied ist ziemlich groß, aber wenn Ihr Array nicht so groß ist, werden die Zeiten so oder so trivial sein.
user1032657
Ich habe reverse ... made array als nil verwendet und dann nur das hinzugefügt, was ich wollte, und Daten neu geladen
Hauptdaten
Für die Inverse muss zusätzlicher Speicher zugewiesen werden. Es ist kein In-Place-Algorithmus und in einigen Fällen keine gute Idee. Wenn Sie direkt entfernen, verschieben Sie einfach das Array (was sehr effizient ist, da es nicht einzeln verschoben wird, sondern einen großen Teil verschieben kann). Wenn Sie jedoch ein neues Array erstellen, benötigen Sie alle Zuordnungen und Zuweisungen. Wenn Sie also nur einige Elemente löschen, ist die Umkehrung viel langsamer. Es ist ein typischer scheinbar richtiger Algorithmus.
Jack
82

Noch eine Variation. So erhalten Sie Lesbarkeit und gute Leistung:

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

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

[originalArrayOfItems removeObjectsAtIndexes:discardedItems];
Corey Floyd
quelle
Das ist fantastisch. Ich habe versucht, mehrere Elemente aus dem Array zu entfernen, und dies hat perfekt funktioniert. Andere Methoden verursachten Probleme :) Danke Mann
AbhinavVinay
Corey, diese Antwort (unten) sagte, dass dies removeObjectsAtIndexesdie schlechteste Methode zum Entfernen der Objekte ist. Sind Sie damit einverstanden? Ich frage dies, weil Ihre Antwort jetzt zu alt ist. Trotzdem ist es gut, das Beste zu wählen?
Hemang
Ich mag diese Lösung sehr in Bezug auf die Lesbarkeit. Wie ist es in Bezug auf die Leistung im Vergleich zu @HotLicks Antwort?
Victor Maia Aldecôa
Diese Methode sollte auf jeden Fall empfohlen werden, wenn Objekte aus dem Array in Obj-C gelöscht werden.
Boreas
enumerateObjectsUsingBlock:Sie erhalten das Indexinkrement kostenlos.
Pkamb
42

Dies ist ein sehr einfaches Problem. Sie iterieren einfach rückwärts:

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

Dies ist ein sehr verbreitetes Muster.

Hot Licks
quelle
hätte Jens Antwort verpasst, weil er den Code nicht ausgeschrieben hat: P .. thnx m8
FlowUI. SimpleUITesting.com
3
Dies ist die beste Methode. Es ist wichtig, sich daran zu erinnern, dass die Iterationsvariable eine vorzeichenbehaftete Variable sein sollte, obwohl Array-Indizes in Objective-C als vorzeichenlos deklariert sind (ich kann mir vorstellen, wie Apple dies jetzt bedauert).
Mojuba
39

Einige der anderen Antworten hätten eine schlechte Leistung bei sehr großen Arrays, da Methoden eine lineare Suche des Empfängers mögen removeObject:und removeObjectsInArray:beinhalten, was eine Verschwendung ist, da Sie bereits wissen, wo sich das Objekt befindet. Außerdem muss jeder Aufruf von removeObjectAtIndex:Werte um jeweils einen Steckplatz vom Index bis zum Ende des Arrays kopieren.

Effizienter wäre Folgendes:

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

Da wir die Kapazität von festlegen itemsToKeep, verschwenden wir keine Zeit damit, Werte während einer Größenänderung zu kopieren. Wir ändern das Array nicht an Ort und Stelle, daher können wir Fast Enumeration verwenden. Mit setArray:auf den Inhalt ersetzt arraymit itemsToKeepwird effizient sein. Abhängig von Ihrem Code können Sie sogar die letzte Zeile durch Folgendes ersetzen:

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

Sie müssen also nicht einmal Werte kopieren, sondern nur einen Zeiger austauschen.

Benzado
quelle
Dieses Algo erweist sich in Bezug auf die zeitliche Komplexität als gut. Ich versuche es in Bezug auf die Komplexität des Raums zu verstehen. Ich habe die gleiche Implementierung, bei der ich die Kapazität für 'itemsToKeep' mit der tatsächlichen 'Array-Anzahl' festgelegt habe. Angenommen, ich möchte nicht wenige Objekte aus dem Array, also füge ich sie nicht zu itemsToKeep hinzu. Die Kapazität meiner itemsToKeep beträgt also 10, aber ich speichere tatsächlich nur 6 Objekte darin. Bedeutet das, dass ich Platz für 4 Objekte verschwende? PS finde keine Fehler, sondern versuche nur, die Komplexität der Algo zu verstehen. :)
tech_human
Ja, Sie haben Platz für vier Zeiger, die Sie nicht verwenden. Beachten Sie, dass das Array nur Zeiger enthält, nicht die Objekte selbst. Für vier Objekte bedeutet dies 16 Byte (32-Bit-Architektur) oder 32 Byte (64 Bit).
Benzado
Beachten Sie, dass jede der Lösungen bestenfalls 0 zusätzlichen Speicherplatz benötigt (Sie löschen Elemente an Ort und Stelle) oder im schlimmsten Fall die ursprüngliche Arraygröße verdoppelt (weil Sie eine Kopie des Arrays erstellen). Da es sich um Zeiger und nicht um vollständige Kopien von Objekten handelt, ist dies unter den meisten Umständen ziemlich billig.
Benzado
Okay, verstanden. Danke Benzado !!
tech_human
Laut diesem Beitrag wird der Hinweis der Methode arrayWithCapacity: über die Größe des Arrays nicht verwendet.
Kremk
28

Mit NSpredicate können Sie Elemente aus Ihrem veränderlichen Array entfernen. Dies erfordert kein for-Schleifen.

Wenn Sie beispielsweise ein NSMutableArray mit Namen haben, können Sie ein Prädikat wie dieses erstellen:

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

In der folgenden Zeile erhalten Sie ein Array, das nur Namen enthält, die mit b beginnen.

[namesArray filterUsingPredicate:caseInsensitiveBNames];

Wenn Sie Probleme beim Erstellen der benötigten Prädikate haben, verwenden Sie diesen Apple-Entwicklerlink .


quelle
3
Benötigt keine sichtbaren for-Schleifen. Es gibt eine Schleife in der Filteroperation, Sie sehen sie einfach nicht.
Hot Licks
18

Ich habe einen Leistungstest mit 4 verschiedenen Methoden durchgeführt. Jeder Test durchlief alle Elemente in einem Array mit 100.000 Elementen und entfernte jedes fünfte Element. Die Ergebnisse variierten mit / ohne Optimierung nicht sehr. Diese wurden auf einem iPad 4 durchgeführt:

(1) removeObjectAtIndex:- 271 ms

(2) removeObjectsAtIndexes:- 1010 ms (da das Erstellen des Indexsatzes ~ 700 ms dauert; ansonsten entspricht dies im Grunde dem Aufruf von removeObjectAtIndex: für jedes Element)

(3) removeObjects:- 326 ms

(4) Erstellen Sie ein neues Array mit Objekten, die den Test bestehen - 17 ms

Das Erstellen eines neuen Arrays ist also bei weitem am schnellsten. Die anderen Methoden sind alle vergleichbar, mit der Ausnahme, dass die Verwendung von removeObjectsAtIndexes: aufgrund der zum Erstellen des Indexsatzes erforderlichen Zeit mit mehr zu entfernenden Elementen schlechter ist.

user1032657
quelle
1
Haben Sie die Zeit gezählt, um ein neues Array zu erstellen und es anschließend freizugeben? Ich glaube nicht, dass es das alleine in 17 ms schafft. Plus 75.000 Auftrag?
Jack
Die Zeit, die benötigt wird, um ein neues Array zu erstellen und die
Zuordnung aufzuheben,
Sie haben das Reverse-Loop-Schema anscheinend nicht gemessen.
Hot Licks
Der erste Test entspricht dem Reverse-Loop-Schema.
user1032657
Was passiert, wenn Sie mit Ihrem neuen Array zurückbleiben und Ihr prevArray auf Null gesetzt ist? Sie müssten das newArray in den Namen des PrevArray kopieren (oder umbenennen). Andernfalls würde Ihr anderer Code darauf verweisen.
Aremvee
17

Verwenden Sie entweder eine Schleife, die über Indizes herunterzählt:

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

oder erstellen Sie eine Kopie mit den Objekten, die Sie behalten möchten.

Verwenden Sie insbesondere keine for (id object in array)Schleife oder NSEnumerator.

Jens Ayton
quelle
3
Sie sollten Ihre Antwort in Code m8 schreiben. haha hätte es fast verpasst.
FlowUI. SimpleUITesting.com
Das ist nicht richtig. "for (id object in array)" ist schneller als "for (NSInteger i = array.count - 1; i> = 0; --i)" und wird als schnelle Iteration bezeichnet. Die Verwendung des Iterators ist definitiv schneller als die Indizierung.
Jack
@jack - Aber wenn Sie ein Element unter einem Iterator entfernen, verursachen Sie normalerweise Chaos. (Und "schnelle Iteration" ist nicht immer viel schneller.)
Hot Licks
Die Antwort stammt aus dem Jahr 2008. Eine schnelle Iteration gab es nicht.
Jens Ayton
12

Für iOS 4+ oder OS X 10.6+ hat Apple eine passingTestReihe von APIs hinzugefügt NSMutableArray, z – indexesOfObjectsPassingTest:. Eine Lösung mit einer solchen API wäre:

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

Heutzutage können Sie die umgekehrte blockbasierte Aufzählung verwenden. Ein einfacher Beispielcode:

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];
}];

Ergebnis:

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

Eine weitere Option mit nur einer Codezeile:

[array filterUsingPredicate:[NSPredicate predicateWithFormat:@"shouldDelete == NO"]];
vikingosegundo
quelle
Gibt es eine Garantie dafür, dass das Array nicht neu zugewiesen wird?
Vgl.
Was meinst du mit Neuzuweisung?
Vikingosegundo
Beim Entfernen des Elements aus der linearen Struktur kann es effektiv sein, einen neuen zusammenhängenden Speicherblock zuzuweisen und alle Elemente dorthin zu verschieben. In diesem Fall würden alle Zeiger ungültig.
Vgl.
Da der Löschvorgang nicht wissen würde, wie viele Elemente am Ende gelöscht werden, ist es nicht sinnvoll, dies beim Entfernen zu tun. Wie auch immer: Implementierungsdetails, wir müssen Apple vertrauen, um vernünftigen Code zu schreiben.
Vikingosegundo
Erstens ist es nicht schöner (weil man zu viel darüber nachdenken muss, wie es überhaupt funktioniert) und zweitens ist Refactoring nicht sicher. Am Ende endete ich mit einer klassisch akzeptierten Lösung, die tatsächlich gut lesbar ist.
Renetik
8

Je nach den Kriterien, die den zu entfernenden Elementen entsprechen, können Sie deklarativer Folgendes verwenden:

[theArray filterUsingPredicate:aPredicate]

@ Nathan sollte sehr effizient sein

elp
quelle
6

Hier ist der einfache und saubere Weg. Ich möchte mein Array direkt im Aufruf der schnellen Aufzählung duplizieren:

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

Auf diese Weise führen Sie eine Kopie des Arrays auf, aus dem gelöscht wird, wobei beide dieselben Objekte enthalten. Ein NSArray enthält nur Objektzeiger, sodass dies in Bezug auf Speicher und Leistung völlig in Ordnung ist.

Matjan
quelle
2
Oder noch einfacher -for (LineItem *item in self.lineItems.copy)
Alexandre G
5

Fügen Sie die Objekte, die Sie entfernen möchten, zu einem zweiten Array hinzu und verwenden Sie nach der Schleife -removeObjectsInArray:.

Nathan Kinsinger
quelle
5

das sollte es tun:

    NSMutableArray* myArray = ....;

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

hoffe das hilft...

Pokot0
quelle
Obwohl unorthodox, habe ich festgestellt, dass das Rückwärtslaufen und Löschen eine saubere und einfache Lösung ist. Normalerweise auch eine der schnellsten Methoden.
Rpetrich
Was ist daran falsch? Es ist sauber, schnell, leicht lesbar und wirkt wie ein Zauber. Für mich sieht es nach der besten Antwort aus. Warum hat es eine negative Punktzahl? Vermisse ich hier etwas?
Steph Thirion
1
@Steph: Die Frage lautet "etwas eleganteres als das manuelle Aktualisieren des Index".
Steve Madsen
1
Oh. Ich hatte den Teil "Ich möchte den Index absolut nicht manuell aktualisieren" verpasst. danke steve. IMO ist diese Lösung eleganter als die gewählte (kein temporäres Array erforderlich), daher fühlen sich negative Stimmen dagegen unfair an.
Steph Thirion
@Steve: Wenn Sie die Änderungen überprüfen, wurde dieser Teil hinzugefügt, nachdem ich meine Antwort eingereicht habe. Wenn nicht, hätte ich mit "Rückwärts iterieren IST die eleganteste Lösung" geantwortet :). Einen schönen Tag noch!
Pokot0
1

Warum fügen Sie die zu entfernenden Objekte nicht einem anderen NSMutableArray hinzu? Wenn Sie mit dem Iterieren fertig sind, können Sie die gesammelten Objekte entfernen.

Paul Croarkin
quelle
1

Wie wäre es, wenn Sie die Elemente, die Sie löschen möchten, gegen das 'n'-te Element, das' n-1'-te Element usw. austauschen?

Wenn Sie fertig sind, ändern Sie die Größe des Arrays auf "vorherige Größe - Anzahl der Swaps".

Cyber ​​Oliveira
quelle
1

Wenn alle Objekte in Ihrem Array eindeutig sind oder Sie alle Vorkommen eines Objekts entfernen möchten, wenn es gefunden wurde, können Sie eine Array-Kopie schnell auflisten und das Objekt mit [NSMutableArray removeObject:] aus dem Original entfernen.

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

for (NSObject *anObject in myArrayCopy) {
    if (shouldRemove(anObject)) {
        [myArray removeObject:anObject];
    }
}
lajos
quelle
Was passiert, wenn das ursprüngliche myArray während +arrayWithArrayder Ausführung aktualisiert wird?
Bioffe
1
@bioffe: Dann hast du einen Fehler in deinem Code. NSMutableArray ist nicht threadsicher. Es wird erwartet, dass Sie den Zugriff über Sperren steuern. Siehe diese Antwort
dreamlax
1

Benzados Antwort oben ist das, was Sie für die Vorformung tun sollten. In einer meiner Anwendungen dauerte removeObjectsInArray eine Laufzeit von 1 Minute, das Hinzufügen zu einem neuen Array dauerte 0,023 Sekunden.

Kaiser
quelle
1

Ich definiere eine Kategorie, mit der ich mithilfe eines Blocks filtern kann:

@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

die dann so verwendet werden kann:

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

Eine schönere Implementierung könnte darin bestehen, die unten stehende Kategoriemethode für NSMutableArray zu verwenden.

@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

Der Prädikatblock kann implementiert werden, um die Verarbeitung für jedes Objekt im Array durchzuführen. Wenn das Prädikat true zurückgibt, wird das Objekt entfernt.

Ein Beispiel für ein Datumsarray zum Entfernen aller in der Vergangenheit liegenden Daten:

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

Rückwärts iterieren war jahrelang mein Favorit, aber lange Zeit bin ich nie auf den Fall gestoßen, dass das 'tiefste' Objekt (höchste Anzahl) zuerst entfernt wurde. Kurz bevor der Zeiger zum nächsten Index übergeht, gibt es nichts und es stürzt ab.

Benzados Weg kommt dem, was ich jetzt mache, am nächsten, aber ich hätte nie gedacht, dass es nach jedem Entfernen zu einer Stapelumbildung kommen würde.

unter Xcode 6 funktioniert das

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];
Aremvee
quelle