Jaka jest struktura danych za NSMutableArray?

Zazwyczaj Klasa" mutable array " jest zaimplementowana jako otoczka wokół prostej tablicy. Opakowanie przydziela więcej pamięci po dodaniu elementu poza końcem. Jest to wspólna struktura danych, a wydajność różnych operacji jest dobrze znana. Dostajesz dostęp do elementu o (1), O(N) insert and remove, lub o (1) (średnio) insert and remove na końcu tablicy. Ale NSMutableArray to coś innego. Na przykład docs powiedz [emfaza]:

Uwaga: większość operacji na tablicy wziąć stały czas: dostęp do elementu, dodawanie lub usuwanie elementu na obu końcach, i wymiana elementu. Wstawianie elementu do środka tablicy zajmuje czas liniowy.

Czym dokładnie jest NSMutableArray? Czy to jest gdzieś udokumentowane?

Author: Rob N, 2014-03-23
Source

2 answers

To owijka wokół okrągłego bufora.

To nie jest ani udokumentowane, ani open-source, ale ten post na blogu pokazuje niesamowitą pracę inżyniera odwrotnego nad NSMutableArray, co myślę, że znajdziesz bardzo interesujące.

Klaster klasy NSMutableArray jest wspierany przez konkretną prywatną podklasę o nazwie __NSArrayM.

Największym odkryciem jest to, że NSMutableArray nie jest cienką owijką wokół CFArray, Jak można rozsądnie sądzić: CFArray jest open-source i nie używa bufor okrągły, natomiast __NSArrayM robi.

Czytając komentarze do artykułu, wydaje się, że zaczęło tak być od iOS 4, podczas gdy w poprzednich SDK NSMutableArray faktycznie używane CFArray wewnętrznie i __NSArrayM nawet tam nie było.

Prosto z blogu, o którym wspomniałem powyżej

Struktura Danych

Jak można się domyślić, __NSArrayM korzysta z okrągłego bufora. Ta struktura danych jest niezwykle prosta, ale trochę więcej wyrafinowane niż zwykła tablica / bufor. Zawartość okólnika bufor może zawijać się po osiągnięciu obu końców.

Okrągły bufor ma bardzo fajne właściwości. W szczególności, chyba że bufor jest pełny, wstawianie/usuwanie z obu końców nie wymaga żadnych pamięć do przeniesienia.

Pseudo-kod dla objectAtIndex: wygląda następująco: 

- (id)objectAtIndex:(NSUInteger)index {
    if (_used <= index) {
        goto ThrowException;
    }

    NSUInteger fetchOffset = _offset + index;
    NSUInteger realOffset = fetchOffset - (_size > fetchOffset ? 0 : _size);

    return _list[realOffset];

ThrowException:
    // exception throwing code
}

Gdzie Ivary są zdefiniowane jako

  • _used: liczba elementów przechowywanych w tablicy
  • _list: the wskaźnik do okrągłego bufora
  • _size: Rozmiar bufora
  • _offset: indeks pierwszego elementu tablicy w buforze

Ponownie nie przypisuję sobie żadnych zasług za wszystkie powyższe informacje, ponieważ pochodzą one prosto z tego niesamowitego wpisu na blogu Bartosza Ciechanowskiego .

 22
Author: Gabriele Petronella,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-03-23 13:41:10

Wykonałem kilka pomiarów: zaczynając od pustej tablicy, dodałem @ "Hello" 100 000 razy, a następnie usunąłem ją 100 000 razy. Różne wzorce: Dodawanie/usuwanie na końcu, na początku, w środku, blisko początku (w indeksie 20, jeśli to możliwe), blisko końca( 20 indeksów od końca, jeśli to możliwe) i jeden, w którym zmieniałem się między blisko początku i końca. Oto czasy dla 100 000 obiektów (mierzone na Core 2 Duo): 

Adding objects = 0.006593 seconds
Removing objects at the end = 0.004674 seconds
Adding objects at the start = 0.003577 seconds
Removing objects at the start = 0.002936 seconds
Adding objects in the middle = 3.057944 seconds
Removing objects in the middle = 3.059942 seconds
Adding objects close to the start = 0.010035 seconds
Removing objects close to the start = 0.007599 seconds
Adding objects close to the end = 0.008005 seconds
Removing objects close to the end = 0.008735 seconds
Adding objects close to the start / end = 0.008795 seconds
Removing objects close to the start / end = 0.008853 seconds

Więc czas każdego dodawania / usuwania jest proporcjonalna odległość do początku lub końca tablicy, w zależności od tego, która jest bliżej. Dodawanie rzeczy w środku jest drogie. Nie musisz pracować Dokładnie na końcu; usuwanie elementów blisko początku / końca jest również dość tanie.

Sugerowana implementacja jako lista okrągła pomija ważny szczegół: istnieje luka o zmiennej wielkości między położeniem ostatniego i pierwszego elementu tablicy. Gdy elementy tablicy są dodawane / usuwane, rozmiar tej szczeliny zmienia się. Więcej pamięć musi być przydzielona i wskaźniki obiektów muszą być przenoszone, gdy luka znika i dodaje się więcej obiektów; tablica może być zmniejszona, a wskaźniki obiektów muszą być przenoszone, gdy luka staje się zbyt duża. Prosta zmiana (pozwalająca na zlokalizowanie luki w dowolnym miejscu, a nie tylko między ostatnim i pierwszym elementem) pozwoliłaby na szybkie zmiany w dowolnym miejscu (o ile jest to ta sama lokalizacja) i przyspieszyłaby operacje, które "rozrzedzają" tablicę.

 1
Author: gnasher729,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-03-23 14:56:52