Melhor maneira de remover do NSMutableArray enquanto itera?

194

No Cocoa, se eu quiser fazer um loop através de um NSMutableArray e remover vários objetos que atendem a um determinado critério, qual é a melhor maneira de fazer isso sem reiniciar o loop toda vez que removo um objeto?

Obrigado,

Edit: Apenas para esclarecer - eu estava procurando a melhor maneira, por exemplo, algo mais elegante do que atualizar manualmente o índice em que estou. Por exemplo, em C ++ eu posso fazer;

iterator it = someList.begin();

while (it != someList.end())
{
    if (shouldRemove(it))   
        it = someList.erase(it);
}
Andrew Grant
fonte
9
Loop de trás para a frente.
Hot Licks
Ninguém responde o "POR QUE"
onmyway133 10/10
1
@HotLicks Um dos meus favoritos de todos os tempos e a solução mais subestimado na programação geral: D
Julian F. Weinert

Respostas:

388

Para maior clareza, gosto de fazer um loop inicial onde coleciono os itens a serem excluídos. Então eu os apago. Aqui está um exemplo usando a sintaxe do Objective-C 2.0:

NSMutableArray *discardedItems = [NSMutableArray array];

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

[originalArrayOfItems removeObjectsInArray:discardedItems];

Não há dúvidas sobre se os índices estão sendo atualizados corretamente ou outros pequenos detalhes da contabilidade.

Editado para adicionar:

Observou-se em outras respostas que a formulação inversa deve ser mais rápida. ou seja, se você percorrer a matriz e compor uma nova matriz de objetos a serem mantidos, em vez de objetos a serem descartados. Isso pode ser verdade (embora o que dizer da memória e do custo de processamento de alocar uma nova matriz e descartar a antiga?), Mas mesmo que seja mais rápido, pode não ser tão importante quanto seria para uma implementação ingênua, porque o NSArrays não se comporte como matrizes "normais". Eles falam a conversa, mas andam uma caminhada diferente. Veja uma boa análise aqui:

A formulação inversa pode ser mais rápida, mas nunca precisei me importar se é, porque a formulação acima sempre foi rápida o suficiente para minhas necessidades.

Para mim, a mensagem para levar para casa é usar qualquer formulação que seja mais clara para você. Otimize apenas se necessário. Pessoalmente, acho a formulação acima mais clara, e é por isso que a uso. Mas se a formulação inversa for mais clara para você, faça isso.

Christopher Ashworth
fonte
47
Cuidado, pois isso pode criar bugs se os objetos estiverem mais de uma vez em uma matriz. Como alternativa, você pode usar um NSMutableIndexSet e - (void) removeObjectsAtIndexes.
Georg Schölly
1
Na verdade, é mais rápido fazer o inverso. A diferença de desempenho é bastante grande, mas se sua matriz não for tão grande, os tempos serão triviais de qualquer maneira.
precisa saber é o seguinte
Eu costumava revers ... fez array como nulo .. só então adicionados o que eu queria e dados de recarga ... feito ... criado dummyArray que é espelho da série principal para que tenhamos principais dados reais
Fahim Parkar
Memória extra precisa ser alocada para fazer inversão. Não é um algoritmo no local e não é uma boa ideia em alguns casos. Quando você remove diretamente, apenas muda a matriz (o que é muito eficiente, pois não se move uma a uma, pode mudar uma grande parte), mas quando você cria uma nova matriz, precisa de toda a alocação e atribuição. Portanto, se você excluir apenas alguns itens, o inverso será muito mais lento. É um algoritmo típico que parece correto.
jack
82

