Cómo hacer una matriz dispersa en Cocoa

Question

Tengo un tamaño indeterminado para un conjunto de datos basado en claves enteras únicas.

Me gustaría utilizar un NSMutableArray para una búsqueda rápida ya que todas mis claves están basadas en un entero.

Quiero hacer esto.

NSMutableArray* data = [NSMutableArray array]; // just create with 0 size 

entonces la gente va a empezar a tirar posteriores datos a mí con índices enteros (todos únicos), así que sólo quieren hacer algo como esto ...

if ([data count] < index) 
    [data resize:index]; // ? how do you resize 

y tienen la matriz cambia de tamaño para que yo entonces puede hacer ...

[data insertObject:obj atIndex:index]; 

con todas las ranuras entre el último tamaño y el nuevo tamaño siendo cero, que eventualmente se completará más tarde.

Así que mi pregunta es ¿cómo puedo cambiar el tamaño de una existente NSMutableArray?

Gracias, romana

Answer 1

Suena como sus necesidades se satisfacen mejor con una NSMutableDictionary. Usted tendrá que envolver los int s en NSNumber objetos de la siguiente manera:

-(void)addItem:(int)key value:(id)obj 
{ 
    [data setObject:obj forKey:[NSNumber numberWithInt:key]]; 
} 

-(id)getItem:(int)key 
{ 
    return [data objectForKey:[NSNumber numberWithInt:key]]; 
} 

no hay fácil fue para agrandar el tamaño de un NSMutableArray, ya que no se puede tener cero objetos en el entre las ranuras. Sin embargo, puede usar [NSNull null] como 'relleno' para crear la apariencia de una matriz dispersa.

Answer 2

Utilice un NSPointerArray.

http://developer.apple.com/mac/library/documentation/Cocoa/Reference/Foundation/Classes/NSPointerArray_Class/Introduction/Introduction.html

NSPointerArray es una colección mutable modelado después NSArray pero también puede contener valores NULL, que pueden ser inserta o extrae (y que contribuyen a la cuenta del objeto). Además, a diferencia de las matrices tradicionales, , puede establecer el recuento de la matriz directamente. En un entorno recogido de basura , si especifica una configuración de memoria débil , si se recopila un elemento se reemplaza por un valor NULO.

Si tuviera que utilizar una solución con un diccionario, utilice NSMapTable. Permite claves enteras. La solución basada en NSMutableDictionary recomendada tiene una tremenda cantidad de sobrecarga relacionada con el boxeo & unboxing de claves enteras.

Answer 3

Tengo que estar en desacuerdo con la respuesta de bbum sobre esto. Un NSPointerArray es una matriz, no una matriz dispersa, y existen diferencias importantes entre las dos.

I fuertemente recomiendan que la solución bbums no se use.

La documentación para NSPointerArray está disponible here.

Cocoa ya tiene un objeto de matriz como se define en la clase NSArray. NSPointerArray hereda de NSObject, por lo que no es una subclase directa de NSArray. Sin embargo, la documentación NSPointerArray define la clase como tal:

NSPointerArray is a mutable collection modeled after NSArray but it can also hold NULL values

que hará que el supuesto axiomático que esta definición de la documentación afirma que esta es una subclase "lógica" de NSArray.

Definiciones-

Una matriz "general" es: una colección de elementos, cada uno de los cuales tiene un número de índice único asociado con él.

Una matriz, sin reservas, es: Una matriz "general" donde los índices de los elementos tienen las siguientes propiedades: Los índices de los elementos en la matriz comienzan en 0 y aumentan secuencialmente. Todos los elementos en la matriz contienen un número de índice menor que el número de elementos en la matriz. Agregar un elemento a una matriz debe estar en el índice + 1 del último elemento de la matriz o un elemento se puede insertar entre dos números de índice de elementos existentes, lo que hace que el número de índice de todos los elementos subsecuentes se incremente en uno. Un artículo en un número de índice existente puede ser reemplazado por otro artículo y esta operación no cambia los números de índice de las operaciones existentes. Por lo tanto, insertar y reemplazar son dos operaciones distintas.

