Bitvectorの使用: x10編

大規模なデータを高速かつ低メモリ使用量で扱うために、bitvectorがよく使われている。
今回は、自分のコードを修正するにあたって、初めて使って見たので、ポスティングする。

bitvectorの実現方法って色々あるらしいが、今回は kw bitsというものを実装した。

概念

まず、bitvectorが何かを説明すると、これはbitarrayとも呼ばれ、通常integer、booleanなどprimitive typeで
表していたものを、bit単位でインパクとに格納するデータ構造である。
(ps: この概念はあくまでは自分でまとめたものでどれまであっているかは自身がない ^_^)

例えば、ある購買サイトの顧客(顧客数: n)がプレミアム会員か否かの情報を扱うとする。この時、普段はbooleanやintegerのarrayで表すことだが、bitvectorはこれらの情報bit単位で表そうとする。つまり、あるinteger(x10の場合32bits)の変数において、32人の情報を扱うことができ、i番目のbit値が 0 か 1 によってi番目のプレミアム会員か否かが表せる。

なので、x10のinteger型で有無を表す時、n*32 bitsほどのメモリが必要だったのが、bitvectorを使うことで、
(n / 32 + 1 )*32 bitsぐらいのメモリで上の情報を表すことができる。

(ps: 実際にはこんな場面で使わないだろうし、応用面として、Linuxのpriority queueや memory page locationなどで使われているらいが、今回は分かりやすくするため、こんないいかけんな例を挙げる。)

実装

bitvectorを使う場合、主な操作はあるか否かの判定操作と値の設定操作になる。

上の例で、顧客数が130人で、integer型を使って情報を扱うとする。すると、サイズ5のinteger型 arrayで扱うことができる(130/32+1=5)。

val A = new Array[int](5, 0);

この場合、i番目の人の情報は、index=i/32, bitpos=i%32により、A[index]のbitpos番目の位置に格納されているのが明らかになる。なので、結局判定と設定操作は以下の２つのbit演算で計算できる。

1.判定
V = A[index] & (1 << (bitpos-1))
- V = 0 (bitpos目の値 0)
- V > 0 (bitpos目の値 1)
2.設定
V = A[index] | (1 << (bitpos-1))
- bitpos目の値を1にする

ソースコード

bit_sample.x10

import x10.util.*;
public class bit_sample {
    public static def main(args: Array[String]) {   
        val n = 130;
        val rnd = new Random();
        val info = new Array[int](n/32+1, (i:int)=>rnd.nextInt());

        //operate the 10th value
        val i = 10; 
        val index  = i / 32;
        val bitpos = i % 32 - 1;

        //Check value
        Console.OUT.println("Bit value(10) = " + (info(index)&(1<<bitpos)));
        //Set value
        if ((info(index)&(1<<bitpos))==0) {
            if ((info(index)|(1<<bitpos)) != info(index)) 
                Console.OUT.println("Bit value be setted! ");
            else 
                Console.OUT.println("Bit value not be setted! ");
        }
    }
}