Entries

スポンサーサイト

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

NSMutableArrayから任意の要素を削除するには

タグ: Objective-C

NSMutableArray等のコンテナ内の要素を走査するには、通常NSEnumeratorか高速列挙を使う。
これらはとても便利な仕組みだが、走査中はコンテナに変更を加えられないため、「走査しながら不要な要素を見つけて除外する」ことができない。

for(NSNumber* number in array)
{
	if([number intValue] % 3 == 0)
	{
		[array removeObject:number]; // ここで除外すると壊れる!(゜∀。)
	}
}

このようなことをしたい場合、どうするのが良いか。
方法はいくつかある。

一つは、高速列挙を使わない方法。

NSMutableArray* test_1(NSMutableArray* numbers, int denom)
{
	for(int i = [numbers count] - 1; i >= 0; i--)
	{
		NSNumber* number = [numbers objectAtIndex:i];
		if([number intValue] % denom == 0)
		{
			[numbers removeObjectAtIndex:i];
		}
	}
	return numbers;
}

インデックスによる走査が高速列挙と比べて十分速いなら、この方法は悪くない。

次に、removeObjectsInArray:を使う方法。

NSMutableArray* test_2(NSMutableArray* numbers, int denom)
{
	NSMutableArray* targets = [NSMutableArray array];
	for(NSNumber* number in numbers)
	{
		if([number intValue] % denom == 0)
		{
			[targets addObject:number];
		}
	}
	[numbers removeObjectsInArray:targets];
	return numbers;
}

これが元のコードに一番近く、見た目もスマート。
しかし、計算量という観点から見ると、あまり良いものではない。
なぜなら、NSMutableArrayのremoveObjectsInArray:(とremoveObject:)は「除外対象のインデックスを求めるために全ての要素を評価する」ものなので、

  1. 除外対象を求めるために全ての要素を評価し
  2. 除外対象のインデックスを求めるために全ての要素を評価する

という、なんとも無駄な二段構えになってしまうのである。

removeObjectsInArray:を使うぐらいなら、removeObjectsAtIndexes:を使った方がいい。

NSMutableArray* test_3(NSMutableArray* numbers, int denom)
{
	NSMutableIndexSet* targetIndexes = [NSMutableIndexSet indexSet];
	NSUInteger index = 0;
	for(NSNumber* number in numbers)
	{
		if([number intValue] % denom == 0)
		{
			[targetIndexes addIndex:index];
		}
		index++;
	}
	[numbers removeObjectsAtIndexes:targetIndexes];
	return numbers;
}

この方法は私も好んで使う。

あとはfilterUisngPredicate:があるが……今回の評価式をどう表記すれば良いのか/表記できるのか分からないので、見送る。
iPhone OSでは使えないメソッドだし。

「除外」にこだわらないのであれば、新しい配列を用意し、そちらに必要なものを「抜き出す」方法も考えられる。

NSMutableArray* test_4(NSMutableArray* numbers, int denom)
{
	NSMutableArray* filterdNumbers = [NSMutableArray array];
	for(NSNumber* number in numbers)
	{
		if([number intValue] % denom != 0)
		{
			[filterdNumbers addObject:number];
		}
	}
	return filterdNumbers;
}

除外対象の位置や数次第では、むしろこの方が速い。

さて。
色々方法を挙げたが、では、元のコードがやろうとしていた「3の倍数を除外する」処理に関しては、どの方法が一番速いのだろう。
次のコードで比較してみる。

NSMutableArray* (*functions[])(NSMutableArray*, int) = { test_1, test_2, test_3, test_4 };
for(int i = 1000000; i >= 10; i /= 10)
{
	NSLog(@"[%d]", i);
	for(int j = 0; j < sizeof(functions) / sizeof(*functions); j++)
	{
		NSAutoreleasePool* pool = [[NSAutoreleasePool alloc] init];
		NSMutableArray* numbers = [NSMutableArray arrayWithCapacity:i];
		for(int k = 0; k < i; k++)
		{
			[numbers addObject:[NSNumber numberWithInt:k]];
		}
		NSTimeInterval start = [NSDate timeIntervalSinceReferenceDate];
		NSMutableArray* result = (*functions[j])(numbers, 3);
		NSTimeInterval end = [NSDate timeIntervalSinceReferenceDate];
		NSLog(@"test_%d %d: %f", j + 1, [result count], end - start);
		[pool drain];
	}
}

実験環境はMacOS X 10.5.6、MPB(C2D2.8)。

[1000000]
test_1 666666: 0.429504
test_2 666666: 1.299514
test_3 666666: 0.515651
test_4 666666: 0.219786
[100000]
test_1 66666: 0.266793
test_2 66666: 0.312643
test_3 66666: 0.273719
test_4 66666: 0.014766
[10000]
test_1 6666: 0.003096
test_2 6666: 0.007273
test_3 6666: 0.003714
test_4 6666: 0.001416
[1000]
test_1 666: 0.000137
test_2 666: 0.000584
test_3 666: 0.000201
test_4 666: 0.000141
[100]
test_1 66: 0.000013
test_2 66: 0.000058
test_3 66: 0.000021
test_4 66: 0.000018
[10]
test_1 6: 0.000003
test_2 6: 0.000054
test_3 6: 0.000006
test_4 6: 0.000005

やはりtest_2は遅い。
そして次に遅いのはtest_3(´・ω・`)。除外する要素数が多く、NSMutableIndexSetへのaddIndex:が足を引っ張っている。
test_1とtest_4は、「配列の途中の要素を多数除外する」今回の例では、後者の方が安定して速い。

では、今度は除外する数を「3の倍数」から「100の倍数」に変えて実行してみよう。

NSMutableArray* result = (*functions[j])(numbers, 100);
[1000000]
test_1 990000: 0.082423
test_2 990000: 0.482822
test_3 990000: 0.061485
test_4 990000: 0.322317
[100000]
test_1 99000: 0.016072
test_2 99000: 0.039003
test_3 99000: 0.015080
test_4 99000: 0.019549
[10000]
test_1 9900: 0.000718
test_2 9900: 0.002801
test_3 9900: 0.000578
test_4 9900: 0.002020
[1000]
test_1 990: 0.000072
test_2 990: 0.000434
test_3 990: 0.000060
test_4 990: 0.000196
[100]
test_1 99: 0.000011
test_2 99: 0.000025
test_3 99: 0.000006
test_4 99: 0.000023
[10]
test_1 9: 0.000003
test_2 9: 0.000008
test_3 9: 0.000004
test_4 9: 0.000005

一番速いのはtest_3(`・ω・´)。objectAtIndex:ループに対する高速列挙の優位性が出た。
ただ、これも要素数が少ないと「NSMutableIndexSetのインスタンスを作ってremoveObjectsAtIndexes:に渡す」こと自体のコストがネックになる。
結局はtest_1のやり方が一番使いやすいかもしれない。
3の倍数の時に一番速かったtest_4は、追加する要素が増えた分順当に遅くなり3位になった。
test_2は、やはり遅い。

スポンサーサイト

コメント

コメントの投稿

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

トラックバック

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

Appendix

タグ

Blog内検索

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