Come fare array sparse in Cocoa

Question

Ho una dimensione indeterminata per un set di dati basato su chiavi integer univoche.

Mi piacerebbe utilizzare un NSMutableArray per la ricerca rapida poiché tutte le mie chiavi sono basate su numeri interi.

Voglio farlo.

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

allora la gente più tardi sarà iniziare a gettare i dati a me con gli indici interi (tutti unici), così ho solo voglia di fare qualcosa di simile ...

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

e hanno la matrice ridimensionata in modo che io può quindi ...

[data insertObject:obj atIndex:index]; 

con tutti gli slot tra l'ultima dimensione e la nuova dimensione pari a zero che verrà eventualmente completata in seguito.

Quindi la mia domanda è come ridimensionare uno esistente NSMutableArray?

Grazie, romana

Answer 1

che suona come le vostre esigenze sarebbe meglio soddisfatte con una NSMutableDictionary. Avrete bisogno di avvolgere le int s in NSNumber oggetti come segue:

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

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

Non c'è facile era per ingrandire la dimensione di un NSMutableArray, dal momento che non si può avere nil oggetti in-tra gli slot. Tuttavia, è possibile utilizzare [NSNull null] come "riempitivo" per creare l'aspetto di una matrice sparsa.

Answer 2

Utilizzare un NSPointerArray.

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

