Entries

スポンサーサイト

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

CFArrayは環状バッファではない

タグ: Objective-C

記事「NSMutableArrayは環状バッファ」の続き。

なお、NSMutableArrayクラスが生成するオブジェクトは実際にはNSMutableArrayのサブクラスのインスタンスで、大抵はCFArrayと等価なNSCFArrayクラスのインスタンスである。
ゆえに前回記事表題の「NSMutableArray」も、厳密には「NSCFArray」か「CFArray」にすべきである。

さて、「CFArray」の計算量についてだが、これはちゃんとADCの方に資料があった。

Collections Programming Topics for Core Foundation

Xcodeのヘルプで「Collections Programming Topics for Cocoa」の方は見たんだが、こちらは見てなかった。
というか、「for Co」まで同じだから「for Cocoa」と「for Core Foundation」の2つがあることに気付かなかった。

「Co」coaと「Co」re Foundation

さらに、これと同程度の情報はCFArray.hにも記載されていた。
CFArrayもリファレンスの方は見たんだが、むぅ。

まあそれはともかく。
CFArrayの計算量に関する規定は、斜め読んだ感じ次のようになっている。

  • 値へのアクセス時間は最悪でもO(log N)。まあ、大抵はO(1)。
  • そんなわけだから、リニアサーチの最大計算量もO(N log N)になる。
  • 挿入/削除はO(N)だが、いくつかの実装ではO(N log N)になることも。
  • どの「位置」が最も効率的かなんて決まっていない。先頭に近いほどアクセスが速いとか、後ろに近いほど挿入/削除が速いとか、あるいは「そう」かもしれないが「絶対」じゃない。

アクセス時間がO(log N)というと、平衡二分探索木か。
全体的に、「一般的な配列ではなく、二分木かもしれない」と言っているように見える。
「配列か二分木かはっきりしろ」と言いたいところだが……まあ、こう規定されているのでは仕方がない。
CFArrayのことは「環状バッファかもしれないが、実装によっては二分木程度の計算量を要する配列」程度に認識し、素直にstd::vectorやstd::dequeを使うことにしよう――

そう、心に決めた矢先、CFArrayの実装に関するこんな資料を見つけた。
これが真だとすると、CFArrayは環状バッファではなく、また配列の先頭に値を定数時間で追加/削除することもできない
だが、前回の実験では先頭への追加/削除が定数時間で行われていることを確認している。
となると、現在のCFArrayの実装は、これとは異なる可能性が高い。
俄然、興味が沸いてきたので、ADCから最新のCore Foundationのソース(CF-476.17)を落として見てみることにした。
落とすのが面倒なら、少々古いがCF-368のでも良いだろう。

さて、最新のソースによると、CFArrayの内部実装はこのようになっている。

struct __CFArrayDeque {
    uint32_t _leftIdx;
    uint32_t _capacity;
    int32_t _bias;
#if __LP64__
    uint32_t _pad;   // GC:  pointers must be 8-byte aligned for the collector to find them.
#endif
    /* struct __CFArrayBucket buckets follow here */
};

struct __CFArray {
    CFRuntimeBase _base;
    CFIndex _count;		/* number of objects */
    CFIndex _mutations;
    void *_store;           /* can be NULL when MutableDeque */
};

deque(両端キュー)……!
それなら「先頭」と「末尾」への追加が定数時間で行えるのもうなずける。
この構造だけ見ると、環状バッファとして実装されている可能性も考えられるが……

