ios - 二维数据高效存储，实现 "rotation"的行列数据

Question

我想存储一个二维数据数组，这样可以轻松地按行或列“旋转”数据。

例如，考虑以下初始状态

A B C D
E F G H
I J K L
M N O P

如果我想将数据的第 3('C')列“旋转”+2，结果将是:

A B K D
E F O H
I J C L
M N H P

如果我想将第二行('E')“旋转”-1，结果将是:

A B K D
F O H E
I J C L
M N H P

我可以设想如何通过将基础数据存储为行数组或列数组来实现按行或列旋转 的有效方法，但能够做到两者都可能导致使用一种旋转方式的效率大大降低，因为您必须依次对每个阵列执行操作。

话又说回来，我以前从未尝试过解决这类问题，所以也许我遗漏了一些明显的东西。

Answer 1

除非你有巨大的数组，否则我不会像你提到的那样使用带有普通 NSArrays 的行或列存储。另一种实现方式是只使用一个数组并自己计算索引。最后，还有可能在内部使用 c 数组。我已经使用 4x4 矩阵实现了所有三个，c 数组是迄今为止最快的，但简单的嵌套数组仍然足够快:

#import <mach/mach_time.h>

typedef void(^execution_block_t)(void);

double time_execution(execution_block_t aBlock);
double time_execution(execution_block_t aBlock)
{
    uint64_t time0 = mach_absolute_time();
    aBlock();
    uint64_t time1 = mach_absolute_time();
    return (double)(time1 - time0)/NSEC_PER_SEC;
}

// -----------------------------------------------------------------------------
   #pragma mark - Using Nested Arrays
// -----------------------------------------------------------------------------

@interface Simple2DRotMatrix : NSObject {
    NSMutableArray *_rows;
}
- (void) rotateRowRightAtIndex:(NSUInteger)index;
- (void) rotateColumnRightAtIndex:(NSUInteger)index;
@end

@implementation Simple2DRotMatrix

- (id) init
{
    if ((self = [super init])) {
        _rows = [NSMutableArray array];
        for (int i=0;  i<4;  i++) {
            NSMutableArray *aRow = [NSMutableArray array];
            for (int j=0;  j<4;  j++)
                [aRow addObject:@(i*4+j+1)];
            [_rows addObject:aRow];
        }
    }
    return self;
}

- (void) rotateArrayRight:(NSMutableArray*)array
{
    id value = array.lastObject;
    [array removeObjectAtIndex:array.count-1];
    [array insertObject:value atIndex:0];
}

- (void) rotateRowRightAtIndex:(NSUInteger)index
{
    [self rotateArrayRight:_rows[index]];
}

- (void) rotateColumnRightAtIndex:(NSUInteger)index
{
    NSMutableArray *col = [NSMutableArray arrayWithCapacity:_rows.count];
    for (NSArray *row in _rows)
        [col addObject:row[index]];

    [self rotateArrayRight:col];

    NSEnumerator *values = col.objectEnumerator;
    for (NSMutableArray *row in _rows)
        [row replaceObjectAtIndex:index withObject:values.nextObject];
}

- (NSString*) description
{
    NSMutableString *descr = [NSMutableString string];
    for (NSArray *row in _rows) {
        [descr appendString:[row componentsJoinedByString:@","]];
        [descr appendString:@"\n"];
    }
    return descr;
}

@end


// -----------------------------------------------------------------------------
   #pragma mark - Using 1-D Arrays
// -----------------------------------------------------------------------------

@interface Simple1DRotMatrix : NSObject {
    NSMutableArray    *_values;
    NSMutableIndexSet *_indexes0;
}
- (void) rotateRowRightAtIndex:(NSUInteger)index;
- (void) rotateColumnRightAtIndex:(NSUInteger)index;
@end

@implementation Simple1DRotMatrix

- (id) init
{
    if ((self = [super init])) {
        _values = [NSMutableArray array];
        for (int i=0;  i<16;  i++)
            [_values addObject:@(i)];
        _indexes0 = [NSMutableIndexSet indexSetWithIndex:0];
        [_indexes0 addIndex:4];
        [_indexes0 addIndex:8];
        [_indexes0 addIndex:12];
    }
    return self;
}

- (void) rotateArrayRight:(NSMutableArray*)array
{
    id value = array.lastObject;
    [array removeObjectAtIndex:array.count-1];
    [array insertObject:value atIndex:0];
}

- (void) rotateRowRightAtIndex:(NSUInteger)index
{
    NSIndexSet *indexes = [NSIndexSet indexSetWithIndexesInRange:NSMakeRange(index*4, 4)];
    NSMutableArray *row = [[_values objectsAtIndexes:indexes] mutableCopy];
    [self rotateArrayRight:row];
    [_values replaceObjectsAtIndexes:indexes withObjects:row];
}