NSPointerArray è una raccolta mutevole modellato NSArray ma può anche contenere valori NULL, che può essere inserita o estratta (e che contribuiscono al conteggio dell'oggetto). Inoltre, a differenza degli array tradizionali, è possibile impostare direttamente il conteggio dell'array . In un ambiente garbage collection , se si specifica una configurazione di memoria debole con azzeramento , se viene raccolto un elemento , questo viene sostituito da un valore NULL.

Se si dovesse utilizzare un dizionario come soluzione, utilizzare NSMapTable. Permette chiavi intere. La soluzione basata su NSMutableDictionary ha una quantità enorme di spese generali relative a tutto il boxing delle chiavi intere &.

Answer 3

Devo non essere d'accordo con la risposta di bbum su questo. A NSPointerArray è un array, non un array sparse, e ci sono differenze importanti tra i due.

I fortemente consiglia di non utilizzare la soluzione di bbums.

La documentazione per NSPointerArray è disponibile here.

Cocoa ha già un oggetto array come definito dalla classe NSArray. NSPointerArray eredita da NSObject, quindi non è una sottoclasse diretta di NSArray. Tuttavia, la documentazione NSPointerArray definisce la classe in quanto tale:

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

io farò il presupposto assiomatico che questa definizione dalla documentazione afferma che si tratta di una sottoclasse "logica" di NSArray.

definizioni di

Una matrice "generale" è: un insieme di elementi, ciascuno dei quali ha un numero di indice univoco associato con esso.

Un array, senza qualifiche, è: Una matrice "generale" in cui gli indici degli articoli hanno le seguenti proprietà: Gli indici per gli articoli nell'array iniziano da 0 e aumentano in sequenza. Tutti gli elementi nell'array contengono un numero di indice inferiore al numero di elementi nell'array. L'aggiunta di un elemento a un array deve essere nell'indice + 1 dell'ultimo elemento dell'array, oppure è possibile inserire un elemento tra due numeri di indice di articoli esistenti, il che fa incrementare di uno il numero indice di tutti gli articoli successivi. Un articolo a un numero di indice esistente può essere sostituito da un altro elemento e questa operazione non modifica i numeri di indice delle operazioni esistenti. Pertanto, inserire e sostituire sono due operazioni distinte.

Un array sparse è un array "generale" in cui il numero indice del primo elemento può iniziare con qualsiasi numero e il numero di indice degli elementi successivi aggiunti all'array non ha alcuna relazione o restrizioni in base ad altri elementi nel array. L'inserimento di un elemento in un array sparse non influisce sul numero di indice di altri elementi dell'array. L'inserimento di un articolo e la sostituzione di un articolo sono generalmente anche nella maggior parte delle implementazioni. Il conteggio del numero di elementi nell'array sparse non ha alcuna relazione con i numeri di indice degli elementi nell'array sparse.

Queste definizioni rendono alcune previsioni sul comportamento di una matrice "scatola nera" verificabile. Per semplicità, ci concentreremo sulla seguente relazione:

In un array, il numero di indice di tutti gli elementi nell'array è inferiore al numero del numero di elementi nell'array. Anche se questo può essere vero per un array sparse, non è un requisito.

In un commento a bbum, mi ha dichiarato quanto segue:

un NSPointerArray non è una matrice sparsa, né si comportano come uno. Devi ancora riempire tutti gli indici inutilizzati con i puntatori NULL. Uscita da [pointerArray insertPointer:@"test" atIndex:17]; su un fresco un'istanza NSPointerArray:

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

Si afferma, senza dimostrare, il comportamento dei NSPointerArray sopra viola la definizione stessa di una matrice sparsa. Questa parte del messaggio di errore è indicativa: attempt to insert pointer at index 17 beyond bounds 0', in particolare la parte relativa alla necessità di aggiungere il primo elemento nuovo all'indice 0.

bbum commenta quindi:

Questo non è corretto. Non è riuscito a chiamare -setCount: per impostare la capacità su una dimensione sufficiente.

È non sensical a "impostare il conteggio" del numero di elementi in una matrice sparsa. Se NSPointerArray era un array sparse, ci si aspetterebbe che dopo aver aggiunto il primo elemento all'indice 17, il conteggio del numero di elementi nello NSPointerArray sia uno. Tuttavia, seguendo il consiglio di bbums, il numero di articoli nel numero NSPointerArray dopo aver aggiunto i primi articoli è 18, non 1.

QED- Viene mostrato che uno NSPointerArray è in realtà un array e ai fini di questa discussione, uno NSArray.

Inoltre, bbum fa le seguenti ulteriori osservazioni:

NSPointerArray fa certamente fori di supporto.

Questo è probabilmente falso. Un array richiede che tutti gli elementi in esso contenuti contengano qualcosa, anche se quel qualcosa è "nulla". Questo non è vero per un array sparse. Questa è la definizione stessa di "buco" ai fini di questa discussione. A NSPointerArray non contiene holes nel senso sparse dell'array del termine.

Questo era uno dei punti principali della scrittura della classe. Devi prima impostare il conteggio.

È probabilmente non sensato "impostare il conteggio" di una matrice sparsa.

Se l'implementazione interna è un array sparse o un hash o, ecc, è un dettaglio di implementazione.

Questo è vero. Tuttavia, la documentazione per NSPointerArray non fa alcun riferimento a come implementa o gestisce la sua matrice di elementi. Inoltre, non dichiara da nessuna parte che un NSPointerArray "gestisce in modo efficiente una serie di puntatori NULL."

QED- bbum dipende dal comportamento irregolare che un NSPointerArray gestisce efficientemente NULL puntatori tramite una matrice sparsa internamente. Essendo comportamento non documentato, questo comportamento può cambiare in qualsiasi momento o non essere applicabile a tutti gli usi di NSPointerArray. Un cambiamento in questo comportamento sarebbe catastrofico se il numero di indice più elevato memorizzato in esso è sufficientemente grande (~ 2^26).

E, in effetti, non è implementato come un grosso pezzo di memoria ...

Ancora una volta, questo è un privato dettaglio di implementazione che è non documentata. È estremamente pratica di programmazione scadente a dipendere da questo tipo di comportamento.

Answer 4

Come nella risposta di Jason, un NSMutableDictionary sembra essere l'approccio migliore. Aggiunge il sovraccarico di convertire i valori dell'indice in e da NSNumbers, ma questo è un classico scambio spazio/tempo.

Nella mia implementazione ho incluso anche un NSIndexSet per rendere molto più semplice l'attraversamento dell'array sparse.

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