0

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

例如，考虑以下初始状态

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

如果我想将数据的第三（'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

我可以设想您如何通过将基础数据存储为行数组或列数组来启用一种有效的按行或按列旋转的方法，但是能够同时执行这两种方法可能会导致具有一种旋转方式效率要低得多，因为您必须依次在每个阵列上执行操作。

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

4

1 回答 1

2

除非你有巨大的数组，否则我不会像你提到的那样使用普通 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
于 2013-04-25T21:23:36.813 回答