NSMutableArrayとLinkedList速度比較

どれくらい違いあるのか調べてみた。
メモリアクセス遅いということが非常によくわかる。
あと、LinkedListは、シリアライズしてディスクやネットワークに書き込みできないのが弱点。

Mac Mini / CPU 2.7GHz Intel Core i7 / RAM 8GB 1333MHz DDR3 / iOS simulator 7.0

要素の数:1000 試行回数:100 分解能:usec
2013-07-18 00:25:05.505 Experiment[13921:a0b] linkedList new elapsed:161780
2013-07-18 00:25:05.506 Experiment[13921:a0b] linkedList new elapsed average:192075.000000
2013-07-18 00:25:05.506 Experiment[13921:a0b] linkedList new elapsed min:143801
2013-07-18 00:25:05.507 Experiment[13921:a0b] linkedList new elapsed max:241674
2013-07-18 00:25:05.547 Experiment[13921:a0b] linkedList read elapsed:388
2013-07-18 00:25:05.548 Experiment[13921:a0b] linkedList read elapsed average:400.000000
2013-07-18 00:25:05.548 Experiment[13921:a0b] linkedList read elapsed min:339
2013-07-18 00:25:05.548 Experiment[13921:a0b] linkedList read elapsed max:889

要素の数:1000 試行回数:100 分解能:usec
2013-07-18 00:24:44.709 Experiment[13921:a0b] MutableArray new elapsed:304
2013-07-18 00:24:44.710 Experiment[13921:a0b] MutableArray new elapsed average:350.000000
2013-07-18 00:24:44.711 Experiment[13921:a0b] MutableArray new elapsed min:304
2013-07-18 00:24:44.711 Experiment[13921:a0b] MutableArray new elapsed max:551
2013-07-18 00:24:44.722 Experiment[13921:a0b] MutableArray read elapsed:99
2013-07-18 00:24:44.723 Experiment[13921:a0b] MutableArray read elapsed average:105.000000
2013-07-18 00:24:44.723 Experiment[13921:a0b] MutableArray read elapsed min:98
2013-07-18 00:24:44.723 Experiment[13921:a0b] MutableArray read elapsed max:178

