[NSArray containsObject:] vs [NSSet containsObject:]

Dzisiejszy post nie jest wyłącznie związany z Objective-C i iOS. Chcę jedynie zwrócić uwagę na pewien drobny szczegół w pisaniu aplikacji. Szczegół, który łatwo przeoczyć i zrobić coś bardzo nieefektywnie.

Sam miałem możliwość poprawienia czegoś takiego w jednym z projektów jakiś czas temu.  Dziś przyszła pora na podzielenie się tym i zwrócenie uwagi na myślenie. To ważne.

Załóżmy, że mamy do przeszukania i do znalezienia 1 unikalny rekord ze zbioru około 70 tysięcy 25 znakowych łańcuchów znaków.  Jak to zrobić? Opcji jest sporo. Dziś pokażę różnicę w 2 różnych podejściach używając gotowych metod containsObject z kolekcji NSArray i NSSet. Kolekcje bardzo często używane w wielu aplikacjach mobilnych.

Na początek pytanie: Czym różnią się te 2 kolekcje i dlaczego containsObject działa w nich inaczej?

Rzućmy okiem na obrazek z dokumentacji Apple:

NSArray trzyma dane w sposób uporządkowany, każdy element ma swój indeks. NSSet to kolekcja w której elementy nie mają swojej kolejności (indeksu) ani nie jest uporządkowana.

Teraz pora na containsObject. Proste sprawdzenie czy dany obiekt (w naszym przypadku po prostu łańcuch znaków – NSString*) jest elementem danej kolekcji. Niby nic, a jednak. Popatrzcie na te pomiary dla 100 wyszukań 25 znakowych tekstów w zbiorze 68496 elementów:

2016-01-11 01:11:59.664 TestStringComparisonTime[90970:26783381] Case 1
2016-01-11 01:11:59.911 TestStringComparisonTime[90970:26783381] arrayContainsInStringTest execution time: 0.246980
2016-01-11 01:11:59.911 TestStringComparisonTime[90970:26783381] ----------------------------
2016-01-11 01:11:59.911 TestStringComparisonTime[90970:26783381] Case 2
2016-01-11 01:11:59.912 TestStringComparisonTime[90970:26783381] setContainsInStringTest execution time: 0.000064

4 tysiące razy szybciej….

Taki benefit tylko i wyłącznie dzięki temu, że można użyć innej kolekcji. W NSArray iOS musi przeiterować się przez tablicę aż do znalezienia elementu lub aż do jej końca, aby stwierdzić, że takiego elementu w niej nie ma. W NSSet, wyliczany jest hash z danego elementu i sprawdzane jest czy pod danych hashem  jest już zapisany jakiś obiekt. O(n) vs O(1).

Przykładowy projekt z danymi testowymi można znaleźć tutaj. Zapraszam do eksperymentów.

Bądźcie uważni i myślcie na każdym kroku.


 

I na koniec: jeśli ciekawy Cię temat wydajności, to polecam jeszcze inny krótki wpis pokazujący jak można zoptymalizować przeszukanie NSArray używając 4 różnych metod.

Dodaj komentarz