- (void) rotateColumnRightAtIndex:(NSUInteger)index
{
    NSMutableIndexSet *indexes = [_indexes0 mutableCopy];
    [indexes shiftIndexesStartingAtIndex:0 by:index];
    NSMutableArray *col = [[_values objectsAtIndexes:indexes] mutableCopy];
    [self rotateArrayRight:col];
    [_values replaceObjectsAtIndexes:indexes withObjects:col];
}

- (NSString*) description
{
    NSMutableString *descr = [NSMutableString stringWithString:@"\n"];
    for (int i=0;  i<4;  i++) {
        for (int j=0;  j<4;  j++) {
            [descr appendFormat:@"%@,",_values[i*4+j]];
        }
        [descr appendString:@"\n"];
    }
    return descr;
}

@end



// -----------------------------------------------------------------------------
   #pragma mark - Using C Arrays
// -----------------------------------------------------------------------------

@interface Simple2DCArrayRotMatrix : NSObject {
    id _values[4][4];
}
- (void) rotateRowRightAtIndex:(NSUInteger)index;
- (void) rotateColumnRightAtIndex:(NSUInteger)index;
@end

@implementation Simple2DCArrayRotMatrix

- (id) init
{
    if ((self = [super init])) {
        for (int i=0;  i<4;  i++) {
            for (int j=0;  j<4;  j++)
                _values[i][j] = @(i);
        }
    }
    return self;
}

- (void) rotateRowRightAtIndex:(NSUInteger)index
{
    id temp = _values[index][0];
    _values[index][0] = _values[index][3];
    _values[index][1] = _values[index][0];
    _values[index][2] = _values[index][1];
    _values[index][3] = temp;
}

- (void) rotateColumnRightAtIndex:(NSUInteger)index
{
    id temp = _values[0][index];
    _values[0][index] = _values[3][index];
    _values[1][index] = _values[0][index];
    _values[2][index] = _values[1][index];
    _values[3][index] = temp;
}

- (NSString*) description
{
    NSMutableString *descr = [NSMutableString stringWithString:@"\n"];
    for (int i=0;  i<4;  i++) {
        for (int j=0;  j<4;  j++) {
            [descr appendFormat:@"%@,",_values[i][j]];
        }
        [descr appendString:@"\n"];
    }
    return descr;
}

@end



int main (int argc, const char * argv[])
{
    @autoreleasepool {

        static int kLoopSize = 50000;

        Simple2DRotMatrix *mat2d = [[Simple2DRotMatrix alloc] init];

        double t0 = time_execution(^(void) {
            for (int i=0;  i<kLoopSize;  i++)
                [mat2d rotateRowRightAtIndex:i%4];
        });

        double t1 = time_execution(^(void) {
            for (int i=0;  i<kLoopSize;  i++)
                [mat2d rotateColumnRightAtIndex:i%4];
        });

        NSLog(@"2D: Time for %d row rotations: %f",kLoopSize, t0);
        NSLog(@"2D: Time for %d column rotations: %f",kLoopSize, t1);


        Simple1DRotMatrix *mat1d = [[Simple1DRotMatrix alloc] init];

        t0 = time_execution(^(void) {
            for (int i=0;  i<kLoopSize;  i++)
                [mat1d rotateRowRightAtIndex:i%4];
        });

        t1 = time_execution(^(void) {
            for (int i=0;  i<kLoopSize;  i++)
                [mat1d rotateColumnRightAtIndex:i%4];
        });

        NSLog(@"1D: Time for %d row rotations: %f",kLoopSize, t0);
        NSLog(@"1D: Time for %d column rotations: %f",kLoopSize, t1);


        Simple2DCArrayRotMatrix *mat2dC = [[Simple2DCArrayRotMatrix alloc] init];

        t0 = time_execution(^(void) {
            for (int i=0;  i<kLoopSize;  i++)
                [mat2dC rotateRowRightAtIndex:i%4];
        });

        t1 = time_execution(^(void) {
            for (int i=0;  i<kLoopSize;  i++)
                [mat2dC rotateColumnRightAtIndex:i%4];
        });

        NSLog(@"C-Array: Time for %d row rotations: %f",kLoopSize, t0);
        NSLog(@"C-Array: Time for %d column rotations: %f",kLoopSize, t1);
    }
    return 0;
}

我得到以下输出:

2D: Time for 50000 row rotations: 0.009645
2D: Time for 50000 column rotations: 0.099982
1D: Time for 50000 row rotations: 0.118850
1D: Time for 50000 column rotations: 0.133798
C-Array: Time for 50000 row rotations: 0.001620
C-Array: Time for 50000 column rotations: 0.002277