Posted at

ビットマスクを使ってBooleanの配列のサイズを1/32にする

More than 3 years have passed since last update.

JavaScriptである大きな配列の要素について、それぞれtrueかfalseで表現したいことがあります(?)

例えば、ある640x640の画像データ(ImageData)のピクセルごとの二値化のマスクを保持したい時、普通に考えたら以下の様なコードを書いてしまいます。


js


var mask = new Array(640*640);
for (var i = 0; i < mask.length; i=i+1|0) {
mask[i] = false;
}


JavaScriptの配列の実装は処理系によって違いますが、型を持たないjsの配列に関して初期化時のサイズの設定はメモリアロケーション上あまり意味を持ちません。

ちょっとjsに詳しい人ならこう書くかもしれません。


js


var mask = new Uint8ClampedArray(640*640);
for (var i = 0; i < mask.length; i=i+1|0) {
mask[i] = false;
}


真偽値の配列というものはjsでは定義できないので、整数の配列でメモリを節約しようという考えですね。

この場合、TypedArrayを使うことでメモリの確保をコントロールでき、メモリフレンドリになります。

しかし、そもそもUint8は8ビット=1byte, Cでいうchar型です。

真偽値を表したいのだから、そんなに大きなサイズはいりません。

そこで、ビットマスクを使って長さを1/8にしてみます。


BinraryArray.js


var BinaryArray = function(size) {
this.size = size;
this.mArray = new Uint32Array(Math.ceil(size));
}
BinaryArray.prototype.get = function(i) {
return mArray[0|i/32] >>> i%32 & 1 === 1;
}
BinaryArray.prototype.set = function(i,flag) {
return mArray[0|i/32] |= flag ? 1 : 0 << i%32;
}


アイデアは単純で、32bit整数ならば32個の真偽値を保持できるので、実際の長さの1/32の配列で済むのです。あとはアクセッサでビット演算してやればOK。

jsのTypedArrayは最初に設定したsize以上の値へのアクセスは常にundefined, 書き込みは評価値は帰ってくるものの実際の書き込みは無効となるのでこの実装で問題ないはずです。

なぜUint8ClampedArrayではなくUint32Arrayを使っているかというと...配列の長さが短い(8/32=1/4)のでメモリアロケーションがこっちのほうが速い(?)と思ったからですが実際は分かりません。

タイトルですが、ちょっと釣りかも?

長さは1/32になっていますが、たぶんメモリのサイズで言うと1/8だと思います。

そんな細かいこと気にしててJSerやってられんの?っていうツッコミはなしでお願いします。ちなみに私はHaxerです。