高效存儲二維數據，使數據按行或列「旋轉」

Question

我想要存儲一個二維數據數組，以便可以按行或列輕鬆「旋轉」數據。

例如，考慮到如果通過我想+2的數據到 「旋轉」 的第三（ 'C'）列中的以下初始狀態

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

，其結果將是：

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