Быстрый способ хранить и извлекать пары чисел в Objective-C

Question

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

По сути, я создаю массив

m_queue = [NSMutableArray array];

тогда в какой-то момент я заполняю массив

[m_queue addObject:[NSValue valueWithCGPoint:CGPointMake(x + 1, y)]];

затем я получаю данные для следующей итерации и удаляю значение в начале массива

NSValue* value = [m_queue objectAtIndex:0];
[m_queue removeObjectAtIndex:0];
CGPoint nextPoint = [value CGPointValue];

[self queueFloodFill8:nextPoint.x y:nextPoint.y];

Вопрос в том, что можно сделать, чтобы избежать создания большого количества объектов CGPoint и NSValue?

Мне не нужны точки, алгоритм использует пары целочисленных значений, поэтому я думаю, что может быть лучший способ хранить такие пары.

UPDATE: Я посмотрел на реализацию решения в стиле C, например, @mattjgalloway и @CRD.

Я ввел

typedef struct lookup_point_struct
{
    int x;
    int y;
    struct lookup_point_struct* next;
} LookupPoint;

и переписали код для использования связанного списка таких структур вместо NSMutableArray и CGPoint / NSValue.

Все это сделало мой код примерно в 3 раза быстрее. И потребление памяти значительно снизилось.

Answer 1

Не было бы лучшего способа сделать это с помощью Objective-C / Foundation, кроме создания собственного класса, такого как NumberPair или чего-то, что вы помещаете в массив вместо использования NSValue и * 1003. *. Это может быть немного более эффективно для использования памяти, и вы можете сделать так, чтобы NumberPair содержал два целых числа, а не числа с плавающей запятой, как вас беспокоит. Что-то вроде:

@interface NumberPair : NSObject
@property (nonatomic, assign) int x;
@property (nonatomic, assign) int y;
@end

@implementation NumberPair
@synthesize x, y;
@end

...

m_queue = [NSMutableArray array];

NumberPair *newPair = [[NumberPair alloc] init];
newPair.x = 1;
newPair.y = 2;
[m_queue addObject:newPair];

...

NumberPair *nextPoint = [m_queue objectAtIndex:0];
[m_queue removeObjectAtIndex:0];
[self queueFloodFill8:nextPoint.x y:nextPoint.y];

Кроме этого, вы могли бы сделать более похожую на C вещь, имеющую struct, содержащую два целых числа, создать динамически распределенный массив для хранения структур (вам необходимо знать максимальный размер очереди или продолжать перераспределение ). Что-то вроде:

typedef struct {
    int x;
    int y;
} NumberPair;

NumberPair *m_queue = (NumberPair*)malloc(sizeof(NumberPair) * QUEUE_SIZE);
// ... etc

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

Answer 2

Какого размера вы ожидаете получить массив m_queue?

Если стоимость объектов NSMutableArray и NSValue (CGPoint является структурой, реальных затрат там нет) влияетЗатем ваш алгоритм рассмотрит использование массива структур в стиле C в качестве кольцевого буфера вместе с двумя индексами для начала / конца очереди.Вы можете абстрагировать это в класс очереди (или, если нужно, использовать функции, чтобы сэкономить на динамическом вызове метода).

Если вам нужно работать с неограниченной очередью, вы можете malloc & realloc массив с вашим классом очереди / adt по мере необходимости (что по сути то, что NSMutableArray делает за кулисами, но с дополнительными накладными расходами для его общности).