はじめに
プログラミング言語Goを読んでいて、ビットベクトルを利用してSetを実装するところがありました。 シンプルかつ思いつきもしない方法だったので紹介します。
プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)
- 作者:Alan A.A. Donovan,Brian W. Kernighan
- 発売日: 2016/06/20
- メディア: 単行本(ソフトカバー)
過去に以下の記事でGoでのSetの実装について触れましたが、ビットベクトルを扱う方法には触れていませんでした。
ビットベクトル
プログラミング言語Goではuint型のSetが実装されていました。
構造体としては、[]uint64
がSetを表します。
indexが0の場合は0~63がSetに含まれているか、indexが1の場合は64~127がSetに含まれているかを表します。
ビットが1であれば、その数値はSetに含まれていることを表します。
以下の表は、集合{0,1,2,3,64,65,68,69}
を表します(表中の・・・が全て0の場合)。
index | uint64(ビット表記) |
---|---|
0 | 00000・・・001111 |
1 | 00000・・・110011 |
セットの要素が負でない小さな整数で、セットが多数の要素を持ち、和集合や共通集合など集合操作がよく行われる場合では、ビットベクトルによるSetは効果的です。
実装
type IntSet struct { words []uint64 } func (s *IntSet) Has(x int) bool { word, bit := x/64, uint(x%64) return word < len(s.words) && s.words[word]&(1<<bit) != 0 } func (s *IntSet) Add(x int) { word, bit := x/64, uint(x%64) for word >= len(s.words) { s.words = append(s.words, 0) } s.words[word] |= 1 << bit } func (s *IntSet) Remove(x int) { word, bit := x/64, uint(x%64) if word > len(s.words) { return } s.words[word] &= ^(1 << bit) } func (s *IntSet) UnionWith(t *IntSet) { for i, tword := range t.words { if i < len(s.words) { s.words[i] |= tword } else { s.words = append(s.words, tword) } } } func (s *IntSet) IntersectWith(t *IntSet) { for i, sword := range s.words { sword &= t.words[i] } s.words = s.words[:len(t.words)] }
正の整数以外の場合
負の数を含む場合やstring型の場合でも、正の整数へマッピングすることでビットベクトル形式のSetを表現できるのではないかと思います。 負の数の場合は、負の数にならないように足せば解決できそうです。 string型の場合は、何らかの関数で数値に変換して正の整数へマッピングすることが可能です。 しかし、uint64型で全ての文字列を表現することが不可能なのは自明です。 そのため、集合に含まれていないが含まれていると判断してしまう偽陽性が発生します。 2年前に記事にした確率的データ構造であるブルームフィルタと似ているなと思いました。