Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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

More than 5 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です。

keroxp
iOS/Android/Unity/Node.js/Rails/Go/フロントエンド/SRE プログラマ
http://scrapbox.io/keroxp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away