どれくらい違いあるのか調べてみた。
メモリアクセス遅いということが非常によくわかる。
あと、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

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

import "EXViewController.h"

include

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