Strassen’s Methodというアルゴリズムを解いている感じを画面にコンソールのようにログを流しながら体験するiPhoneアプリのサンプルコードを描いてみます。
動かすとこんな感じです
サンプルコード
#import “ViewController.h”
@interface ViewController () <UITableViewDataSource, UITableViewDelegate>
@property (nonatomic, strong) NSMutableArray *logBox;
@property (nonatomic, weak) UITableView *table;
@end
@implementation ViewController
– (void)viewDidAppear:(BOOL)animated
{
UITableView *console = [[UITableView alloc] initWithFrame:self.view.bounds style:UITableViewStylePlain];
console.separatorStyle = UITableViewCellSeparatorStyleNone;
[self.view addSubview:console];
console.delegate = self;
console.dataSource = self;
console.backgroundColor = [UIColor blackColor];
self.table = console;
}
– (void)tableView:(UITableView *)tableView didSelectRowAtIndexPath:(NSIndexPath *)indexPath
{
if (indexPath.row == 0) {
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
NSArray *mA = [self createRandomMatSize:pow(2, 6)];
NSArray *mB = [self createRandomMatSize:pow(2, 6)];
[self strassensMethodA:mA B:mB];
});
}
}
#pragma mark – matrix calculate algorithm
– (NSArray *)strassensMethodA:(NSArray*)matA B:(NSArray*)matB
{
NSUInteger n = matA.count;
if (n == 1) {
return @[@[@([matA[0][0] floatValue] * [matB[0][0] floatValue])]];
}
NSMutableArray *childA = [self childMatrix:matA];
NSMutableArray *childB = [self childMatrix:matB];
NSMutableArray *s1 = [self subtractMatrixA:childB[0][1] matrixB:childB[1][1]]; //B12 – B22
NSMutableArray *s2 = [self addMatrixA:childA[0][0] matrixB:childA[0][1]]; //A11 + A12
NSMutableArray *s3 = [self addMatrixA:childA[1][0] matrixB:childA[1][1]];
NSMutableArray *s4 = [self subtractMatrixA:childB[1][0] matrixB:childB[0][0]];
NSMutableArray *s5 = [self addMatrixA:childA[0][0] matrixB:childA[1][1]];
NSMutableArray *s6 = [self addMatrixA:childB[0][0] matrixB:childB[1][1]];
NSMutableArray *s7 = [self subtractMatrixA:childA[0][1] matrixB:childA[1][1]];
NSMutableArray *s8 = [self addMatrixA:childB[1][0] matrixB:childB[1][1]];
NSMutableArray *s9 = [self subtractMatrixA:childA[0][0] matrixB:childA[1][0]];
NSMutableArray *s10 = [self addMatrixA:childB[0][0] matrixB:childB[0][1]];
NSArray *p1 = [self strassensMethodA:childA[0][0] B:s1];
NSArray *p2 = [self strassensMethodA:s2 B:childB[1][1]];
NSArray *p3 = [self strassensMethodA:s3 B:childB[0][0]];
NSArray *p4 = [self strassensMethodA:childA[1][1] B:s4];
NSArray *p5 = [self strassensMethodA:s5 B:s6];
NSArray *p6 = [self strassensMethodA:s7 B:s8];
NSArray *p7 = [self strassensMethodA:s9 B:s10];
NSMutableArray *C11 = [self addMatrixA:[self subtractMatrixA:[self addMatrixA:p5 matrixB:p4] matrixB:p2] matrixB:p6];
NSMutableArray *C12 = [self addMatrixA:p1 matrixB:p2];
NSMutableArray *C21 = [self addMatrixA:p3 matrixB:p4];
NSMutableArray *C22 = [self subtractMatrixA:[self addMatrixA:p5 matrixB:p1]
matrixB:[self addMatrixA:p3 matrixB:p7]];
NSMutableArray *C = [self combineMatrixM11:C11 M12:C12 M21:C21 M22:C22];
[self createLog:C number:n];
return C;
}
– (NSMutableArray *)addMatrixA:(NSArray *)a matrixB:(NSArray *)b
{
NSUInteger n = a.count;
NSMutableArray *m = [NSMutableArray arrayWithCapacity:n];
for (int i=0; i<n; i++) {
m[i] = [NSMutableArray arrayWithCapacity:n];
for (int j=0; j<n; j++) {
m[i][j] = @([a[i][j] floatValue] + [b[i][j] floatValue]);
}
}
return m;
}
– (NSMutableArray *)subtractMatrixA:(NSArray *)a matrixB:(NSArray *)b
{
NSUInteger n = a.count;
NSMutableArray *m = [NSMutableArray arrayWithCapacity:n];
for (int i=0; i<n; i++) {
m[i] = [NSMutableArray arrayWithCapacity:n];
for (int j=0; j<n; j++) {
m[i][j] = @([a[i][j] floatValue] – [b[i][j] floatValue]);
}
}
return m;
}
– (NSMutableArray *)childMatrix:(NSArray *)m
{
NSMutableArray *child = [NSMutableArray arrayWithCapacity:4];
NSUInteger n = m.count / 2;
for (int k=0; k<2; k++) {
child[k] = [NSMutableArray arrayWithCapacity:2];
for (int l=0; l<2; l++) {
child[k][l] = [NSMutableArray arrayWithCapacity:2];
for (int i=0; i<n; i++) {
child[k][l][i] = [NSMutableArray arrayWithCapacity:n];
for (int j=0; j<n; j++) {
child[k][l][i][j] = m[i + n * k][j + n * l];
}
}
}
}
return child;
}
– (NSMutableArray *)combineMatrixM11:(NSMutableArray*)m11 M12:(NSMutableArray *)m12 M21:(NSMutableArray *)m21 M22:(NSMutableArray *)m22
{
NSUInteger n = m11.count * 2;
NSMutableArray *M = [NSMutableArray arrayWithCapacity:n * 2];
for (int i=0; i<n; i++) {
M[i] = [NSMutableArray arrayWithCapacity:n];
for (int j=0; j<n; j++) {
if (i < n/2 && j < n/2) {
M[i][j] = m11[i][j];
} else if (i < n/2 && j >= n/2) {
M[i][j] = m12[i][j – n/2];
} else if (i >= n/2 && j < n/2) {
M[i][j] = m21[i – n/2][j];
} else {
M[i][j] = m22[i – n/2][j – n/2];
}
}
}
return M;
}
– (NSMutableArray *)createRandomMatSize:(int)size
{
NSMutableArray *mat = [NSMutableArray arrayWithCapacity:size];
for (int i=0; i<size; i++) {
mat[i] = [NSMutableArray arrayWithCapacity:size];
for (int j=0; j<size; j++) {
mat[i][j] = @(arc4random() % 10);
}
}
return mat;
}
#pragma mark – table
– (NSInteger)tableView:(UITableView *)tableView numberOfRowsInSection:(NSInteger)section
{
return self.logBox.count + 1;
}
– (UITableViewCell *)tableView:(UITableView *)tableView cellForRowAtIndexPath:(NSIndexPath *)indexPath
{
static NSString *CellIdentifier = @”Cell”;
UITableViewCell *cell = [tableView dequeueReusableCellWithIdentifier:CellIdentifier];
if(cell == nil)
{
cell = [[UITableViewCell alloc] initWithStyle:UITableViewCellStyleDefault reuseIdentifier:CellIdentifier];
cell.backgroundColor = [UIColor clearColor];
cell.textLabel.textColor = [UIColor greenColor];
}
if (indexPath.row == 0) {
cell.textLabel.text = @” > touch start”;
} else {
cell.textLabel.text = self.logBox[indexPath.row – 1];
}
return cell;
}
– (void)createLog:(NSArray*)m number:(NSUInteger)n
{
NSString *description = [[m description] stringByReplacingOccurrencesOfString:@”\n” withString:@””];
description = [description stringByReplacingOccurrencesOfString:@” “ withString:@””];
NSString *logStr = [NSString stringWithFormat:@”n = %d –> %@”, n, description];
if (!self.logBox) {
self.logBox = [NSMutableArray array];
}
[self.logBox addObject:logStr];
dispatch_async(dispatch_get_main_queue(), ^{
[self.table reloadData];
CGPoint bottomOffset = CGPointMake(0, self.table.contentSize.height – self.table.bounds.size.height);
[self.table setContentOffset:bottomOffset animated:YES];
});
}
@end