Tak, używanie NSSet jest rozsądnym podejściem.
Aby dodać do odpowiedzi Jima Pulsa, oto alternatywne podejście do usuwania duplikatów przy zachowaniu porządku:
// Initialise a new, empty mutable array
NSMutableArray *unique = [NSMutableArray array];
for (id obj in originalArray) {
if (![unique containsObject:obj]) {
[unique addObject:obj];
}
}
Jest to zasadniczo to samo podejście, co Jim's, ale kopiuje unikalne elementy do świeżej, zmiennej tablicy, zamiast usuwać duplikaty z oryginału. To sprawia, że jest nieco bardziej wydajna pamięciowo w przypadku dużej tablicy z dużą ilością duplikatów (nie ma potrzeby wykonywania kopii całej tablicy) i jest moim zdaniem trochę bardziej czytelna.
Zauważ, że w obu przypadkach sprawdzenie, czy element jest już uwzględniony w tablicy docelowej (używając containsObject:w moim przykładzie lub indexOfObject:inRange:w Jim's), nie jest dobrze skalowane dla dużych tablic. Te testy są uruchamiane w czasie O (N), co oznacza, że jeśli podwoisz rozmiar oryginalnej tablicy, wykonanie każdego sprawdzenia potrwa dwa razy dłużej. Ponieważ sprawdzasz każdy obiekt w tablicy, będziesz także uruchamiać więcej tych droższych testów. Ogólny algorytm (zarówno mój, jak i Jima) działa w czasie O (N 2 ), co szybko staje się kosztowne, gdy oryginalna tablica rośnie.
Aby sprowadzić to do czasu O (N), możesz użyć a NSMutableSetdo przechowywania rekordu elementów już dodanych do nowej tablicy, ponieważ wyszukiwania NSSet mają wartość O (1) zamiast O (N). Innymi słowy, sprawdzenie, czy element jest członkiem zestawu NSSet, zajmuje tyle samo czasu, niezależnie od tego, ile elementów znajduje się w zestawie.
Kod wykorzystujący to podejście wyglądałby mniej więcej tak:
NSMutableArray *unique = [NSMutableArray array];
NSMutableSet *seen = [NSMutableSet set];
for (id obj in originalArray) {
if (![seen containsObject:obj]) {
[unique addObject:obj];
[seen addObject:obj];
}
}
To wciąż wydaje się trochę marnotrawne; nadal generujemy nową tablicę, gdy pytanie jasno wskazywało, że oryginalna tablica jest zmienna, więc powinniśmy być w stanie usunąć ją na miejscu i zaoszczędzić trochę pamięci. Coś takiego:
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++;
}
}
AKTUALIZACJA : Yuri Niyazov wskazał, że moja ostatnia odpowiedź faktycznie działa w czasie O (N 2 ), ponieważ removeObjectAtIndex:prawdopodobnie działa w czasie O (N).
(Mówi „prawdopodobnie”, ponieważ nie wiemy na pewno, jak to zaimplementowano; ale jedną z możliwych implementacji jest to, że po usunięciu obiektu w indeksie X metoda przechodzi przez każdy element od indeksu X + 1 do ostatniego obiektu w tablicy , przenosząc je do poprzedniego indeksu. Jeśli tak jest, to rzeczywiście jest to wydajność O (N)).
Więc co robić? To zależy od sytuacji. Jeśli masz dużą tablicę i spodziewasz się tylko niewielkiej liczby duplikatów, funkcja de-duplikacji w miejscu będzie działać dobrze i pozwoli zaoszczędzić na tworzeniu zduplikowanej tablicy. Jeśli masz tablicę, w której spodziewasz się wielu duplikatów, prawdopodobnie najlepszym rozwiązaniem jest utworzenie oddzielnej, pozbawionej dupleksu tablicy. Wniosek jest taki, że notacja duże-O opisuje tylko charakterystykę algorytmu, a nie mówi ostatecznie, który jest najlepszy w danych okolicznościach.