疎な64bit符号なし整数の集合を保持する簡潔データ構造です。
[詳解]
#include "nn/nlib/succinct/Sbv.h"
|
typedef uint64_t | IdxType |
| インデックスとなる整数型のtypedef です。
|
|
疎な64bit符号なし整数の集合を保持する簡潔データ構造です。
- 説明
- 以下の論文で説明されている、
sdarray
を実装しています。
- 疎な集合の場合、
Set
やSbv
よりも小さなメモリ領域でRank/Select
操作をサポートした整数の集合(ビットベクトル)をサポートします。 疎な集合というのは、目安としては、全体の10パーセントかそれ以下がONになっている集合と考えてください。
- このクラスを用いた場合
Select
操作が \(O(1)\)で可能となります。 Rank
操作はNを定義域の大きさ( Init()
に渡すbvSize)とすると、おおよそ \(O(\log N)\)となります。
- また、集合にある整数が含まれているかどうはを判断する操作(
Has()
)は直観と異なり、Rank
操作を実行した後にSelect
操作を実行しているので両者より低速になります。
- このクラスの利用方法は、以下のとおりです。
-
コンストラクタでオブジェクトを作成します。
-
Init()
で定義域を設定してビットベクトルを初期化します。
-
TurnOn()
で整数を集合に加えます。
-
Build()
でRank/Select
操作を定数時間で行うための辞書を構築します。
-
以上で
Rank/Select
操作が利用できるようになります。
- データを
Export()
で書きだした場合はコンストラクタの実行後にImport()
を呼び出すことで利用できるようになります。
Sbv.h の 402 行目に定義があります。
nn::nlib::succinct::SparseSet::Build |
( |
| ) |
|
|
noexcept |
Rank/Select辞書を構築します。
- 戻り値
- 成功した場合は
true
nn::nlib::succinct::SparseSet::Export |
( |
BinaryWriter * |
w | ) |
const |
|
noexcept |
オブジェクトを(ファイルに)書き出します。
- 引数
-
- 戻り値
- 成功した場合は
true
- 説明
- 書きだしたデータは
Import()
関数で読みだして復元することができます。 また、データは常にリトルエンディアンで書き出されます。
nn::nlib::succinct::SparseSet::GetBitVectorSize |
( |
| ) |
const |
|
inlinenoexcept |
ビットベクトルのサイズを返します。
- 戻り値
- 集合の定義域のサイズ(ビットベクトルのサイズ)
- 説明
Init()
関数に渡した値と同じ値を返します。
Sbv.h の 457 行目に定義があります。
nn::nlib::succinct::SparseSet::Has |
( |
uint64_t |
idx, |
|
|
uint32_t * |
rank |
|
) |
| const |
|
inlinenoexcept |
値が集合に含まれているかどうかをテストします。
- 引数
-
[in] | idx | 64bit符号なし整数 |
[out] | rank | NULL でなければランク値が格納されます |
- 戻り値
- 集合に
idx
が含まれている場合はtrue
- 説明
- 内部で
Rank
操作とSelect
操作を実行しています。 引数のrank
がNULL
でない場合はRank
計算の結果が格納されます。
Sbv.h の 436 行目に定義があります。
nn::nlib::succinct::SparseSet::Has |
( |
uint64_t |
idx | ) |
const |
|
inlinenoexcept |
値が集合に含まれているかどうかをテストします。
- 引数
-
- 戻り値
- 集合に
idx
が含まれている場合はtrue
Sbv.h の 446 行目に定義があります。
書き出されたオブジェクトを読み出します。
- 引数
-
- 戻り値
- インポートが成功した場合は
true
nn::nlib::succinct::SparseSet::Init |
( |
uint64_t |
bv_size | ) |
|
|
noexcept |
オブジェクトを初期化します。
- 引数
-
- 戻り値
- 成功した場合は
true
- 説明
0
以上bvSize
未満の値を集合に加えることができるようになります。
nn::nlib::succinct::SparseSet::MemSize |
( |
| ) |
const |
|
noexcept |
このクラスが明示的に確保するメモリ量を返します。
- 戻り値
- バイト数
- 説明
- 実際にシステムが確保するメモリ量はアライメントやヒープの管理領域の関係上この関数の返り値より大きい可能性があります。
nn::nlib::succinct::SparseSet::Rank0 |
( |
uint64_t |
idx | ) |
const |
|
inlinenoexcept |
Rank
操作を行います。
- 引数
-
- 戻り値
- 集合に含まれない
idx
以下の値の数
- 説明
idx
以下の値で集合に含まれない要素の数を返します。 すわなち、ビットベクトル[0 .. idx]内に含まれる1の数を返します。 この操作は \(O(1)\)で行われます。
Sbv.h の 450 行目に定義があります。
nn::nlib::succinct::SparseSet::Rank1 |
( |
uint64_t |
idx | ) |
const |
|
noexcept |
Rank
操作を行います。
- 引数
-
- 戻り値
- 集合に含まれる
idx
以下の値の数
- 説明
- 集合内の
idx
以下の値の数を返します。 すわなち、ビットベクトル[0 .. idx]内に含まれる1の数を返します。 この操作は \(O(1)\)で行われます。
nn::nlib::succinct::SparseSet::Select1 |
( |
uint32_t |
nth | ) |
const |
|
noexcept |
nth
番目の要素の値を返します。nthは0から開始します。
- 引数
-
- 戻り値
nth
番目(基数は0)の要素が存在するならばその値。なければ-1
- 説明
- すなわち、ビットベクトルの
nth
番目のONになっっているビットの位置を返します。 この操作は \(O(1)\)で行われます。64bitの値を返す可能性がある場合にはSelect1Ex()
関数を利用してください。
nn::nlib::succinct::SparseSet::Select1Ex |
( |
uint32_t |
nth | ) |
const |
|
noexcept |
nth
番目の要素の値を返します。nth
は0から開始します。
- 引数
-
- 戻り値
nth
番目(基数は0)の要素が存在するならばその値。なければ-1
- 説明
- すなわち、ビットベクトルの
nth
番目のONになっっているビットの位置を返します。 この操作は \(O(1)\)で行われます。
nn::nlib::succinct::SparseSet::TurnOn |
( |
uint64_t |
idx | ) |
|
|
noexcept |
集合に64bit符号なし整数を追加します。
- 引数
-
- 戻り値
- 成功した場合は
true
- 説明
- 具体的にはビットベクトル内の
idx
に該当する部分をONにします。
このクラス詳解は次のファイルから抽出されました: