2013/10/03

bitset

Gaucheプログラミングの小ネタ。

小さい非負整数の集合同士のintersectionを高速に計算しないとならない用事が出来た。 例えば (0 1 4 7 9) と (2 3 7 8 9 16) から (7 9) を求める、 といった話。データは100万個のオーダー。 整数値の範囲は今のところ最大でも50くらい、 今後増えることはありえるがそう極端に大きくはならない。

こういう話なら、整数の集合をビット集合に変換してビット毎のandを取るのが素直だろう。

整数値のリストからビット集合への変換はfoldですぐできる。

(define (integer-list->bitset ints)
  (fold (cut copy-bit <> <> #t) 0 ints)))

gosh> (integer-list->bitset '(0 3 4 9 15))
33305

ビット集合からリストに戻す方はどうだろう。srfi-60のinteger->listを 使うと整数の各ビットをbooleanにしたリストが得られるが、 右から0,1,2,...と数えないとならないので一旦reverseするのがちと煩わしい。

(define (bitset->integer-list bits)
  (filter-map (^[b n] (and b n)) 
              (reverse (integer->list bits))
              (lrange 0)))

gosh> (bitset->integer-list 33305)
(0 3 4 9 15)

gauche.genreator には整数を真偽値のジェネレータに変換する手続きがある。 bits->generatorは右からビットを取り出すのでそのまま使えるけど、 ジェネレータをリストに変換してやらないとならない。

(define (bitset->integer-list2 bits)
  (filter-map (^[b n] (and b n))
              (generator->list (bits->generator bits))
              (lrange 0)))

あるいは、ジェネレータのまま変換していって最後にリストに戻すか。

(define (bitset->integer-list3 bits)
  (generator->list
   (gfilter-map (^[b n] (and b n))
                (bits->generator bits)
                (grange 0))))

結果を整数の集合と考えるなら数値の順序はどうでも良いはずだ。 それならば、先に最大ビット番号を求めておいて、そこから逆順に畳み込む手もある。 そしたらinteger->list の結果をそのまま使える。 ただ、逆順の整数リストを作るのがちと煩わしい。

(define (bitset->integer-list4 bits)
  (let1 len (integer-length bits)
    (filter-map (^[b n] (and b n))
                (integer->list bits)
                (iota len (- len 1) -1))))

gosh> (bitset->integer-list4 33305)
(15 9 4 3 0)

さてどれが速いだろうか。適当にランダムデータを生成してベンチマーク。

(use data.random)
(use gauche.time)

(let1 testdata (generator->list (integers$ (expt 2 50)) 100000)
  ($ time-these/report 1
     `((srfi-60 . ,(^[] (for-each bitset->integer-list testdata)))
       (gen1    . ,(^[] (for-each bitset->integer-list2 testdata)))
       (gen2    . ,(^[] (for-each bitset->integer-list3 testdata)))
       (rev     . ,(^[] (for-each bitset->integer-list4 testdata))))))

結果:

Benchmark: ran srfi-60, gen1, gen2, rev, each for 1 times.
  srfi-60: 4.384 real, 4.380 cpu (4.370 user + 0.010 sys)@0.23/s n=1
     gen1: 3.865 real, 3.860 cpu (3.860 user + 0.000 sys)@0.26/s n=1
     gen2: 5.648 real, 5.650 cpu (5.650 user + 0.000 sys)@0.18/s n=1
      rev: 3.510 real, 3.510 cpu (3.510 user + 0.000 sys)@0.28/s n=1

          Rate srfi-60  gen1  gen2   rev
  srfi-60  0/s      -- 0.881 1.290 0.801
     gen1  0/s   1.135    -- 1.464 0.909
     gen2  0/s   0.775 0.683    -- 0.621
      rev  0/s   1.248 1.100 1.610    --

data.random は新しいモジュールで、ランダムデータの生成ツールが色々 揃っている。integer$ は0から与えられた数までの間の整数値を 一様分布で生成するジェネレータを作る関数。ここでは条件を揃えるために 一旦リストに直して各関数に与えた。

最後のやつは、lrange で降順のシーケンスが作れないので iotaを使うためにちょっとごちゃっとしたんだけど、lrangeで 降順のシーケンスを作れないようにしたのは何でだったかな? 何か理由があって 意識的にそうした覚えがあるんだけど…

Tags: Programming, Gauche