Kiedy lepiej jest używać zestawu NSSet zamiast NSArray?

Odpowiedzi:

173

Gdy kolejność elementów w kolekcji nie jest ważna, zestawy zapewniają lepszą wydajność wyszukiwania elementów w kolekcji.

Powodem jest to, że zestaw używa wartości skrótu do wyszukiwania elementów (takich jak słownik), podczas gdy tablica musi iterować po całej zawartości, aby znaleźć określony obiekt.

Ole Begemann
źródło
9
log (1) vs log (n)
rohan-patel.
25
@ rohan-patel Poprawnie to O (1) vs O (n)
Mansurov Ruslan
1
Jeśli uporządkowane: O (1) vs O (logn), ponieważ ma zastosowanie wyszukiwanie binarne. Jeśli nieuporządkowany, to O (1) vs O (n)
baskInEminence
180

Obraz z Dokumentacji Apple opisuje to bardzo dobrze:

Kolekcje Objective-C

Arrayto uporządkowana (kolejność jest zachowywana podczas dodawania) sekwencji elementów

[array addObject:@1];
[array addObject:@2];
[array addObject:@3];
[array addObject:@4];
[array addObject:@6];
[array addObject:@4];
[array addObject:@1];
[array addObject:@2];

[1, 2, 3, 4, 6, 4, 1, 2]

Setjest odrębną (bez duplikatów), nieuporządkowaną listą elementów

[set addObject:@1];
[set addObject:@2];
[set addObject:@3];
[set addObject:@4];
[set addObject:@6];
[set addObject:@4];
[set addObject:@1];
[set addObject:@2];

[1, 2, 6, 4, 3]
James Webster
źródło
2
W swoim przykładzie dodajesz prymitywy do tablicy i zbioru. Żadne nie jest możliwe, ponieważ mogą zawierać tylko obiekty.
FreeAsInBeer
10
Dzięki za twoją edycję @Zaheer, ale faktycznie była nieprawidłowa. Nie dodawałem prymitywów. Dodawałem literały.
James Webster,
Świetne wyjaśnienie :) +1 :)
Karun
1
Uwielbiam twoje wyjaśnienie! +1 za to
bunt
66

Najlepszą odpowiedzią na to jest własna dokumentacja Apple .

wprowadź opis obrazu tutaj

Główna różnica polega na tym, że NSArraydotyczy kolekcji zamówionej i NSSetnieuporządkowanej.

Istnieje kilka artykułów, które mówią o różnicy w prędkości między nimi, jak ten . Jeśli przeglądasz nieuporządkowaną kolekcję, NSSetto świetnie. Jednak w wielu przypadkach musisz robić rzeczy, które tylko on NSArraymoże zrobić, więc poświęcasz prędkość dla tych umiejętności.

NSSet

  • Przede wszystkim dostęp do elementów przez porównanie
  • Niezamówiony
  • Nie zezwala na duplikaty

NSArray

  • Może uzyskać dostęp do elementów według indeksu
  • Zamówione
  • Umożliwia duplikaty

Tak naprawdę to wszystko! Jeśli to pomoże, to daj mi znać.

woz
źródło
Nie musisz zawsze poświęcać się NSSetna rzecz indeksowania. Często używa się dwóch różnych struktur danych dla tych samych danych. Albo budujesz i indeksujesz na tej tablicy :) Ale wtedy lepiej jest użyć bazy danych, która ma już zaimplementowaną.
Sulthan
„Zbuduj indeks na tej tablicy”. Nie można utworzyć indeksu w NSSet. Istnieje wiele różnych technik, których możesz użyć. A jeśli musisz poświęcić ZARÓWNO pamięć, jak i moc obliczeniową, robisz to źle.
Sulthan
Ponieważ pytanie dotyczy NSSeti NSArray, moja odpowiedź jest dokładna i kompletna. Tak, możesz budować inne struktury danych, ale ja tylko porównuję te dwie.
woz
Głosowałem za, ale twoja odpowiedź jest nieprawidłowa, kiedy mówisz o ofiarach. Jeśli potrzebujesz jakiejś funkcjonalności NSArrayi jakiejś funkcjonalności z NSSet, poprawną odpowiedzią nie jest „używaj NSArrayi poświęć wydajność”. Odpowiedź brzmi: połącz oba lub użyj innej struktury danych.
Sulthan
Powiedziałbym, że główna różnica dotyczy unikatowych obiektów, gdzie tablica może mieć duplikaty. Aspekt porządku jest drugorzędny w stosunku do tego faktu.
malhal
12

NSOrderedSet jest dostępny w iOS 5+, więc główna różnica polega na tym, czy chcesz zduplikować obiekty w strukturze danych.

Jason
źródło
9

NSArray :

  1. Uporządkowane zbieranie danych
  2. Umożliwia duplikaty
  3. Jest to obiekt typu kolekcja

NSSet :

  1. Nieuporządkowane gromadzenie danych
  2. Nie zezwala na duplikaty
  3. Jest to również obiekt typu kolekcja
iOS Lifee
źródło
7

Tablica służy do uzyskiwania dostępu do elementów według ich indeksu. Dowolny element można wstawić do tablicy wielokrotnie. Tablice zachowują kolejność swoich elementów.

Zestaw jest używany w zasadzie tylko do sprawdzenia, czy przedmiot jest w kolekcji, czy nie. Pozycje nie mają pojęcia kolejności ani indeksowania. Nie możesz mieć elementu w zestawie dwukrotnie.

Jeśli tablica chce sprawdzić, czy zawiera element, musi sprawdzić wszystkie jej elementy. Zestawy są zaprojektowane do korzystania z szybszych algorytmów.