CF_INLINE struct __CFArrayBucket *__CFArrayGetBucketAtIndex(CFArrayRef array, CFIndex idx) {
    switch (__CFArrayGetType(array)) {
    case __kCFArrayImmutable:
    case __kCFArrayDeque:
	return __CFArrayGetBucketsPtr(array) + idx;

ポインタにインデックスをただ加算して値を取り出しているのを見るに、値は先頭から末尾まで連続的に並んでいると考えて良いだろう。
つまりこれは環状バッファではない
値の並びを空き領域の真ん中に置き、その前後に値を追加していく。
もし値を追加する側に空きがなくなったら、値の並びを空き領域の真ん中の方にずらしたのち追加する。
そんな実装だ。

実のところ、前回計算時間を計測した時、このような実装も想定して

[array insertObject:number atIndex:count];
[array removeObjectAtIndex:0];

もテストしていた。
キャパシティがぎりぎりだから

  • 「要素数が少ない」と「再配置が頻発する」が「再配置する要素数が少ない」ため比較的速く
  • 「要素数が多い」と「再配置が頻発する」上「再配置する要素数が多い」ため比較的遅く

なると思ったのだ。
だが、実際はこれも定数時間で処理されてしまった。
なぜそんなことになったのか。

それは、キャパシティが実は2の乗数単位で確保されているためである。
そのため、要素数10000の時キャパシティは16384、要素数100000の時キャパシティは131072と、要素数が多いほど余裕が生まれ、

  • 「要素数が少ない」と「再配置が頻発する」が「再配置する要素数も少ない」
  • 「要素数が多い」と「再配置の頻度は少ない」が「再配置する要素数が多い」

ことで定数時間っぽくなったのだ。
なので、次のコードのように余裕が一定になるようにすると、追加/削除に要する時間がO(N)になることを確認できる。

void test2(unsigned int n)
{
	NSMutableArray* numbers = [NSMutableArray arrayWithCapacity:n + 1];
	for(unsigned int i = 0; i < n; i++)
	{
		[numbers addObject:[NSNumber numberWithInt:i]];
	}
	
	NSTimeInterval start, end;
	NSNumber* number = [NSNumber numberWithInt:n];
	
	start = [NSDate timeIntervalSinceReferenceDate];
	for(int i = 0; i < 1000000; i++)
	{
		[numbers insertObject:number atIndex:n];
		[numbers removeObjectAtIndex:0];
	}
	end = [NSDate timeIntervalSinceReferenceDate];
	NSLog(@"%d tail: %f", n, end - start);
	
	start = [NSDate timeIntervalSinceReferenceDate];
	for(int i = 0; i < 1000000 ; i++)
	{
		[numbers insertObject:number atIndex:0];
		[numbers removeObjectAtIndex:n];
	}
	end = [NSDate timeIntervalSinceReferenceDate];
	NSLog(@"%d head: %f", n, end - start);
}
for(NSUInteger i = 1024; i <= (1 << 16); i <<= 1)
{
	NSAutoreleasePool* pool = [[NSAutoreleasePool alloc] init];
	test2(i - 4);
	[pool drain];
}
1020 tail: 0.288747
1020 head: 0.333276
2044 tail: 0.346368
2044 head: 0.431503
4092 tail: 0.454933
4092 head: 0.616310
8188 tail: 0.808351
8188 head: 1.402597
16380 tail: 1.695329
16380 head: 3.848963
32764 tail: 3.140525
32764 head: 7.446001
65532 tail: 6.020166
65532 head: 14.685018

以上でCFArrayの説明は終わり。
将来はともかく、現在(MacOS 10.5.6)の可変CFArrayの実装は、常に両端キューである。
めでたしめでたし。

……いや。
実はCFArrayには、もう一つ重要な実装がある。

if (__CF_MAX_BUCKETS_PER_DEQUE <= futureCnt) {
   CFStorageRef store;
    __CFArrayConvertDequeToStore(array);
    store = (CFStorageRef)array->_store;
enum {
    __CF_MAX_BUCKETS_PER_DEQUE = 262140
};

CFStorageは平衡木。
__CFArrayConvertDequeToStore()は、CFArrayの実装を両端キューから平衡木に変換する。
つまり、CFArrayはキャパシティが2^18以上になると平衡木になるのである。
これは前回記事のtest()を2^17より大きい値で呼んでみればよく分かる。

test(1000000)
1000000      0: 2.321109
1000000 250000: 1.097532
1000000 500000: 1.071410
1000000 750000: 1.211316
1000000 1000000: 1.084863

また以下のページのグラフも参考になるだろう。
http://ridiculousfish.com/blog/archives/2005/12/23/array/

大量の要素を格納する時に限って平衡木を使っているのは、STLで言えば大量の要素を保持するにはvectorよりdequeの方が具合が良いと言われているのと同じ理由か。
それとも、再配置のコストが際限なく高まるのを嫌ったか。

平衡木になると、アクセス/追加/削除に必要な計算量は全てO(log N)になる。
「アクセス時間が最悪O(log N)」とか「効率的な位置は決まっていない」といった規定は、今、まさにこの実装のためにあったのだ。

スポンサーサイト

コメント

コメントの投稿

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

トラックバック

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

Appendix

タグ

Blog内検索

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