Mais uma variação. Assim, você obtém legibilidade e bom desempenho:

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
fonte
Isso é incrível. Eu estava tentando remover vários itens da matriz e isso funcionou perfeitamente. Outros métodos estavam causando problemas :) Obrigado cara
AbhinavVinay 12/13
Corey, esta resposta (abaixo) disse que, removeObjectsAtIndexesé o pior método para remover os objetos, você concorda com isso? Estou perguntando isso porque sua resposta é muito antiga agora. Ainda assim, é bom escolher o melhor?
Hemang
Eu gosto muito desta solução em termos de legibilidade. Como é o desempenho em comparação à resposta @HotLicks?
Victor Maia Aldecôa
Esse método deve ser definitivamente incentivado ao excluir objetos da matriz no Obj-C.
boreas
enumerateObjectsUsingBlock:obteria o incremento do índice gratuitamente.
Pkamb
42

Este é um problema muito simples. Você apenas itera para trás:

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

Este é um padrão muito comum.

Hot Licks
fonte
teria perdido a resposta de Jens, porque ele não escreveu o código: P .. thnx m8
FlowUI. SimpleUITesting.com
3
Este é o melhor método. É importante lembrar que a variável de iteração deve ser assinada, apesar de os índices da matriz no Objective-C serem declarados como não assinados (posso imaginar como a Apple se arrepende disso agora).
Mojuba
39

Algumas das outras respostas teriam um desempenho ruim em matrizes muito grandes, porque os métodos gostam removeObject:e removeObjectsInArray:envolvem fazer uma pesquisa linear do receptor, o que é um desperdício, porque você já sabe onde está o objeto. Além disso, qualquer chamada para removeObjectAtIndex:terá que copiar valores do índice para o final da matriz em um slot por vez.

Mais eficiente seria o seguinte:

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

Como definimos a capacidade de itemsToKeep, não perdemos tempo copiando valores durante um redimensionamento. Como não modificamos a matriz no local, estamos livres para usar a Enumeração rápida. Usar setArray:para substituir o conteúdo de arraycom itemsToKeepserá eficiente. Dependendo do seu código, você pode até substituir a última linha por:

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

Portanto, não há nem a necessidade de copiar valores, apenas trocar um ponteiro.

benzado
fonte
Este algo prova ser bom em termos de complexidade de tempo. Eu estou tentando entender isso em termos de complexidade do espaço. Tenho a mesma implementação em torno da qual defino a capacidade de 'itemsToKeep' com a real 'Array count'. Mas diga que eu não quero poucos objetos da matriz para não adicioná-los a itemsToKeep. Portanto, a capacidade dos meus itemsToKeep é 10, mas na verdade eu armazeno apenas 6 objetos. Isso significa que estou desperdiçando espaço de 4 objetos? O PS não está encontrando falhas, apenas tentando entender a complexidade de algo. :)
tech_human
Sim, você tem espaço reservado para quatro ponteiros que não está usando. Lembre-se de que a matriz contém apenas ponteiros, não os objetos em si, portanto, para quatro objetos que significam 16 bytes (arquitetura de 32 bits) ou 32 bytes (64 bits).
benzado
Observe que qualquer uma das soluções precisará, na melhor das hipóteses, de 0 espaço adicional (você excluirá os itens no local) ou, na pior das hipóteses, dobrará o tamanho original da matriz (porque você faz uma cópia da matriz). Novamente, como estamos lidando com ponteiros e não com cópias completas de objetos, isso é bastante barato na maioria das circunstâncias.
benzado
Ok entendi. Graças à benzado !!
tech_human
De acordo com este post, a dica do método arrayWithCapacity: sobre o tamanho da matriz não está sendo realmente usada.
Kremk
28

Você pode usar o NSpredicate para remover itens da sua matriz mutável. Isso não requer para loops.

Por exemplo, se você tiver um NSMutableArray de nomes, poderá criar um predicado como este:

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

A linha a seguir apresentará uma matriz que contém apenas nomes começando com b.

[namesArray filterUsingPredicate:caseInsensitiveBNames];

Se você tiver problemas para criar os predicados necessários, use este link para desenvolvedor da apple .


fonte
3
Não requer visibilidade para loops. Há um loop na operação do filtro, você simplesmente não o vê.
Hot Licks
18

