Ответ 1

Это оболочка вокруг круговой буфер.

Это не документировано и не открыто, но это сообщение в блоге показывает удивительную работу ревертора над NSMutableArray, что я думаю вы найдете очень интересным.

Класс кластера NSMutableArray поддерживается конкретным частным подклассом __NSArrayM.

Самое большое открытие состоит в том, что NSMutableArray не является тонкой оболочкой вокруг CFArray, как можно разумно думать: CFArray является открытым исходным кодом и не использует круговой буфер, тогда как __NSArrayM делает.

Прочитав комментарии к статье, похоже, что это началось с iOS 4, тогда как в предыдущих SDK NSMutableArray фактически использовался CFArray внутри, а __NSArrayM даже не был.

Прямо из сообщения в блоге, о котором я говорил выше

Структура данных

Как вы могли догадаться, __NSArrayM использует круговой буфер. Эта структура данных чрезвычайно проста, но немного больше сложный, чем обычный массив/буфер. Содержание циркулярных буфер может обернуться, когда достигнут любой конец.

Циклический буфер имеет некоторые очень классные свойства. В частности, если буфер заполнен, вставка/удаление с любого конца не требует каких-либо памяти для перемещения.

Псевдокод для objectAtIndex: выглядит следующим образом:

- (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
}

где ivars определены как

• _used: количество элементов, которые содержит массив
• _list: указатель на круговой буфер
• _size: размер буфера
• _offset: индекс первого элемента массива в буфере

Опять же, я не беру на себя ответственность за всю информацию выше, поскольку они идут прямо из этого замечательного сообщения в блоге Bartosz Ciechanowski.

Ответ 2

Сделал некоторые измерения: начиная с пустого массива, добавив @ "Привет" 100 000 раз, а затем удалил его 100 000 раз. Различные шаблоны: добавление/удаление в конце, в начале, посередине, близко к началу (по показателю 20, когда это возможно), близко к концу (20 индексов от конца, когда это возможно), и один, где я чередовался между близкими к началу и концу. Здесь времена для 100 000 объектов (измеренных на 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

Таким образом, время для каждого добавления/удаления пропорционально расстоянию до начала или конца массива, в зависимости от того, что ближе. Добавление вещей в середине дорого. Вам не нужно работать точно в конце; удаление элементов, близких к началу/концу, также довольно дешево.

Предлагаемая реализация в виде кругового списка исключает важную деталь: существует пустое разность между расположением последнего и первого элемента массива. Когда элементы массива добавляются/удаляются, размер этого пробела изменяется. Необходимо выделить больше памяти, а указатели объектов нужно перемещать, когда пробел исчезает и добавляется больше объектов; массив может быть уменьшен, и указатели объектов необходимо перемещать, когда зазор становится слишком большим. Простое изменение (позволяющее разбить место в любом месте, а не только между последним и первым элементом) позволило бы изменениям в любом месте быть быстрым (при условии, что это одно и то же местоположение) и сделает операции, которые "истощают" "массив быстрее.