Możesz sobie wyobrazić zbiór jak słownik bez wartości.

Zauważ, że tablica i zbiór nie są jedynymi strukturami danych. Istnieją inne, np. Queue, Stack, Heap, Fibonacci's Heap. Poleciłbym przeczytać książkę o algorytmach i strukturach danych.

Więcej informacji można znaleźć w Wikipedii .

Sulthan
źródło
Właściwie tablicę należy sprawdzić tylko do momentu znalezienia elementu. Jeśli element JEST w tablicy, bardzo rzadko trzeba będzie sprawdzić każdy element.
FreeAsInBeer
Tak, jak mówisz „jeśli element JEST w tablicy”. Jeśli się tego spodziewasz, nie musisz sprawdzać, czy tam jest, czy nie. Złożoność containsoperacji to O(n). Liczba porównań, gdy nie ma w tablicy, wynosi n. Średnia liczba porównań, gdy obiekt znajduje się w tablicy, wynosi n/2. Nawet jeśli obiekt zostanie znaleziony, wydajność jest okropna.
Sulthan
Wydajność byłaby okropna tylko w przypadku dużej macierzy. Jeśli wiesz, że tablica może stać się dość duża, istnieją sposoby na poprawę jej wydajności, takie jak użycie tablicy tablic.
FreeAsInBeer
Jeśli operacja równości jest kosztowna, zobaczysz różnicę nawet w przypadku tablic z 3 elementami. Takie samo zachowanie, jak w przypadku dużej tablicy, może się zdarzyć, gdy często powtarzasz operację (np. Używaj operacji w cyklu „for”). Czy słyszałeś o zamortyzowanej złożoności? Złożoność jest nadal liniowa, a wydajność jest okropna w porównaniu do zestawu (zwykle ze stałą złożonością).
Sulthan
Oczywiście będzie różnica, po prostu stwierdzam, że notacja dużego O jest wykładnicza; przy małych tablicach różnica będzie niewielka. Ponadto NSArrays mają inne zalety szybkości w stosunku do NSSets. Jak zawsze, to kompromis.
FreeAsInBeer
5
NSArray *Arr;
NSSet *Nset;

Arr=[NSArray arrayWithObjects:@"1",@"2",@"3",@"4",@"2",@"1", nil];
Nset=[NSSet setWithObjects:@"1",@"2",@"3",@"3",@"5",@"5", nil];

NSLog(@"%@",Arr);
NSLog(@"%@",Nset);

tablica

04.12.2015 11: 05: 40.935 [598: 15730] (1, 2, 3, 4, 2, 1)

zestaw

04.12.2015 11: 05: 43.362 [598: 15730] {(3, 1, 2, 5)}

abc221
źródło
4

Główne różnice zostały już podane w innych odpowiedziach.

Chciałbym tylko zauważyć, że ze względu na sposób implementacji zestawów i słowników (tj. Za pomocą skrótów), należy uważać, aby nie używać obiektów mutowalnych dla kluczy.

Jeśli klucz jest zmutowany, to hash (prawdopodobnie) również się zmieni, wskazując na inny indeks / zasobnik w tablicy hash. Oryginalna wartość nie zostanie usunięta i będzie faktycznie brana pod uwagę przy wyliczaniu lub pytaniu struktury o jej rozmiar / liczbę.

Może to prowadzić do naprawdę trudnych do zlokalizowania błędów.

joakim
źródło
3

Tutaj można znaleźć dość dokładne porównanie struktur NSArrayi NSSetdanych.

Krótkie wnioski:

Tak, NSArray jest szybszy niż NSSet pod względem prostego trzymania i iteracji. Zaledwie 50% szybciej przy konstruowaniu i aż o 500% szybciej przy iteracji. Lekcja: jeśli potrzebujesz tylko iterować zawartość, nie używaj NSSet.

Oczywiście, jeśli chcesz przeprowadzić testy pod kątem włączenia, ciężko pracuj, aby uniknąć NSArray. Nawet jeśli potrzebujesz zarówno iteracji, jak i testów włączenia, prawdopodobnie nadal powinieneś wybrać zestaw NSSet. Jeśli chcesz zachować porządek w swojej kolekcji i przetestować ją pod kątem włączenia, powinieneś rozważyć przechowywanie dwóch kolekcji (NSArray i NSSet), z których każda zawiera te same obiekty.

NSDictionary jest wolniejszy w tworzeniu niż NSMapTable - ponieważ musi skopiować kluczowe dane. Nadrabia to szybszym wyszukiwaniem. Oczywiście te dwie osoby mają różne możliwości, więc w większości przypadków to ustalenie powinno opierać się na innych czynnikach.

Che
źródło
Chociaż może to teoretycznie odpowiedzieć na pytanie, lepiej byłoby zawrzeć tutaj zasadnicze części odpowiedzi i podać link do odniesienia.
Tunaki,
2

Zwykle używasz zestawu, gdy szybkość dostępu jest najważniejsza, a kolejność nie ma znaczenia lub jest określana w inny sposób (za pomocą predykatu lub deskryptora sortowania). Na przykład dane podstawowe używają zestawów, gdy dostęp do obiektów zarządzanych uzyskuje się za pośrednictwem relacji to-many

iDevAmit
źródło
1

Żeby dodać trochę tego, używam czasami seta tylko po to, aby usunąć duplikaty z tablicy, takie jak: -

NSMutableSet *set=[[NSMutableSet alloc]initWithArray:duplicateValueArray]; // will remove all the duplicate values
tryKuldeepTanwar
źródło