Perfect Hash [プログラミング - NSSetとライフゲーム]
先日頂いたコメントのもうひとつのほうのおさらい。
ところで、コメントいただいたふたつのアイデアは、ぜひ実装してみたい。しかし僕がこんな頭いいアイデアを自分で思いつくということはないので、忘れた頃にコードを見て「なにやってんだ、これ?全然わからん」とかいいそう。ちゃんとメモを残しておかないと絶対言うに決まってる。もっとつまらないコードでも言ってるぐらいだし。
まず、コメントに書いていただいた関数、
例えば、NSSetは同じオブジェクトがひとつしか含まれないということを保証している。その同一性のチェックにメソッドのisEqual:とhashを使う。NSSetはまずhashメソッドを呼んで比較し、一致していればisEqual:メソッドで本当に一致しているかどうかを判断する。hashの効率が良ければisEqual:メソドを呼ぶのを減らすことができる。
hashは格納したオブジェクトをアクセスするのにも使われる。コレクションは多くのオブジェクトを保持できるようになっていなければならないけど、保持したオブジェクトの中から特定のオブジェクトを効率よく見つけ出すことも必要になる。
例えばオブジェクトを単純な配列に格納したとする。あるオブジェクトと同じものをその中から選び出そうとすると配列の先頭から順に一致するかどうかをテストすることになる。選び出すのにかかる平均時間は配列の長さつまりは保持しているオブジェクトの数に比例することになる。
そこで、配列をM個に分割する。N個のオブジェクトを保持していたとすると、ひとつの配列にあるオブジェクトをテストする時間はN/Mに減少する。しかしこのままではどの配列に期待しているオブジェクトがあるかどうかわからないので、結局M個の配列の中身を順に探すことになってその場合単純な1本の配列と同じことになってしまう。
ここでhashを使う。hashの値ごとに配列を用意する。hash値の一致しないオブジェクトはもともと同一性テストに合格しないので、チェックする必要はない。テスト対象のオブジェクトと同じhash値を持つ配列だけをチェックすればいい。選び出すのにかかる平均時間は1/Mになって劇的に効率が上がる。
絵に描けば図-1のような違いである。
図-1 1次元配列とhash table
hash値に対する配列の割り当ては例えばm = hash mod Mとしてmを配列のインデクスとすればいい。さらにMを2のベキにとればmはhash値の下位ビットを取り出す、という作業で簡単に作ることができる。
一方でhash値がどんなオブジェクトも同じ値、例えば0を返すとする。その場合すべてのオブジェクトがMの配列のうちの先頭のひとつに集中することになって、単純な1列の配列と同じになってしまう。同じようにhash値にバラツキがあって、ある値は頻出するけどある値は少ない、ということが起こっても似たような効率低下が発生する。ということでhash値を作り出す計算(hash関数という)はいろいろなオブジェクトに対してhash値をまんべんなく発生させることが必要になる。
セルの位置が決まればその値からkeyの値が計算でき、CFDictionaryにそのkeyを問い合わせればそのvalueがその位置にあるセルである、ということになる。またkeyが見つからなければその位置には生きているセルはない、ということになる。これは頭がいい。非常に面白い。
ようするにCFSetの代わりにCFDictionaryを使えば同一性の検索はまったく同じ効率で、しかもCFDictionaryにすればセルそのものはhash関数を知らなくてもいい、さらにCFSetのmember:メソッドを使うためにはセルのオブジェクトを生成する必要があるが、CFDictionaryだとそのhash値があるだけでいい、ということになる。すばらしい。
もちろん、keyはオブジェクトを指しているわけではないのでたとえば
MacOS Xの64ビットモードのアプリは基本的にLP64のデータモデルを採用していると「64-bit Transition Guide」にはっきり書いてある。
ところでこのドキュメントには「Common Misconceptionsよくある勘違い」として
Mac OS Xではアプリ用のFrameworkであるCocoaは、10.4で64ビット対応に書き換えられて新しくNSIntegerとNSUIntegerが定義され、これまでint、unsigned intだったところはほぼ全部これに置き換えられた。実はこの型は
ようするに「unixなひとはLP64でやってもらっていいよ、こっちはILP64だけどね」ということらしい。今時点ではただ余分にメモリを食うだけではっきり言ってデメリットしかない。あからさまにILP64にしなかったのは、現時点でそのモデルでは32ビット幅のデータを指定する方法がなくなる(shortは16ビットのままが普通なので)ということもありそうな気はする。
でもまあ、そのおかげで余裕の出る部分もあるのは事実である。例えば今回のようなint整数ふたつをひとつのlong int整数に詰め込んでNSUIntegerとして扱うということができる。さらにこれをポインタとみなすことも可能になる。もともとNSInteger/NSUIntegerをlong int/unsigned longにしたのはポインタ(アドレス値)と混在させている場面があったからかもしれない。Core Foundationのコードを見ればその証拠が見つかるかもしれない。machの作法なのか、I/O Kitなどでメモリ上の領域をさすのに(void *などではなく)unsigned intが使われることがある。
文字列にUnicodeが使われて8ビットデータを扱う場面は明らかに減っている。5年もすれば64ビットモードがあたりまえ(「昔は4GBしかメモリが積めなかったんだって?うゎ、狭っ!」)になり、バイト(8ビット)は入出力にしか使われなくなってcharが16ビットshortが32ビットintが64ビットということになるのかもしれない。
なんか今日はいっぱい書いてしまった。寝よ。
ところで、コメントいただいたふたつのアイデアは、ぜひ実装してみたい。しかし僕がこんな頭いいアイデアを自分で思いつくということはないので、忘れた頃にコードを見て「なにやってんだ、これ?全然わからん」とかいいそう。ちゃんとメモを残しておかないと絶対言うに決まってる。もっとつまらないコードでも言ってるぐらいだし。
まず、コメントに書いていただいた関数、
NS_INLINE int64_t AlternativeFilledBitsMake (int32_t _bits) { int64_t bits = (int64_t)_bits; bits = (bits | (bits << 16)) & 0x0000ffff0000ffff; bits = (bits | (bits << 8)) & 0x00ff00ff00ff00ff; bits = (bits | (bits << 4)) & 0x0f0f0f0f0f0f0f0f; bits = (bits | (bits << 2)) & 0x3333333333333333; bits = (bits | (bits << 1)) & 0x5555555555555555; return bits; }がなにをしているか、というと引数で渡されてきた整数のビットパターンが
abcdefghだとする(abc...は0か1として)と、この関数は
0a0b0c0d0e0f0g0hを返す。つまりビットの間に0を挿入して64ビット整数を作る。これを使って
altX = AlternativeFilledBitsMake(X); altY = AlternativeFilledBitsMake(Y); int64_t altBits = altX OR (altY << 1);とするとXとYがビットごとに歯車の歯のように入れ子になったものが作れる。これと単に
int64_t altBits = X OR (Y << 32);とした場合となにが違うか。それはhashの動作と関連している。
1 hashの一般論
hashはふたつのオブジェクトを比較するときに使う。hashの値が異なっていればオブジェクトは異なる、というような値を設定する。hash値が違っていればオブジェクト自身を比較する必要がない。特にオブジェクトの比較に時間がかかるもの、例えば長い文字列などでは文字列の比較をする前にhash値を比較しておけば無駄な作業を省くことができる。例えば、NSSetは同じオブジェクトがひとつしか含まれないということを保証している。その同一性のチェックにメソッドのisEqual:とhashを使う。NSSetはまずhashメソッドを呼んで比較し、一致していればisEqual:メソッドで本当に一致しているかどうかを判断する。hashの効率が良ければisEqual:メソドを呼ぶのを減らすことができる。
hashは格納したオブジェクトをアクセスするのにも使われる。コレクションは多くのオブジェクトを保持できるようになっていなければならないけど、保持したオブジェクトの中から特定のオブジェクトを効率よく見つけ出すことも必要になる。
例えばオブジェクトを単純な配列に格納したとする。あるオブジェクトと同じものをその中から選び出そうとすると配列の先頭から順に一致するかどうかをテストすることになる。選び出すのにかかる平均時間は配列の長さつまりは保持しているオブジェクトの数に比例することになる。
そこで、配列をM個に分割する。N個のオブジェクトを保持していたとすると、ひとつの配列にあるオブジェクトをテストする時間はN/Mに減少する。しかしこのままではどの配列に期待しているオブジェクトがあるかどうかわからないので、結局M個の配列の中身を順に探すことになってその場合単純な1本の配列と同じことになってしまう。
ここでhashを使う。hashの値ごとに配列を用意する。hash値の一致しないオブジェクトはもともと同一性テストに合格しないので、チェックする必要はない。テスト対象のオブジェクトと同じhash値を持つ配列だけをチェックすればいい。選び出すのにかかる平均時間は1/Mになって劇的に効率が上がる。
絵に描けば図-1のような違いである。
一方でhash値がどんなオブジェクトも同じ値、例えば0を返すとする。その場合すべてのオブジェクトがMの配列のうちの先頭のひとつに集中することになって、単純な1列の配列と同じになってしまう。同じようにhash値にバラツキがあって、ある値は頻出するけどある値は少ない、ということが起こっても似たような効率低下が発生する。ということでhash値を作り出す計算(hash関数という)はいろいろなオブジェクトに対してhash値をまんべんなく発生させることが必要になる。
2 もういちどコメントの内容に戻ると
Core Foundationのソース(CF-155.13)を見れば、CFDinctionaryはkeyの検索にCFSetとまったく同じ関数を呼んでいる。つまりCFSetが同一性チェックを行うのとCFDictionaryがkeyを取り出すのとはまったく同じである、ということ。示していただいたhash関数はperfect hashなのでCFDictionaryのkeyにhash値(ポインタの値だとみなして)を、valueにそのセルのオブジェクトを設定しておけば、keyが一致するということは同じ位置にあるセルがあるということになる。また、CFDictionaryはkeyにequalコールバックがない場合、そのアドレス値が一致することがkeyが一致することであるとみなし(これはNSObjectに定義されたisEqual:と同じ)て、そのアドレス値をhash値に使ってhash tableに収める。セルの位置が決まればその値からkeyの値が計算でき、CFDictionaryにそのkeyを問い合わせればそのvalueがその位置にあるセルである、ということになる。またkeyが見つからなければその位置には生きているセルはない、ということになる。これは頭がいい。非常に面白い。
ようするにCFSetの代わりにCFDictionaryを使えば同一性の検索はまったく同じ効率で、しかもCFDictionaryにすればセルそのものはhash関数を知らなくてもいい、さらにCFSetのmember:メソッドを使うためにはセルのオブジェクトを生成する必要があるが、CFDictionaryだとそのhash値があるだけでいい、ということになる。すばらしい。
もちろん、keyはオブジェクトを指しているわけではないのでたとえば
NSArray *keys = [cfSpecialDictionary allKeys];などとしたらいっきにクラッシュする。
3 unsigned intとvoid *の取り替えについて
実はこのhash関数がperfect hashとして機能するためにはintのビット幅の2倍がhash値およびポインタのビット幅になっていないといけない。64ビットモードでこれを満足するOSはあまりなくて、Mac OS Xは特殊な例。MacOS Xの64ビットモードのアプリは基本的にLP64のデータモデルを採用していると「64-bit Transition Guide」にはっきり書いてある。
Mac OS X uses two data models: ILP32 (in which integers, long integers, and pointers are 32-bit quantities) and LP64 (in which integers are 32-bit quantities, and long integers and pointers are 64-bit quantities). Other types are equivalent to their 32-bit counterparts (except for size_t and a few others that are defined based on the size of long integers or pointers).LP64というのはlong int型とポインタに64ビットを使う、ということでint型は32ビットのままである。ちなみにint型も64ビットとして扱うのをILP64という。普通のプログラミングをしていて2GB(あるいは4GB)を超えるデータを扱うことはあっても、ループをまわすカウンタに64ビット必要になるということは非常に稀である、という事実から64ビットモードでもLP64モデルが使われることが多い。MacOS Xもそれにならったということだろう。もちろん、OSがLP64モデルを採用しているからと言ってアプリも同じにしなければいけない、ということはなく、単にスタイルの問題と言っていい。しかしそろえておけばSystem Call(API)との受け渡しのときビット幅を調整する必要がなくて、効率は良くなる。
ところでこのドキュメントには「Common Misconceptionsよくある勘違い」として
- 64ビットデータを扱うなら64ビットモードにしないといけない
- 64ビットプロセサには64ビットモードでないと効率が悪い
- APIは全部64ビットコンパチに変更される
- アプリはみんな4GB以上のメモリが使えるようにしないといけない
- 64ビットネイティブだと速いアプリが作れる
Mac OS Xではアプリ用のFrameworkであるCocoaは、10.4で64ビット対応に書き換えられて新しくNSIntegerとNSUIntegerが定義され、これまでint、unsigned intだったところはほぼ全部これに置き換えられた。実はこの型は
#if __LP64__ || TARGET_OS_EMBEDDED || TARGET_OS_IPHONE || TARGET_OS_WIN32 || NS_BUILD_32_LIKE_64 typedef long NSInteger; typedef unsigned long NSUInteger; #else typedef int NSInteger; typedef unsigned int NSUInteger; #endifとNSObjCRuntime.hの中で定義されている。つまり64ビットモードではどちらも64ビット幅になる。Cocoaにでてくる整数はほぼ全部(例外はNSCondingやNSNumberなどすこし、しかも32びっとと64ビットを区別するようになっただけ)これに書き換えられ、従ってそれとToll-Freeで結ばれているCore Foundationも互換を取る形でCFIndexなどが64ビットに指定されている。Core FoundationはCベースの基本的なサービスでMacOS Xの広範な場面で使われている。OSのコアサービスのレベルでは32ビット整数が出現することはほとんど無くて、実質的にILP64だと言っていい。LP64というのは過渡的なデータモデルであって、OSとしては将来にわたって互換性を維持するために先取りしておくという認識なんだろう。そのわりにはすぐdeprecatedにするけど。
ようするに「unixなひとはLP64でやってもらっていいよ、こっちはILP64だけどね」ということらしい。今時点ではただ余分にメモリを食うだけではっきり言ってデメリットしかない。あからさまにILP64にしなかったのは、現時点でそのモデルでは32ビット幅のデータを指定する方法がなくなる(shortは16ビットのままが普通なので)ということもありそうな気はする。
でもまあ、そのおかげで余裕の出る部分もあるのは事実である。例えば今回のようなint整数ふたつをひとつのlong int整数に詰め込んでNSUIntegerとして扱うということができる。さらにこれをポインタとみなすことも可能になる。もともとNSInteger/NSUIntegerをlong int/unsigned longにしたのはポインタ(アドレス値)と混在させている場面があったからかもしれない。Core Foundationのコードを見ればその証拠が見つかるかもしれない。machの作法なのか、I/O Kitなどでメモリ上の領域をさすのに(void *などではなく)unsigned intが使われることがある。
文字列にUnicodeが使われて8ビットデータを扱う場面は明らかに減っている。5年もすれば64ビットモードがあたりまえ(「昔は4GBしかメモリが積めなかったんだって?うゎ、狭っ!」)になり、バイト(8ビット)は入出力にしか使われなくなってcharが16ビットshortが32ビットintが64ビットということになるのかもしれない。
なんか今日はいっぱい書いてしまった。寝よ。
2010-10-28 22:19
nice!(0)
コメント(4)
トラックバック(0)
AltFilledBits ですが修正します。こんなにおほめいただいたのですが、すみません。
問題点:入力値が負値のときにint64_tだと上位32ビットが1で埋まる。OR をとるので 0 であるべきところまで 1で埋まり、perfect でなくなる。
解決策:uint32, 64で入出力する。
手元の僕のコードでは unsigned になっているんですが、特に何も考えずに singed にして書き込んでしまいました。unsinedにしてるのは意味があったとは…我ながら困った脳みそです。コードにコメント書いとかないとダメですね。
NS_INLINE uint64_t AlternateFilledBitsMake (uint32_t _bits) {
uint64_t bits = (uint64_t)_bits;
bits = (bits | (bits << 16)) & 0x0000ffff0000ffff;
bits = (bits | (bits << 8)) & 0x00ff00ff00ff00ff;
bits = (bits | (bits << 4)) & 0x0f0f0f0f0f0f0f0f;
bits = (bits | (bits << 2)) & 0x3333333333333333;
bits = (bits | (bits << 1)) & 0x5555555555555555;
return bits;
}
あと、英語の話なのですが alternative より altenate の方がいいかな、と思いまして、関数名もついでに変更しました。重ねてお詫びを。
by SY (2010-10-29 16:20)
コメントありがとうございます。
負数に関してはその通りでした。
僕もスルーしていました。
そのままキャストすると「処理系に依存する」ということになるんでしたっけ?
関数やメソッドの名前は悩ましいですが、非常に重要だと思います。
誰かが言った「プログラミングとは名前をつけることだ」というのは、僕は慧眼だと思います。
機能に即した名前がついているとソースを読み下すだけで理解できたりします。そういうソースを読むと「えらいなあ」と思います。美しさとは別かもしれませんが。
ものによっては逆にミスリードさせられたり、a0、a1、a2...のほうがわかりやすかったりする(最近やたらと長い名前が多い)こともありますが...
by decafish (2010-10-29 21:34)
処理系に依存するかどうかについては詳しくないので分かりませんが、明示的にビットシフトやビットアンドで上位ビットをつぶした方が後で分かりやすいですね。今回のようなミスもなくせるし。
関数名やメソッド名についてはよく悩みます。後から変更して Xcode のリファクタリングのお世話になる事もしばしば。長くなってしまうのが難点ですが Cocoa の命名規約のおかげで、読み下しやすい名前を心がけるようになりました。補完機能がないとまた話が違うかもしれませんが(笑。ともあれ、もうちょっと英語ができるようになりたいです。
by SY (2010-10-31 11:34)
僕は歳をとってからなるべくビットパターンが見えるようなプログラミングはなるべく避けるようにしてきましたが、今回のような簡潔は表現はやはり面白くて、気持ちいいです。
Xcodeの補完機能はもう手放せません。ところが持ち歩き用のPowerBook G4では言うことをきいてくれなくて、かえって邪魔になったりして...
新しいMacBook Air欲しいなあ...かんけーないですけど。
by decafish (2010-10-31 22:13)