Una matriz dispersa es: una matriz "general" donde el número de índice del primer elemento puede comenzar en cualquier número y el número índice de elementos posteriores agregados a la matriz no tiene relación o restricciones basadas en otros elementos en el formación. Insertar un elemento en una matriz dispersa no afecta el número de índice de otros elementos en la matriz. Insertar un elemento y reemplazar un artículo son, por lo general, sinónimos en la mayoría de las implementaciones. El recuento de la cantidad de elementos en la matriz dispersa no tiene relación con los números de índice de los elementos en la matriz dispersa.

Estas definiciones hacen que ciertas predicciones sobre el comportamiento de una matriz de "caja negra" sean comprobables. Para simplificar, nos centraremos en la siguiente relación:

En una matriz, el número de índice de todos los elementos de la matriz es menor que el recuento de la cantidad de elementos en la matriz. Si bien esto puede ser cierto para una matriz dispersa, no es un requisito.

En un comentario a bbum, que declaró lo siguiente:

un NSPointerArray no es una matriz dispersa, ni se comporta como tal. Aún debe completar todos los índices sin usar con NULL punteros. La salida de [pointerArray insertPointer:@"test" atIndex:17]; en un recién instanciado NSPointerArray:

*** Terminating app due to uncaught exception 'NSInvalidArgumentException', reason: '*** -[NSConcretePointerArray insertPointer:atIndex:]: attempt to insert pointer at index 17 beyond bounds 0'

Se afirma, sin probar, el comportamiento de NSPointerArray sentencia vulnera la propia definición de una matriz dispersa. Esta parte del mensaje de error es reveladora: attempt to insert pointer at index 17 beyond bounds 0', en particular la parte de tener que agregar el primer elemento nuevo en el índice 0.

bbum luego comenta:

Eso es incorrecto. Error al llamar a -setCount: para establecer la capacidad a un tamaño suficiente.

Es sin sentido a "establecer el recuento" del número de elementos de una matriz dispersa. Si NSPointerArray fuera una matriz dispersa, cabría esperar que, después de agregar el primer elemento en el índice 17, el recuento de la cantidad de elementos en el NSPointerArray sería uno. Sin embargo, siguiendo el consejo de bbums, el número de elementos en el NSPointerArray después de agregar los primeros artículos es 18, no 1.

QED- Se muestra que un NSPointerArray es de hecho una matriz, y para los fines de esta discusión, un NSArray.

Además, bbum hace las siguientes observaciones adicionales:

NSPointerArray sin duda hace agujeros de soporte.

Esto es provablemente falso. Una matriz requiere que todos los elementos que contiene contengan algo, incluso si ese algo es 'nada'. Esto no es cierto para una matriz dispersa. Esta es la definición misma de 'hoyo' para los propósitos de esta discusión. Un NSPointerArray no contiene holes en el sentido de matriz dispersa del término.

Ese fue uno de los puntos principales de la clase. Tienes que establecer el conteo primero.

Probablemente no sensitivo "establecer el recuento" de una matriz dispersa.

Si la implementación interna es una matriz dispersa o un hash o, etc., es un detalle de implementación.

Esto es cierto. Sin embargo, la documentación para NSPointerArray no hace ninguna referencia a cómo implementa o administra su conjunto de elementos. Además, no dice en ningún lugar que un NSPointerArray "administra de manera eficiente una matriz de punteros NULL".

QED- bbum está en función del comportamiento no documentado que un NSPointerArray gestiona de manera eficaz NULL punteros a través de una matriz dispersa internamente. Al ser comportamiento no documentado, este comportamiento puede cambiar en cualquier momento o incluso puede no aplicarse a todos los usos del NSPointerArray. Un cambio en este comportamiento sería catastrófico si el número de índice más alto almacenado en él es suficientemente grande (~ 2^26).

Y, de hecho, no está implementado como un gran trozo de memoria ...

Una vez más, este es un privada detalle de implementación que es indocumentado . Es extremadamente pobre práctica de programación para depender de este tipo de comportamiento.

Answer 4

Como en la respuesta de Jason, un NSMutableDictionary parece ser el mejor enfoque. Agrega la sobrecarga de convertir los valores de índice a NSNumbers y viceversa, pero este es un intercambio de espacio/tiempo clásico.

En mi implementación también incluí un NSIndexSet para hacer que recorrer la matriz dispersa sea mucho más simple.

Ver https://github.com/LavaSlider/DSSparseArray