在 Objective-C 中存储和检索数字对的快速方法 [英] Fast way to store and retrieve pairs of numbers in Objective-C

问题描述

我正在实现排队洪水填充算法，需要在 NSMutableArray 中存储和检索数字对.

I am implementing queued flood fill algorithm and need to store and retrieve pairs of numbers in NSMutableArray.

基本上，我正在创建一个数组

Basically, I am creating an array

m_queue = [NSMutableArray array];

然后在某个时候我填充数组

then at some time I populate the array

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

然后我检索下一次迭代的数据并删除数组开头的值

then I retrieve data for the next iteration and remove the value at the beginning of the array

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

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

问题是:我该怎么做才能避免创建大量 CGPoint 和 NSValue 对象?

The question is: what can I do to avoid creating large number of CGPoint and NSValue objects?

我真的不需要点，算法使用整数对，所以我认为可能有更好的方法来存储这些对.

I don't really need points, the algorithm uses pairs of integer values, so I think there might be a better way to store such pairs.

更新:我研究了实现 C 风格的解决方案，如 @mattjgalloway 和 @CRD 建议.

UPDATE: I looked into implementing C-style solution like @mattjgalloway and @CRD suggested.

我已经介绍了

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

并重写代码以使用此类结构的链表而不是 NSMutableArray 和 CGPoint/NSValue.

and have rewritten code to use linked list of such structs instead of NSMutableArray and CGPoint/NSValue.

所有这些都使我的代码快了大约 3 倍.内存消耗也显着下降.

All this made my code about 3 times faster. And memory consumption dropped significantly too.

推荐答案

除了可能创建自己的类，例如 NumberPair 或您放入数组而不是使用 NSValue 和 CGPoint 的东西.这样做可能会稍微提高内存效率，并且您可以使 NumberPair 包含两个整数而不是您关心的浮点数.类似的东西:

There wouldn't really be a better Objective-C / Foundation way of doing it, apart from maybe creating your own class such as NumberPair or something which you put into the array rather than using NSValue and CGPoint. It might be slightly more memory efficient to do that and you could make NumberPair contain two integers rather than floats like you are concerned about. Something like:

@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 包含两个整数，创建一个动态分配的数组来存储结构(你需要知道队列或继续重新分配).类似的东西:

Other than that you could do a more C-like thing of having a struct containing two integers, create a dynamically allocated array to store the structs (you'd need to know the max size of the queue or keep reallocating). Something like:

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

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

另外，您可能想查看我的 MJGStack 类，它包装 NSMutableArray 以提供类似堆栈的接口，您可以稍微调整它以执行您想要的操作，而不是直接使用 NSMutableArray.尽管这无论如何都不是必需的.

Also, you might want to check out my MJGStack class which wraps NSMutableArray to provide a stack like interface which you might be able to adjust slightly to do what you want rather than using NSMutableArray directly. Although that's not essential by any means.

这篇关于在 Objective-C 中存储和检索数字对的快速方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！