Eu fiz um teste de desempenho usando 4 métodos diferentes. Cada teste repetiu todos os elementos em uma matriz de 100.000 elementos e removeu cada quinto item. Os resultados não variaram muito com / sem otimização. Isso foi feito em um iPad 4:

(1) removeObjectAtIndex:- 271 ms

(2) removeObjectsAtIndexes:- 1010 ms (porque a criação do conjunto de índices leva ~ 700 ms; caso contrário, é basicamente o mesmo que chamar removeObjectAtIndex: para cada item)

(3) removeObjects:- 326 ms

(4) faça uma nova matriz com objetos que passam no teste - 17 ms

Portanto, criar uma nova matriz é de longe o mais rápido. Os outros métodos são todos comparáveis, exceto que o uso de removeObjectsAtIndexes: será pior com mais itens a serem removidos, devido ao tempo necessário para criar o conjunto de índices.

user1032657
fonte
1
Você contou o tempo para criar uma nova matriz e desalocá-la posteriormente. Não acredito que possa fazer isso sozinho em 17 ms. Mais 75.000 tarefas?
tomada
O tempo necessário para criar e desaloque uma nova matriz é mínima
user1032657
Você aparentemente não mediu o esquema de loop reverso.
Hot Licks
O primeiro teste é equivalente ao esquema de loop reverso.
User1032657
o que acontece quando você fica com seu newArray e seu prevArray é nulo? Você teria que copiar o newArray para o que o PrevArray foi nomeado (ou renomeá-lo), caso contrário, como seu outro código faria referência a ele?
Aremvee
17

Use o loop com contagem decrescente sobre os índices:

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

ou faça uma cópia com os objetos que você deseja manter.

Em particular, não use um for (id object in array)loop ou NSEnumerator.

Jens Ayton
fonte
3
você deve escrever sua resposta no código m8. haha quase perdeu.
FlowUI. SimpleUITesting.com
Isto não está certo. "for (objeto de identificação na matriz)" é mais rápido que "para (NSInteger i = array.count - 1; i> = 0; --i)" e é chamado de iteração rápida. O uso do iterador é definitivamente mais rápido que a indexação.
tomada
@jack - Mas se você remover um elemento de um iterador, normalmente cria estragos. (E "iteração rápida" nem sempre é muito mais rápida.)
Hot Licks
A resposta é de 2008. A iteração rápida não existia.
Jens Ayton #
12

Para iOS 4+ ou OS X 10.6+, a Apple adicionou uma passingTestsérie de APIs em NSMutableArray, como – indexesOfObjectsPassingTest:. Uma solução com essa API seria:

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

Atualmente, você pode usar a enumeração baseada em bloco invertida. Um código de exemplo simples:

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

Resultado:

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

outra opção com apenas uma linha de código:

[array filterUsingPredicate:[NSPredicate predicateWithFormat:@"shouldDelete == NO"]];
vikingosegundo
fonte
Existe alguma garantia de que a matriz não seria realocada?
Cfr
O que você quer dizer com realocação?
Vikingosegundo
Ao remover o elemento da estrutura linear, pode ser eficaz alocar um novo bloco de memória contíguo e mover todos os elementos para lá. Nesse caso, todos os ponteiros seriam invalidados.
Cfr
Como a operação de exclusão não saberia quantos elementos serão apostados excluídos no final, não faria sentido fazê-lo durante a remoção. Enfim: detalhes de implementação, temos que confiar na apple para escrever um código razoável.
Vikingosegundo
Primeiro não é mais agradável (porque você tem que pensar muito sobre como ele funciona) e o segundo não é refatoração segura. Então, no final, terminei com uma solução aceita clássica que é bastante legível na verdade.
Renetik 13/07/19
8

De uma maneira mais declarativa, dependendo dos critérios correspondentes aos itens a serem removidos, você pode usar:

[theArray filterUsingPredicate:aPredicate]

@ Nathan deve ser muito eficiente

elp
fonte
6

Aqui está a maneira fácil e limpa. Eu gosto de duplicar minha matriz diretamente na chamada de enumeração rápida:

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

