Как реализовать круговой буфер в Objective C для высокой производительности

Question

Мы хотим добавить массив удвоений в круглый буфер в Objective C много раз в секунду.

В настоящее время мы используем NSMutableArray, вложенный в другой массив NSMutableArray (2D-массив). Это работает отлично, но слишком медленно для наших нужд.

Мы хотим добавить в круглый буфер много раз в секунду. Когда мы это делаем и выполняем мониторинг производительности, мы видим, что вызов removeObjectAtIndex: 0 становится узким местом (сдвиг n-1 объектов или O (n-1)). Это связано с тем, что в нашем круговом буфере имеется много тысяч записей.

Мы рассмотрели возможно использование STL и std :: deque. Мы также посмотрели CHDataStructures. Как вы знаете, STL находится на C++ и может быть интегрирована, но не так прямо, как решение Objective C. CHDataStructures становится устаревшим и не совместим с ARC.

Просьба предложить нам использовать круговой буфер (для нашего массива удвоений) для высокой производительности с помощью образца кода, если это возможно.

Answer 1

Прочитав ваш комментарий (и подумал об этом чуть больше), я понял, что использование обычного NSArray было бы лучше, так как нет проблем с управлением памятью (NSArrays сохраняет свои объекты естественно). Просто определите емкость спереди, чтобы избежать необходимости перераспределять память по мере ее запуска. Вызов [self resetBuffer] быстро освободит все данные и начнется снова.

#define BUFFER_SIZE 1000 

@implementation ViewController { 
    NSMutableArray *circularBuffer; 
    NSUInteger bufferHead; 
} 

- (instancetype)initWithCoder:(NSCoder *)aDecoder { 
    if (self = [super initWithCoder:aDecoder]) { 
     [self resetBuffer]; 
    } 
    return self; 
} 

- (void)addArrayToBuffer:(NSMutableArray *)incoming { 

    if (bufferHead < circularBuffer.count) 
     [circularBuffer replaceObjectAtIndex:bufferHead withObject:incoming]; 
    else 
     [circularBuffer addObject:incoming]; 

    bufferHead = (bufferHead + 1) % BUFFER_SIZE; 
} 

- (NSArray *)bufferContent { 

    if (circularBuffer.count < BUFFER_SIZE) { 
     return circularBuffer; 
    } else { 
     NSArray *arrHead = [circularBuffer objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, bufferHead)]]; 
     NSArray *arrTail = [circularBuffer objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(bufferHead, BUFFER_SIZE-bufferHead)]]; 

     return [arrTail arrayByAddingObjectsFromArray:arrHead]; 
    } 
} 

- (void)resetBuffer { 
    circularBuffer = [NSMutableArray arrayWithCapacity:BUFFER_SIZE]; 
    bufferHead = 0; 
}