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

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?

Спасибо, Roman

Answer 1

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

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

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

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

Answer 2

Звучит так, как будто ваши потребности будут лучше удовлетворены NSMutableDictionary. Вам нужно будет обернуть int s в 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 3

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

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

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

Answer 4

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

I настоятельно рекомендую не использовать раствор bbums.

Документация для NSPointerArray доступна здесь .

Какао уже имеет объект массива, определенный классом 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 я сказал следующее:

a 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 наверняка поддерживает дыры.

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

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

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

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

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

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

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

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