Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

NSMutableArrayは環状バッファ

タグ: Objective-C Mac

――という噂を耳にしたが出典が見つからない。
なのでとりあえず現在(MacOS X 10.5.6)の実装を慮ってみる。

void test(unsigned int n)
{
	NSMutableArray* numbers = [NSMutableArray arrayWithCapacity:n + 1];
	for(unsigned int i = 0; i < n; i++)
	{
		[numbers addObject:[NSNumber numberWithInt:i]];
	}
	
	NSNumber* number = [NSNumber numberWithInt:n];
	for(unsigned int i = 0; i <= 4; i++)
	{
		unsigned int index = n * i / 4;
		NSTimeInterval start = [NSDate timeIntervalSinceReferenceDate];
		for(int j = 0; j < 1000000; j++)
		{
			[numbers insertObject:number atIndex:index];
			[numbers removeObjectAtIndex:index];
		}
		NSTimeInterval end = [NSDate timeIntervalSinceReferenceDate];
		NSLog(@"%d %6d: %f", n, index, end - start);
	}
}

指定した数の要素を持つNSMutableArrayの、「先頭」「前より」「真ん中」「後ろより」「後方」への要素追加/削除にかかる時間(×1000000)を測る。

引数は、

for(int i = 10; i <= 100000; i *= 10)
{
	NSAutoreleasePool* pool = [[NSAutoreleasePool alloc] init];
	test(i);
	[pool drain];
}

「10」「100」「1000」「10000」「100000」の5通り。

これをMBP(C2D2.8)で実行。

10      0: 0.189038
10      2: 0.203648
10      5: 0.206734
10      7: 0.203767
10     10: 0.187448
100      0: 0.230543
100     25: 0.262474
100     50: 0.277086
100     75: 0.269977
100    100: 0.232720
1000      0: 0.231873
1000    250: 0.390210
1000    500: 0.631260
1000    750: 0.389550
1000   1000: 0.231937
10000      0: 0.229667
10000   2500: 2.249399
10000   5000: 3.242165
10000   7500: 1.745310
10000  10000: 0.232156
100000      0: 0.228711
100000  25000: 18.939664
100000  50000: 38.732296
100000  75000: 22.498229
100000 100000: 0.230097

先頭と後方への追加/削除だけが定数時間で済んでいるところを見ると、たしかに環状バッファっぽい感じはする。

……と、ここまで読んで
「成る程環状バッファか」
と納得した人、逆に
「これだけでは環状バッファとは断定できぬ」
という人は、続きをどうぞ。

スポンサーサイト

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://idlysphere.blog66.fc2.com/tb.php/178-0d74f680
この記事にトラックバックする(FC2ブログユーザー)

Appendix

タグ

Blog内検索

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。