Zastanawiam się, co jest notacją big-O dla iteracji poprzez NSSet. Odpowiedzią na NSArray jest oczywiście O (n) - ale jaka jest odpowiedź dla NSSet? Ponadto - zakładam, że ta sama odpowiedź miałaby zastosowanie do NSDictionary?Co to jest notacja big-O dla iteracji przez NSSet i NSDictionary
Można się zorientować w złożoności obliczeniowej struktur danych Apple, patrząc na komentarze w nagłówkach ich zmostkowanych odpowiedników Core Foundation (ponieważ w zasadzie używają tego samego kodu pod maską).
ciekawe, złożoność czas CFArray jest nie faktycznie gwarancją O (n):
złożoność obliczeniowa
Czas dostępu do wartości w tablicy gwarantuje się w najgorszy O (lg N) dla każdego wdrożenia, bieżącego i przyszłego, ale będzie często być O (1) (stały czas). Liniowe operacje wyszukiwania podobnie mają najgorszy przypadek złożoności O (N * lg N), chociaż zwykle granice są bardziej rygorystyczne i tak dalej. Operacje wstawiania lub usuwania będą zwykle liniowe pod względem liczby wartości w tablicy, ale może być wyraźnie O (N * lg N) w najgorszym przypadku w niektórych implementacjach. Nie ma preferowanych pozycji w tablicy dla wydajności; oznacza to, że niekoniecznie jest szybszy dostęp do wartości o niskich indeksach lub wstawianie lub usuwanie wartości z wysokimi indeksami lub cokolwiek.
te zawiłości czasu sugerują, że CFArray (a więc NSArray) może być faktycznie realizowane w postaci drzewa (badania wskazują, że może to być nawet przełączanie pomiędzy wieloma podstawowych struktur danych).
Podobnie do CFDictionary, granice podane mają dość szeroki zakres:
złożoność obliczeniowa
Czas dostępu do wartości w słowniku jest gwarantowana w najgorszym O (n) w przypadku dowolna implementacja, obecna i przyszła, ale będzie często być O (1) (stały czas). Operacje wstawiania lub usuwania zwykle będą również stałym czasem, ale w niektórych implementacjach są O (N * N) w najgorszym przypadku . Dostęp do wartości za pomocą klucza jest szybszy niż bezpośredni dostęp do wartości (jeśli istnieją takie operacje ). Słowniki będą zwykle używać znacznie więcej pamięci niż tablica o tej samej liczbie wartości.
nie byłem w stanie znaleźć podobny komentarz w nagłówkach Fundacji rdzenia dla CFSet, ale inspekcja kodu źródłowego wskazuje, że jest ona oparta na CFBasicHash, czyli tabeli mieszania, więc złożoność czas byłoby tak typowe dla tabeli mieszania - O (1) wstawianie, usuwanie i testowanie zazwyczaj i O (n) w najgorszym przypadku.
Jeśli naprawdę chcesz dowiedzieć się, jak działają te struktury danych, Core Foundation ma otwarte oprogramowanie źródłowe, więc możesz przeczytać kod źródłowy pod numerem Apple's website.
Jeśli zależy Ci na wydajności, upewnij się, że używasz "szybkiego wyliczenia" lub bloków. Nie używaj zwykłej pętli C 'for' lub' while'. https://developer.apple.com/library/ios/documentation/Cocoa/Conceptual/Collections/Articles/Enumerators.html –
To pytanie jest raczej tematem ciekawości niż faktycznym pytaniem. – YogevSitton
Rozumiem. Cóż, wtedy odpowiedź zależy od tego, co jest w zestawie. NSSet nie jest prostą klasą, nie zdziwiłbym się, gdyby implementacja była dziesiątkami tysięcy tysięcy linii kodu. Na początek nie ma nawet prawdziwej klasy o nazwie "NSSet". To tylko nazwa używana do łączenia wszystkich klas, które wchodzą w skład zestawów, która to klasa jest faktycznie używana, zmienia się w zależności od zawartości zestawu i wzorców używanych przez twój kod w celu uzyskania dostępu do zestawu. Ogólnie rzecz biorąc, zestaw z 5 przedmiotami będzie miał znacznie inną charakterystykę wydajności niż zestaw zawierający 5 miliardów przedmiotów. I tak, może obsłużyć tyle danych. –