Dessa forma, você enumera por meio de uma cópia da matriz da qual está sendo excluído, ambos mantendo os mesmos objetos. Um NSArray contém ponteiros de objeto apenas, portanto, este é um ótimo desempenho de memória / desempenho.

Matjan
fonte
2
Ou ainda mais simples -for (LineItem *item in self.lineItems.copy)
Alexandre G
5

Adicione os objetos que você deseja remover a uma segunda matriz e, após o loop, use -removeObjectsInArray :.

Nathan Kinsinger
fonte
5

Isso deve servir:

    NSMutableArray* myArray = ....;

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

espero que isto ajude...

Pokot0
fonte
Embora não seja ortodoxo, achei a iteração para trás e a exclusão, por ser uma solução limpa e simples. Geralmente, um dos métodos mais rápidos também.
Rpetrich 01/08/09
O que há de errado nisso? É limpo, rápido, de fácil leitura e funciona como um encanto. Para mim, parece a melhor resposta. Por que tem uma pontuação negativa? Estou faltando alguma coisa aqui?
Steph Thirion
1
@ Steph: A pergunta afirma "algo mais elegante do que atualizar manualmente o índice".
Steve Madsen
1
ah Eu tinha perdido a parte Eu absolutamente não quero atualizar manualmente o índice. obrigado steve. Na IMO, essa solução é mais elegante do que a escolhida (não é necessária uma matriz temporária); portanto, votos negativos são injustos.
Steph Thirion
@ Steve: Se você verificar as edições, essa parte foi adicionada depois que eu enviei minha resposta .... se não, eu teria respondido com "Iterar para trás é a solução mais elegante" :). Tenha um bom dia!
Pokot0
1

Por que você não adiciona os objetos a serem removidos para outro NSMutableArray. Quando você terminar de iterar, poderá remover os objetos que você coletou.

Paul Croarkin
fonte
1

Que tal trocar os elementos que você deseja excluir pelo elemento "n", "n-1" e assim por diante?

Quando terminar, redimensione a matriz para 'tamanho anterior - número de trocas'

Cyber ​​Oliveira
fonte
1

Se todos os objetos em sua matriz forem exclusivos ou você desejar remover todas as ocorrências de um objeto quando encontrado, você poderá enumerar rapidamente em uma cópia da matriz e usar [NSMutableArray removeObject:] para remover o objeto do original.

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

for (NSObject *anObject in myArrayCopy) {
    if (shouldRemove(anObject)) {
        [myArray removeObject:anObject];
    }
}
lajos
fonte
o que acontece se o myArray original for atualizado enquanto +arrayWithArrayestiver sendo executado?
bioffe 16/03/11
1
@bioffe: Então você tem um bug no seu código. O NSMutableArray não é seguro para threads, é esperado que você controle o acesso via bloqueios. Veja esta resposta
dreamlax
1

A resposta do benzado acima é o que você deve fazer para obter a pré-forma. Em um dos meus aplicativos, o removeObjectsInArray levou um tempo de execução de 1 minuto, apenas a adição a uma nova matriz levou 0,023 segundos.

Kaiser
fonte
1

Defino uma categoria que me permite filtrar usando um bloco, assim:

@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

que pode ser usado assim:

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

Uma implementação melhor seria usar o método de categoria abaixo no NSMutableArray.

@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

O bloco de predicado pode ser implementado para processar em cada objeto na matriz. Se o predicado retornar true, o objeto será removido.

Um exemplo para uma matriz de datas para remover todas as datas anteriores:

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

Iterar para trás era o meu favorito por anos, mas por um longo tempo nunca encontrei o caso em que o objeto 'mais profundo' (contagem mais alta) foi removido primeiro. Momentaneamente antes de o ponteiro passar para o próximo índice, não há nada e ele trava.

O caminho de Benzado é o mais próximo do que faço agora, mas eu nunca percebi que haveria a reorganização da pilha após cada remoção.

no Xcode 6 isso funciona

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
fonte