Как сделать разреженный массив в Cocoa

Question

У меня есть неопределенный размер для набора данных на основе уникальных целых ключей.

Я бы хотел использовать NSMutableArray для быстрого поиска, так как все мои ключи основаны на целых числах.

Я хочу это сделать.

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

потом люди начнут бросать данные у меня с целыми индексами (уникальными), так что я просто хочу, чтобы сделать что-то вроде этого ...

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

и есть массив изменен так, что я то можно сделать ...

[data insertObject:obj atIndex:index]; 

со всеми слотами между последним размером и нового размером равен нулем, которые в конечном итоге будут заполнены позже.

Итак, мой вопрос заключается в том, как изменить размер существующего NSMutableArray?

Спасибо, Роман

Answer 1

Похоже, ваши потребности будут лучше встречались с NSMutableDictionary. Вам нужно будет обернуть int сек в NSNumber объектов следующим образом:

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

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

Там нет просто не было, чтобы увеличить размер в NSMutableArray, так как вы не можете иметь ноль объектов в промежутке между пазами. Однако вы можете использовать [NSNull null] как «наполнитель», чтобы создать видимость разреженного массива.

Answer 2

Используйте NSPointerArray.

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

NSPointerArray является изменяемым коллекция по образцу NSArray, но он также может удерживать NULL значения, которые могут быть вставлены или экстрагируют (и которые способствуют графа объекта). Кроме того, в отличие от традиционных массивов, вы можете установить счетчик массива напрямую. В сборке мусора, собранной , если вы указали нулевую конфигурацию слабой памяти, если элемент собран, он заменяется на значением NULL.

Если вы хотите использовать словарь, например, решение, используйте NSMapTable. Он позволяет использовать целые ключи. Рекомендуемое решение, основанное на NSMutableDictionary, имеет огромное количество накладных расходов, связанных со всеми боксами & распаковкой целых ключей.

Answer 3

Я должен не согласиться с ответом на bbum. A NSPointerArray - это массив, а не разреженный массив, и между ними существуют важные различия.

I настоятельно рекомендовать, чтобы решение bbums не использовалось.

Имеется документация для NSPointerArrayhere.

Какао уже имеет объект массива, определенный классом NSArray. NSPointerArray наследует от NSObject, поэтому он не является прямым подклассом NSArray. Однако документация NSPointerArray определяет класс как таковые:

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

Я сделаю аксиоматическое предположение, что это определение из документации утверждает, что это «логический» подкласс NSArray.

Definitions-

А «общий» массив: коллекция элементов, каждый из которых имеет уникальный номер индекса, связанный с ним.

Массив без квалификаций представляет собой: «Общий» массив, в котором индексы элементов имеют следующие свойства: Индексы для элементов в массиве начинаются с 0 и увеличиваются последовательно. Все элементы массива содержат номер индекса меньше, чем количество элементов в массиве. Добавление элемента в массив должно быть в индексе + 1 последнего элемента в массиве, или элемент может быть вставлен между двумя существующими номерами индексов элементов, что приводит к тому, что индексный индекс всех последующих элементов будет увеличен на единицу. Элемент с существующим номером индекса может быть заменен другим элементом, и эта операция не изменяет номера индексов существующих операций. Поэтому вставка и замена - это две различные операции.

Редкий массив: «общий» массив, где номер индекса первого элемента может начинаться с любого числа, а номер индекса последующих элементов, добавленных в массив, не имеет никакого отношения к или ограничениям на основе других элементов в массив. Вставка элемента в разреженный массив не влияет на число индексов других элементов в массиве. Вставка элемента и замена элемента обычно являются синонимами в большинстве реализаций. Количество элементов в разреженном массиве не имеет отношения к номерам индексов элементов в разреженном массиве.

Эти определения содержат определенные прогнозы о поведении массива «черного ящика», которые можно тестировать. Для простоты мы сосредоточимся на следующем соотношении:

В массиве индексный индекс всех элементов массива меньше, чем количество элементов в массиве. Хотя это может быть справедливо для разреженного массива, это не является обязательным требованием.

В комментарии к bbum, я заявил следующее:

NSPointerArray не разреженный массив, и не ведут себя, как один. Вам все равно придется заполнять все неиспользуемые индексы указателями NULL. Выход из [pointerArray insertPointer:@"test" atIndex:17]; на свеже экземпляр NSPointerArray:

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

Он заявил, что не доказывает, то поведение NSPointerArray выше нарушает само определение разреженного массива. Эта часть сообщения об ошибке раскрывает: attempt to insert pointer at index 17 beyond bounds 0', в частности, часть о том, что нужно добавить первый новый элемент по индексу 0.

bbum затем комментарии:

Это неправильно. Вы не смогли вызвать -setCount: чтобы установить емкость достаточного размера.

Это без бы бессмысленно «установить счетчик» числа элементов в разреженном массиве. Если NSPointerArray был разреженным массивом, можно было бы ожидать, что после добавления первого элемента в индекс 17 подсчет количества элементов в NSPointerArray будет одним. Тем не менее, после консультации с bbums, количество предметов в NSPointerArray после добавления первых позиций составляет 18, а не 1.

QED- Показано, что NSPointerArray представляет собой массив, и для целей этой дискуссии - NSArray.

Кроме того, bbum делает следующие дополнительные комментарии:

NSPointerArray безусловно, делает поддержку отверстий.

Это доказуемо неверно. Массив требует, чтобы все содержащиеся в нем элементы содержали что-то, даже если это что-то «ничего». Это не относится к разреженному массиву. Это само определение «дыры» для целей этого обсуждения. A NSPointerArray не содержит holes в разреженном смысле этого термина.

Это была одна из целей написания класса. Сначала нужно установить счет.

Неверно, чтобы «установить счет» разреженного массива.

Является ли внутренняя реализация разреженным массивом или хешем или, и т. Д., Является деталью реализации.

Это правда. Однако документация для NSPointerArray не содержит ссылок на то, как она реализует или управляет массивом элементов. Более того, он не указывает нигде, что NSPointerArray «эффективно управляет массивом NULL-указателей».

QED- bbum зависит от незарегистрированного поведения что NSPointerArray эффективно обрабатывает NULL указателей через разреженный массив внутри. Будучи недокументированным поведением, это поведение может измениться в любое время или может даже не применяться ко всем видам использования NSPointerArray. Изменение этого поведения было бы катастрофическим, если наивысший индекс в нем достаточно большой (~ 2^26).

И, по сути, он не реализован как один большой кусок памяти ...

Опять же, это частного детали реализации, что является недокументированными. Это чрезвычайно Плохая практика программирования зависит от этого типа поведения.

Answer 4

Как и в ответе Джейсона, наилучшим подходом является NSMutableDictionary. Он добавляет накладные расходы на преобразование значений индекса в NSNumbers и из него, но это классический компромисс между пространством и временем.

В моей реализации я также включил NSIndexSet, чтобы сделать пересечение разреженного массива намного проще.

См. https://github.com/LavaSlider/DSSparseArray