Wie spare Array in Cocoa zu tun

8

Ich habe eine unbestimmte Größe für ein Dataset basierend auf eindeutigen Ganzzahlschlüsseln.

Ich würde gerne eine NSMutableArray für schnelle Suche verwenden, da alle meine Schlüssel integer sind.

Ich möchte das tun.

%Vor%

später werden Leute anfangen, Daten mit ganzzahligen Indizes (alle einzigartig) zu werfen, also möchte ich einfach so etwas machen ...

%Vor%

und habe die Größe des Arrays so geändert, dass ich es dann tun kann ...

%Vor%

wobei alle Slots zwischen der letzten Größe und der neuen Größe Null sind, die später eventuell ausgefüllt werden.

Also meine Frage ist, wie ändere ich eine bestehende NSMutableArray ?

Danke, Römisch

    
Alex Rozanski 30.08.2009, 21:34
quelle

4 Antworten

17

Es klingt, als wären Ihre Bedürfnisse besser mit einem NSMutableDictionary erfüllt. Sie müssen die int s wie folgt in NSNumber -Objekte einschließen:

%Vor%

Es ist nicht einfach, die Größe von NSMutableArray zu vergrößern, da Sie keine Objekte in den Zwischenslots haben können. Sie können jedoch [NSNull null] als 'Füller' verwenden, um das Aussehen eines Sparse-Arrays zu erzeugen.

    
Jason 30.08.2009, 21:39
quelle
33

Verwenden Sie ein NSPointerArray.

Ссылка

  

NSPointerArray ist eine veränderbare Auflistung   nach NSArray modelliert, kann es aber auch   Halten Sie NULL-Werte, die sein können   eingefügt oder extrahiert (und das   zur Zählung des Objekts beitragen).   Im Gegensatz zu traditionellen Arrays,   Sie können die Anzahl der Arrays festlegen   direkt. In einem Müll gesammelt   Umgebung, wenn Sie eine Nullsetzung angeben   schwache Speicherkonfiguration, wenn ein   Element wird gesammelt, es wird durch ersetzt   ein NULL-Wert.

Wenn Sie eine wörterbuchähnliche Lösung verwenden möchten, verwenden Sie NSMapTable. Es erlaubt Integer-Schlüssel. Die NSMutableDictionary-basierte Lösung hat eine enorme Menge an Overhead im Zusammenhang mit all dem Boxen & amp; Unboxing von Ganzzahlschlüsseln.

    
bbum 31.08.2009 15:02
quelle
1

Wie in Jasons Antwort scheint ein NSMutableDictionary der beste Ansatz zu sein. Es fügt den Overhead der Konvertierung der Indexwerte zu und von NSNumbers hinzu, aber dies ist ein klassisches Zeit / Raum-Kompromiss.

In meiner Implementierung habe ich auch einen NSIndexSet eingefügt, um das trarse Array viel einfacher zu machen.

Siehe Ссылка

    
LavaSlider 26.05.2014 17:38
quelle
-4

Ich muss der Antwort von bbum hier widersprechen. A NSPointerArray ist ein Array, kein Sparse-Array, und es gibt wichtige Unterschiede zwischen den beiden.

Ich stark empfehle, dass die Bbums-Lösung nicht verwendet wird.

Die Dokumentation für NSPointerArray ist hier verfügbar .

Cocoa hat bereits ein Array-Objekt, wie es in der Klasse NSArray definiert ist. NSPointerArray erbt von NSObject , also ist es keine direkte Unterklasse von NSArray . Die Dokumentation NSPointerArray definiert jedoch die Klasse als solche:

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

Ich werde die axiomatische Annahme machen, dass diese Definition aus der Dokumentation behauptet, dass dies eine "logische" Unterklasse von NSArray ist.

Definitionen -

Ein "allgemeines" Array ist: eine Sammlung von Elementen, denen jeweils eine eindeutige Indexnummer zugeordnet ist.

Ein Array ohne Qualifikationen ist: Ein "allgemeines" Array, in dem die Indizes der Elemente die folgenden Eigenschaften haben: Indizes für Elemente im Array beginnen bei 0 und erhöhen sich sequenziell. Alle Elemente im Array enthalten eine Indexnummer, die kleiner als die Anzahl der Elemente im Array ist. Das Hinzufügen eines Elements zu einem Array muss bei Index + 1 des letzten Elements im Array erfolgen, oder ein Element kann zwischen zwei vorhandenen Elementindexnummern eingefügt werden, wodurch die Indexnummer aller nachfolgenden Elemente um eins erhöht wird. Ein Element an einer vorhandenen Indexnummer kann durch ein anderes Element ersetzt werden, und diese Operation ändert nicht die Indexnummern der vorhandenen Operationen. Daher sind Einfügen und Ersetzen zwei verschiedene Vorgänge.

