CODEWITHSUNDEEP
objective-cdata-structuresnsmutablearrayios5iphone-4
Alex Stone
Alex Stone

Reputation: 47348

Objective-C efficient closed loop equivalent of NSMutableArray

Right now my app uses a pre-allocated NSMutableArray of ~40000 objects. When the app hits this limit, it crashes due to an index out of bounds exception. I would like to eliminate this concern by re-using objects within a smaller array, lets say 900 items. This should give me enough room to be able to query previous objects within a certain time window.

I'm trying to avoid continuously growing the array, and I see 2 potential solutions (I'm using ARC and a backgroundSelector to periodically autosave the data):

1) keep removing old objects when new ones are inserted. I see the potential downside of having to continuously allocate objects. The benefit is that the data is in order, and I control the amount of elements in the array, accessing elements is also easy. Some of the app's logic may break if I try to access an element that is beyond the bounds of the loop (for example a 900 element queue and I'm trying to access element (currentIndex -1200). Another downside is that this is not safe to use with multiple threads, if I try to iterate over the array to try to save some elements, it will crash if I try to dequeue the same array from a different thread. 

NSMutableArray* queue;


- (NSNumber*) dequeue:(NSMutableArray*)queue {
    if ([queue count] == 0) return nil; // to avoid raising exception (Quinn)
    id headObject = [queue objectAtIndex:0];
    if (headObject != nil) {
        // so it isn't dealloc'ed on remove
        [queue removeObjectAtIndex:0];
    }
    return headObject;
}

// Add to the tail of the queue (no one likes it when people cut in line!)
- (void) enqueue:(NSNumber*)anObject forQueue:(NSMutableArray*) queue{
    [queue addObject:anObject];
    //this method automatically adds to the end of the array
}

2) Use some kind of a closed loop, and reset objects prior to use. Here any kind of array access logic would still work, although the results may be surprising. I also have not tested any of these methods. 

NSMutableArray loopingArray;

- (id) getObjectAtIndex:(int)arrayIndex{
    id object =  [loopingArray objectAtIndex:arrayIndex %arraySize];  
    return object;
}

- (id) getObjectForWriting{
    [loopingArray resetForEvent:(++currentIndex %arraySize)];  
    id object =  [loopingArray objectAtIndex:currentIndex %arraySize];  
    return object;
}

- (id) getCurrentObject{
    id object =  [loopingArray objectAtIndex:currentIndex %arraySize];  
    return object;
}

-(void)resetForEvent:(int)event
{
   //get an object at index and ask it to reset itself 
}

3) Same as the queue, except the de-queued object is reset and is inserted at the head of the queue. This seems like the most reasonable solution.

How would you solve a problem like this? After writing this, it seems that the queue is an easier solution, even if it will require re-allocating the objects.

Updated: I ended up using a circular buffer like data structure:

int count = [mutableArray count]
    [mutableArray replaceObjectAtIndex:((lastProcessedEpoch+1)%count) withObject:newDataPoint];
    lastProcessedEpoch++;

All subsequent accesses of the array use the current index % count. The call to replace can be changed to reset, but I dont want to write a reset method for ~30 variables within data point.

Thank you!

Upvotes: 0

Views: 559

Answers (3)

gnasher729
gnasher729

Reputation: 52538

In an NSMutableArray, adding / removing elements both at the start and at the end are fast (dozens of nanoseconds). There is no need to implement a fancy circular buffer because NSMutableArray is clever itself. Just add elements at the end and remove them at the start.

Upvotes: 0

yershuachu
yershuachu

Reputation: 788

I think that you can simply use modulo of the array count:

array[index%array.count];

Upvotes: 0

Jesse Rusak
Jesse Rusak

Reputation: 57168

I'd use a circular buffer, which is similar to what what you're suggesting for #2.

I think your #1 method is probably simpler, though may be too slow, since the array might do a lot of work when you modify the head of the array. Watch your dequeue method; it needs to retain and autorelease the returned object before removing it from the queue.

Upvotes: 2

Related Questions