La meilleure façon de supprimer les valeurs en double de NSMutableArray dans Objective-C?

Question

La meilleure façon de supprimer les valeurs en double (NSString) de NSMutableArray dans Objective-C?

Est-ce la façon la plus simple et la plus efficace de le faire?

 uniquearray = [[NSSet setWithArray:yourarray] allObjects];
 

Answer 1

Votre approche NSSet est la meilleure si vous ne vous souciez pas de l'ordre des objets, mais encore une fois, si vous ne vous inquiétez pas de l'ordre, pourquoi ne les stockez-vous pas en NSSet pour commencer?

Si vous vous inquiétez de l'ordre, passez en revue une copie du tableau:

 NSArray *copy = [mutableArray copy];
NSInteger index = [copy count] - 1;
for (id object in [copy reverseObjectEnumerator]) {
    if ([mutableArray indexOfObject:object inRange:NSMakeRange(0, index)] != NSNotFound) {
        [mutableArray removeObjectAtIndex:index];
    }
    index--;
}
[copy release];
 

Answer 2

Je sais que c'est une vieille question, mais il existe un moyen plus élégant de supprimer les doublons dans un NSArray .

Si nous utilisons les opérateurs d’objets du codage des valeurs clés, nous pouvons le faire:

 uniquearray = [yourarray valueForKeyPath:@"@distinctUnionOfObjects.self"];
 

Answer 3

Oui, à l'aide de NSSet est une approche pratique.

Pour ajouter à Jim Puls' réponse, voici une autre approche du décapage des doublons, tout en conservant l'ordre:

// Initialise a new, empty mutable array 
NSMutableArray *unique = [NSMutableArray array];

for (id obj in originalArray) {
    if (![unique containsObject:obj]) {
        [unique addObject:obj];
    }
}

C'est essentiellement la même approche que celle de Jim, mais des copies des objets uniques pour une nouvelle mutable tableau plutôt que de la suppression des doublons à partir de l'original. De ce fait, il est légèrement plus efficace en terme de mémoire dans le cas d'un grand tableau avec beaucoup de doublons (pas besoin de faire une copie de l'ensemble de la matrice), et il est à mon avis un peu plus lisible.

Notez que dans les deux cas, vérifier pour voir si un élément est déjà inclus dans la cible de tableau (à l'aide d' containsObject: dans mon exemple, ou indexOfObject:inRange: dans le Jim's) n'est pas à l'échelle pour de grands tableaux. Ces contrôles s'exécuter en O(N) le temps, ce qui signifie que si vous doublez la taille du tableau original puis chaque case prendra deux fois plus de temps à s'exécuter. Puisque vous êtes en train de faire la vérification pour chaque objet du tableau, vous serez également en cours d'exécution de plus de ceux qui sont les plus coûteux contrôles. L'ensemble de l'algorithme (à la fois de la mine et Jim) s'exécute en O(N²), qui se coûteux rapidement que le tableau d'origine grandit.

Pour obtenir jusqu'à O(N) le temps que vous pourriez utiliser un NSMutableSet de stocker un enregistrement de ce qui a déjà ajouté à la nouvelle matrice, depuis NSSet des recherches sont en O(1) au lieu de O(N). En d'autres termes, de vérifier si un élément est un membre d'une NSSet prend le même temps, indépendamment de la façon dont de nombreux éléments sont dans le jeu.

Code à l'aide de cette approche devrait ressembler à quelque chose comme ceci:

NSMutableArray *unique = [NSMutableArray array];
NSMutableSet *seen = [NSMutableSet set];

for (id obj in originalArray) {
    if (![seen containsObject:obj]) {
        [unique addObject:obj];
        [seen addObject:obj];
    }
}

Cela semble encore un peu de gaspillage; nous sommes toujours à la génération d'un nouveau tableau, lorsque la question de préciser que le tableau d'origine est mutable, donc nous devrions être en mesure de dupe en place et d'économiser de la mémoire. Quelque chose comme ceci:

NSMutableSet *seen = [NSMutableSet set];
NSUInteger i = 0;

while (i < [originalArray count]) {
    id obj = [originalArray objectAtIndex:i];

    if ([seen containsObject:obj]) {
        [originalArray removeObjectAtIndex:i];
        // NB: we *don't* increment i here; since
        // we've removed the object previously at
        // index i, [originalArray objectAtIndex:i]
        // now points to the next object in the array.
    } else {
        [seen addObject:obj];
        i++;
    }
}

---

Mise à JOUR: Yuri Niyazov a souligné que ma dernière réponse exécute en O(N²) parce qu' removeObjectAtIndex: probablement s'exécute en O(N) fois.

(Il dit "probablement" parce que nous ne savons pas vraiment comment il est mis en œuvre; mais une mise en œuvre possible est que, après la suppression de l'objet à l'index X la méthode, puis une boucle sur chaque élément à partir de l'index X+1 pour le dernier objet dans le tableau, en les déplaçant à l'indice précédent. Si c'est le cas, alors c'est bien O(N).)

Alors, que faire? Cela dépend de la situation. Si vous avez un grand tableau et que vous êtes seul à attendre un petit nombre de doublons puis la dé-duplication fonctionnent très bien, et vous éviter d'avoir à construire un double tableau. Si vous avez un tableau où vous vous attendez à beaucoup de doublons, puis la construction d'un distinct, de-dupe tableau est probablement la meilleure approche. Faut-il retenir ici est que le big-O notation décrit les caractéristiques d'un algorithme, il ne vous dira pas définitivement qui est le mieux pour toutes les circonstances.

Answer 4

Si vous utilisez iOS 5+ (ce qui couvre l'ensemble du monde iOS), la meilleure utilisation NSOrderedSet. Il supprime les doublons et conserve l'ordre de votre NSArray.

Il suffit de ne

NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:yourArray];

Vous pouvez maintenant convertir un unique NSArray

NSArray *uniqueArray = orderedSet.array;

Ou tout simplement utiliser le orderedSet parce qu'il a les mêmes méthodes comme un NSArray comme objectAtIndex:, firstObject et ainsi de suite.

Une adhésion à vérifier avec contains est encore plus rapide sur l' NSOrderedSet qu'il serait sur un NSArray

Pour plus de caisse de la NSOrderedSet de Référence

Answer 5

Disponible sous OS X v10.7 et versions ultérieures.

Si vous vous inquiétez de la commande, la bonne façon de faire

 NSArray *no = [[NSOrderedSet orderedSetWithArray:originalArray]allObjects];
 

Voici le code de suppression des valeurs en double de NSArray dans Order.