objective-c - initialize - objective c new array

¿Cuál es la estructura de datos detrás de NSMutableArray?

Question

Por lo general, una clase de "matriz mutable" se implementa como un contenedor alrededor de una matriz simple. El contenedor asigna más memoria cuando agrega un elemento más allá del final. Esta es una estructura de datos común y el rendimiento de las diversas operaciones es bien conocido. Obtiene O (1) elemento de acceso, O (N) insertar y eliminar, o O (1) (en promedio) insertar y eliminar al final de la matriz. Pero NSMutableArray es otra cosa. Por ejemplo, los docs dicen [énfasis mío]:

Nota: la mayoría de las operaciones en una matriz toman tiempo constante : acceder a un elemento, agregar o eliminar un elemento en cada extremo y reemplazar un elemento. Insertar un elemento en el medio de una matriz toma tiempo lineal.

Entonces, ¿qué es exactamente NSMutableArray ? ¿Está esto documentado en alguna parte?

Answer 1

Es una envoltura alrededor de un buffer circular .

Esto no está documentado ni es de código abierto, pero esta publicación de blog muestra un increíble trabajo de ingeniería inversa en NSMutableArray , que creo que encontrará muy interesante.

El NSMutableArray clase NSMutableArray está respaldado por una subclase privada concreta llamada __NSArrayM .

El mayor descubrimiento es que NSMutableArray no es una envoltura delgada alrededor de un CFArray , como uno puede pensar razonablemente: CFArray es de código abierto y no usa un búfer circular, mientras que __NSArrayM sí __NSArrayM hace.

Al leer los comentarios del artículo, parece que comenzó a ser así desde iOS 4, mientras que en los SDK anteriores, NSMutableArray realidad usaba CFArray internamente y __NSArrayM ni siquiera estaba allí.

Directamente de la entrada del blog que mencioné anteriormente.

Estructura de datos

Como habrá adivinado, __NSArrayM utiliza un búfer circular. Esta estructura de datos es extremadamente simple, pero un poco más sofisticada que la matriz / buffer regular. El contenido del búfer circular puede envolverse cuando se alcanza cualquiera de los extremos.

El tampón circular tiene algunas propiedades muy interesantes. Notablemente, a menos que el búfer esté lleno, la inserción / eliminación desde cualquier extremo no requiere que se mueva ninguna memoria.

El pseudocódigo para objectAtIndex: es el siguiente:

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

donde los ivars se definen como

• _used : el número de elementos que contiene la matriz
• _list : el puntero al buffer circular
• _size : el tamaño del búfer
• _offset : el índice del primer elemento de la matriz en el búfer

Nuevamente, no tomo ningún crédito por toda la información anterior, ya que vienen directamente de esta increíble publicación de blog de Bartosz Ciechanowski .

Answer 2

Hice algunas mediciones: Comenzando con una matriz vacía, agregó @ "Hola" 100.000 veces y luego la eliminó 100.000 veces. Diferentes patrones: agregar / eliminar al final, al inicio, en el medio, cerca del inicio (en el índice 20 cuando sea posible), cerca del final (20 índices lejos del final cuando sea posible), y uno donde alterné Entre cerca del inicio y del final. Aquí están los tiempos para 100,000 objetos (medidos en 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

Por lo tanto, el tiempo para cada adición / eliminación es proporcional a la distancia al principio o al final de la matriz, lo que esté más cerca. Añadir cosas en el medio es caro. No tienes que trabajar exactamente al final; Eliminar elementos cerca del inicio / final también es bastante barato.

La implementación sugerida como una lista circular omite un detalle importante: hay un espacio de tamaño variable entre la ubicación del último y el primer elemento de la matriz. A medida que se agregan / eliminan elementos de la matriz, el tamaño de ese espacio cambia. Se necesita asignar más memoria y los punteros a objetos deben moverse cuando la brecha desaparece y se agregan más objetos; la matriz se puede contraer y los punteros de los objetos deben moverse cuando el espacio es demasiado grande. Un cambio simple (que permita que la separación se ubique en cualquier ubicación, no solo entre el último y el primer elemento) permitiría que los cambios en cualquier ubicación sean rápidos (siempre que sea la misma ubicación), y realizaría operaciones que se "aclaran "la matriz más rápida.