EXViewController.m`

//
//  EXViewController.m
//  Experiment
//
//  Created by adachic on 2013/07/17.
//  Copyright (c) 2013年 adachic. All rights reserved.
//

#import "EXViewController.h"
#include <sys/time.h>

const NSUInteger arraySize = 1000;
const NSUInteger tryCount = 100;

@interface Content : NSObject
@property(retain) Content *next;
@property(retain) NSString *dummyData;
@end

@implementation Content
- (id)init {
    if (self = [super init]) {
        /* 500characters */
        self.dummyData = @""
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    }
    return self;
}
@end

@interface EXViewController ()

@property(retain) NSMutableArray *mArray;
@property(retain) NSArray *array;
@property(retain) Content *head;

@end

@implementation EXViewController

static char **charsArray;

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    charsArray = (char **) malloc(sizeof(char *) * arraySize);
    memset(charsArray, 0x0, sizeof(charsArray));
    self.mArray = [NSMutableArray array];
    self.array = [NSArray array];
    self.head = [[Content alloc] init];
}

- (void)didReceiveMemoryWarning {
    [super didReceiveMemoryWarning];
    // Dispose of any resources that can be recreated.
}

volatile void evaluatePattern1(NSMutableArray *mArray) {
    struct timeval start[tryCount];
    struct timeval end[tryCount];
    time_t elapsed = 0;
    time_t elapsed_min = INT32_MAX;
    time_t elapsed_max = 0;
    long long elapsed_sum_for_ave = 0;
    double elapsed_ave = 0;
    /**/
    for (int try = 0; try < tryCount; try++) {
        gettimeofday(&start[try], NULL);
        for (int ii = 0; ii < arraySize; ii++) {
            [mArray addObject:[[Content alloc] init]];
        }
        gettimeofday(&end[try], NULL);
        elapsed = (end[try].tv_sec - start[try].tv_sec) * 1000000 + end[try].tv_usec - start[try].tv_usec;
        if (elapsed_min > elapsed) {
            elapsed_min = elapsed;
        }
        if (elapsed_max < elapsed) {
            elapsed_max = elapsed;
        }
        elapsed_sum_for_ave += elapsed;
        if (try != tryCount - 1) {
            [mArray removeAllObjects];
        }
    }
    elapsed_ave = elapsed_sum_for_ave / tryCount;

    NSLog(@"MutableArray new elapsed:%ld", elapsed);
    NSLog(@"MutableArray new elapsed average:%lf", elapsed_ave);
    NSLog(@"MutableArray new elapsed min:%ld", elapsed_min);
    NSLog(@"MutableArray new elapsed max:%ld", elapsed_max);

    elapsed_min = INT32_MAX;
    elapsed_max = 0;
    elapsed_sum_for_ave = 0;
    elapsed_ave = 0;
    NSString *aho;
    for (int try = 0; try < tryCount; try++) {
        gettimeofday(&start[try], NULL);
        for (int ii = 0; ii < arraySize; ii++) {
            aho = [mArray objectAtIndex:ii];
        }
        gettimeofday(&end[try], NULL);
        elapsed = (end[try].tv_sec - start[try].tv_sec) * 1000000 + end[try].tv_usec - start[try].tv_usec;
        if (elapsed_min > elapsed) {
            elapsed_min = elapsed;
        }
        if (elapsed_max < elapsed) {
            elapsed_max = elapsed;
        }
        elapsed_sum_for_ave += elapsed;
    }
    elapsed_ave = elapsed_sum_for_ave / tryCount;

    NSLog(@"MutableArray read elapsed:%ld", elapsed);
    NSLog(@"MutableArray read elapsed average:%lf", elapsed_ave);
    NSLog(@"MutableArray read elapsed min:%ld", elapsed_min);
    NSLog(@"MutableArray read elapsed max:%ld", elapsed_max);
}

volatile void evaluatePattern2(Content *head) {
    struct timeval start[tryCount];
    struct timeval end[tryCount];
    time_t elapsed = 0;
    time_t elapsed_min = INT32_MAX;
    time_t elapsed_max = 0;
    long long elapsed_sum_for_ave = 0;
    double elapsed_ave = 0;

    Content *cur;
    for (int try = 0; try < tryCount; try++) {
        head.next = [[Content alloc] init];
        gettimeofday(&start[try], NULL);
        for (int ii = 0; ii < arraySize; ii++) {
            cur = head.next;
            while (cur.next) {
                cur = cur.next;
            }
            cur.next = [[Content alloc] init];
        }
        gettimeofday(&end[try], NULL);
        elapsed = (end[try].tv_sec - start[try].tv_sec) * 1000000 + end[try].tv_usec - start[try].tv_usec;
        if (elapsed_min > elapsed) {
            elapsed_min = elapsed;
        }
        if (elapsed_max < elapsed) {
            elapsed_max = elapsed;
        }
        elapsed_sum_for_ave += elapsed;
        NSLog(@"%d", try);
    }
    elapsed_ave = elapsed_sum_for_ave / tryCount;

    NSLog(@"linkedList new elapsed:%ld", elapsed);
    NSLog(@"linkedList new elapsed average:%lf", elapsed_ave);
    NSLog(@"linkedList new elapsed min:%ld", elapsed_min);
    NSLog(@"linkedList new elapsed max:%ld", elapsed_max);

    elapsed_min = INT32_MAX;
    elapsed_max = 0;
    elapsed_sum_for_ave = 0;
    elapsed_ave = 0;
    NSString *aho;
    for (int try = 0; try < tryCount; try++) {
        gettimeofday(&start[try], NULL);
        cur = head.next;
        while (cur.next) {
            cur = cur.next;
            aho = cur;
        }
        gettimeofday(&end[try], NULL);
        elapsed = (end[try].tv_sec - start[try].tv_sec) * 1000000 + end[try].tv_usec - start[try].tv_usec;
        if (elapsed_min > elapsed) {
            elapsed_min = elapsed;
        }
        if (elapsed_max < elapsed) {
            elapsed_max = elapsed;
        }
        elapsed_sum_for_ave += elapsed;
    }
    elapsed_ave = elapsed_sum_for_ave / tryCount;

    NSLog(@"linkedList read elapsed:%ld", elapsed);
    NSLog(@"linkedList read elapsed average:%lf", elapsed_ave);
    NSLog(@"linkedList read elapsed min:%ld", elapsed_min);
    NSLog(@"linkedList read elapsed max:%ld", elapsed_max);
}

- (IBAction)pushButton1:(id)sender {
    evaluatePattern1(self.mArray);
}

- (IBAction)pushButton2:(id)sender {
    evaluatePattern2(self.head);
}

@end