Ein Sparse-Array ist: Ein "allgemeines" Array, in dem die Indexnummer des ersten Elements an einer beliebigen Nummer beginnen kann und die Indexnummer der nachfolgenden Elemente, die dem Array hinzugefügt wurden, keine Beziehung zu oder Einschränkungen aufgrund anderer Elemente im Array hat . Das Einfügen eines Elements in ein Array mit geringer Speicherdichte wirkt sich nicht auf die Indexnummer anderer Elemente im Array aus. Das Einfügen eines Elements und das Ersetzen eines Elements sind in den meisten Implementierungen typisch synonym. Die Anzahl der Elemente im Array spärlich hat keine Beziehung zu den Indexnummern der Elemente im Array spärlich.

Diese Definitionen machen bestimmte Vorhersagen über das Verhalten eines "Black Box" -Arrays, die testbar sind. Der Einfachheit halber konzentrieren wir uns auf die folgende Beziehung:

In einem Array ist die Indexnummer aller Elemente im Array kleiner als die Anzahl der Elemente im Array. Dies trifft zwar auf eine spärliche Array zu, ist jedoch keine Voraussetzung.

In einem Kommentar zu bbum habe ich folgendes gesagt:

  

a NSPointerArray ist kein Sparse-Array und verhält sich auch nicht wie eins. Sie müssen weiterhin alle nicht verwendeten Indizes mit NULL -Zeigern füllen. Ausgabe von [pointerArray insertPointer:@"test" atIndex:17]; auf einem frisch instanziierten NSPointerArray :

     

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

Es wird gesagt, ohne zu beweisen, dass das Verhalten von NSPointerArray oben genau die Definition eines Sparse-Arrays verletzt. Dieser Teil der Fehlermeldung ist aufschlussreich: attempt to insert pointer at index 17 beyond bounds 0' , insbesondere der Teil über das Hinzufügen des ersten neuen Elements am Index 0 .

bbum dann Kommentare:

  

Das ist falsch. Sie haben -setCount nicht aufgerufen: um die Kapazität auf eine ausreichende Größe zu setzen.

Es ist nicht-sensibel , die Anzahl der Elemente in einem Array mit geringer Dichte festzulegen. Wenn NSPointerArray ein Sparse-Array wäre, würde man erwarten, dass nach dem Hinzufügen des ersten Elements bei Index 17 die Anzahl der Elemente in NSPointerArray Eins wäre. Nach dem Bbum-Hinweis ist die Anzahl der Elemente in NSPointerArray nach dem Hinzufügen der ersten Elemente jedoch 18 , nicht 1 .

QED- Es wird gezeigt, dass ein NSPointerArray tatsächlich ein Array ist und für die Zwecke dieser Diskussion ein NSArray .

Zusätzlich macht bbum folgende zusätzliche Kommentare:

  

NSPointerArray unterstützt sicherlich Löcher.

Dies ist nachweislich falsch. Ein Array erfordert, dass alle darin enthaltenen Elemente etwas enthalten, auch wenn das etwas "nichts" ist. Dies gilt nicht für ein Sparse-Array. Dies ist die Definition eines "Lochs" für die Zwecke dieser Diskussion. A NSPointerArray enthält nicht holes in der Sparse-Array-Bedeutung des Begriffs.

  

Das war einer der Hauptpunkte beim Schreiben der Klasse. Sie müssen zuerst die Anzahl einstellen.

Es ist nachweislich sinnlos, "die Anzahl" eines Sparse-Arrays festzulegen.

  

Ob die interne Implementierung ein Sparse-Array oder ein Hash oder usw. ist, ist ein Implementierungsdetail.

Das ist wahr. In der Dokumentation für NSPointerArray wird jedoch nicht darauf Bezug genommen, wie das Array von Elementen implementiert oder verwaltet wird. Außerdem gibt es nirgends an, dass ein NSPointerArray "effizient ein Array von NULL-Zeigern verwaltet."

QED-bbum ist abhängig vom undokumentierten Verhalten , dass ein NSPointerArray effizient NULL Zeiger über ein Sparse Array intern handhabt. Da undokumentiertes Verhalten ist, kann sich dieses Verhalten jederzeit ändern oder möglicherweise nicht für alle Verwendungen von NSPointerArray . Eine Änderung in diesem Verhalten wäre katastrophal , wenn die höchste darin gespeicherte Indexnummer ausreichend groß ist (~ 2 ^ 26).

  

Und tatsächlich, es ist nicht als ein großes Stück Speicher implementiert ...

Auch dies ist ein privates Implementierungsdetail, das undokumentiert ist. Es ist extrem schlechte Programmierpraxis, von dieser Art von Verhalten abhängig zu sein.

    
johne 03.09.2009 23:56
quelle