NSMutableArrayとLinkedList速度比較

gistfile1.txt

//
//  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);
}

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;

//    head.next = [[Content alloc] init];
    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

要素の数：1000
2013-07-18 00:06:22.516 Experiment[13505:a0b] linkedList new elapsed:147756
2013-07-18 00:06:22.517 Experiment[13505:a0b] linkedList new elapsed average:188784.000000
2013-07-18 00:06:22.517 Experiment[13505:a0b] linkedList new elapsed min:142935
2013-07-18 00:06:22.518 Experiment[13505:a0b] linkedList new elapsed max:310306
2013-07-18 00:06:47.332 Experiment[13505:a0b] linkedList read elapsed:346
2013-07-18 00:06:47.333 Experiment[13505:a0b] linkedList read elapsed average:437.000000
2013-07-18 00:06:47.333 Experiment[13505:a0b] linkedList read elapsed min:342
2013-07-18 00:06:47.334 Experiment[13505:a0b] linkedList read elapsed max:680

要素の数：1000
2013-07-18 00:08:08.535 Experiment[13505:a0b] MutableArray new elapsed:302
2013-07-18 00:08:08.535 Experiment[13505:a0b] MutableArray new elapsed average:315.000000
2013-07-18 00:08:08.536 Experiment[13505:a0b] MutableArray new elapsed min:297
2013-07-18 00:08:08.536 Experiment[13505:a0b] MutableArray new elapsed max:556
2013-07-18 00:08:08.546 Experiment[13505:a0b] MutableArray read elapsed:97
2013-07-18 00:08:08.546 Experiment[13505:a0b] MutableArray read elapsed average:90.000000
2013-07-18 00:08:08.547 Experiment[13505:a0b] MutableArray read elapsed min:85
2013-07-18 00:08:08.547 Experiment[13505:a0b] MutableArray read elapsed max:186