Entries

スポンサーサイト

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

『みんなでスペランカー』をやってみた

てっきり、ただのネタリメイクだと思っていたのだが……これが思ったよりずっと力入れて作られていて、面白い。

先生は相変わらずの虚弱体質。事あるごとに死んでいく。
前作がどうだったかは覚えてないが、今作では最後にアイテムを拾ったところが復活ポイントになるので、下手な拾い方をすると復帰に多大なコスト(爆弾、フラッシュ、先生)を支払うことになったり、死ぬ前に打ち上げたフラッシュが復活した直後に降ってきてまた死ぬ。

ぽこぽこ死んでいく先生ではあるが、逆に増殖速度も半端なく(ステージクリア、得点、隠し1upで増える)、慎重に進めばトータルの収支はプラスになる。そんなわけで一人用1周目の難易度はさほど高くない。
2周目になると例によって鍵が見えなくなるが、そのくらいなら大した問題ではない。歩き回れば自然に集まる。
しかし鍵の位置はほとんど覚えていない(100ステージとか1回で覚えられん)ので、3周目以降、ジャンプやらフラッシュやらの行動が要求されるようになると、さすがに厳しそうだ。
(と思ったら3周目に入ってもジャンプは要求されず。一方通行ステージでハマるからだろうか)

で、オンラインモード「みんなで探検」。
これはもう死ぬ。なんか死ぬ。
とりあえず知り合い2人とボイスチャット付きでやってみたが、3倍以上の勢いで残機が減る。
他人が発動させたトラップのなんと恐ろしいこと……!
だが、面白い。とても面白い。
特に残機がなくなってからの救援システム(残機0で倒れても、生き残っている人が制限時間内に救助に駆けつければ何度でも助けられる)は、「ウィザードリィで一番好きなのは全滅したパーティを回収しに行くこと」な自分にはもうたまらない。

「スペランカーが好き」かつ「死んでも(゚ε゚)キニシナイ!!」人同士でプレイできていることもあるが、これは想像以上に楽しいゲームだ。

gcc 4.2と無名名前空間

タグ: C++ gcc
/// @file Hoge.h
#include <boost/scoped_ptr.hpp>

class Hoge
{
public:
    ~Hoge();
    
private:
    class Impl;
    boost::scoped_ptr<Impl> pimpl;
};
/// @file Hoge.cpp
#include "Hoge.h"

namespace {
struct Fuga {};
}

class Hoge::Impl
{
    Fuga fuga;
};

Hoge::~Hoge()
{
}

gcc 4.0向けに書いていた上記のコードをgcc 4.2.1でコンパイルしたところ、次のような警告を受けた。

Hoge.cpp:9: warning: ‘Hoge::Impl’ has a field ‘Hoge::Impl::fuga’ whose type uses the anonymous namespace

どうも「翻訳単位ローカルではないクラスが無名名前空間の構造体をメンバにしている」ことを注意しているようだが……マジか。
たしかに、「Fugaを含む無名名前空間」と「Hoge::Implの定義」が「複数の翻訳単位で参照される(つまりヘッダファイルに書かれている)」場合それは問題になる。
しかし、それを警戒するためにpimplと無名名前空間の蜜月の関係にまで茶々を入れるというのは、いささか大仰に過ぎるのではなかろうか。
そう思ってBugzillaを覗いてみると、案の定、この警告に関する問題が挙げられていた。

Bug 29365 - Unnecessary anonymous namespace warnings - GCC Bugzilla

すでにFIXEDとなっているので、「4.3系」と、あと「4.2.2以降(だと思う)」では対応がなされているらしい。
試しにgcc 4.3.3でビルドしてみたところ、たしかに上記のコードでは警告を受けなくなった。
ひとまず安心。

もっとも、開発環境の都合上、すぐさま新しいgccには移行できない。
この鬱陶しい警告とは、いましばらく付き合わなければならないようだ。

本日見かけた酷いコード12

タグ: C++ 酷いコード
class String : std::basic_string<char>
{
public:
    operator const char* () const;
};

String CreateVerboseName(const char*);

#if 0
const char HOGE[] = "hoge"
#else
#define HOGE CreateVerboseName("hoge")
#endif
void foo()
{
    char hoge[sizeof(HOGE)];
    sprintf(hoge, HOGE);

絶賛稼働中のシステムに含まれていたコード。

「関数foo()の追加」と「HOGEの定義変更」は、ほぼ同時期行われている。
おそらく、複数人による変更が嫌な具合に噛み合い、このような形になってしまったのだろう。

明らかに誤ったコードではあるが、 CreateVerboseName("hoge")sizeof(String) (VC8で32)文字未満の文字列しか返さないので、動作に支障はでていない。

03月06日のココロ日記(BlogPet)

いつか、する姿がほしいです。ココロの夢です。

*このエントリは、ブログペットのココロが書いてます♪

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は、やはり遅い。

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)」とか「効率的な位置は決まっていない」といった規定は、今、まさにこの実装のためにあったのだ。

Appendix

タグ

Blog内検索

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