nlib
nn::nlib::succinct::SparseSet クラスfinal

疎な64bit符号なし整数の集合を保持する簡潔データ構造です。 [詳解]

#include "nn/nlib/succinct/Sbv.h"

公開型

typedef uint64_t IdxType
 インデックスとなる整数型のtypedefです。
 

公開メンバ関数

bool Build () noexcept
 Rank/Select辞書を構築します。 [詳解]
 
bool Has (uint64_t idx, uint32_t *rank) const noexcept
 値が集合に含まれているかどうかをテストします。 [詳解]
 
bool Has (uint64_t idx) const noexcept
 値が集合に含まれているかどうかをテストします。 [詳解]
 
size_t MemSize () const noexcept
 このクラスが明示的に確保するメモリ量を返します。 [詳解]
 
uint64_t GetBitVectorSize () const noexcept
 ビットベクトルのサイズを返します。 [詳解]
 
void Reset () noexcept
 オブジェクトをコンストラクタが呼ばれた直後の状態にします。
 
基本的なメンバ関数
 SparseSet () noexcept
 コンストラクタです。
 
 ~SparseSet () noexcept
 デストラクタです。
 
 SparseSet (SparseSet &&rhs) noexcept
 ムーブコンストラクタです。C++11の利用時に有効です。
 
SparseSetoperator= (SparseSet &&rhs) noexcept
 ムーブ代入演算子です。C++11の利用時に有効です。
 
void swap (SparseSet &rhs) noexcept
 オブジェクトの内容をスワップします。
 
整数集合の構築

Build()の実行前に利用します。

bool Init (uint64_t bv_size) noexcept
 オブジェクトを初期化します。 [詳解]
 
bool TurnOn (uint64_t idx) noexcept
 集合に64bit符号なし整数を追加します。 [詳解]
 
RankとSelect操作

Build()の実行後に利用します。

uint32_t Rank1 (uint64_t idx) const noexcept
 Rank操作を行います。 [詳解]
 
uint32_t Rank0 (uint64_t idx) const noexcept
 Rank操作を行います。 [詳解]
 
int32_t Select1 (uint32_t nth) const noexcept
 nth 番目の要素の値を返します。nthは0から開始します。 [詳解]
 
int64_t Select1Ex (uint32_t nth) const noexcept
 nth 番目の要素の値を返します。nth は0から開始します。 [詳解]
 
インポートとエクスポート
bool Export (BinaryWriter *w) const noexcept
 オブジェクトを(ファイルに)書き出します。 [詳解]
 
bool Import (BinaryReader *r) noexcept
 書き出されたオブジェクトを読み出します。 [詳解]
 

詳解

疎な64bit符号なし整数の集合を保持する簡潔データ構造です。

説明
以下の論文で説明されている、sdarrayを実装しています。
疎な集合の場合、SetSbvよりも小さなメモリ領域でRank/Select操作をサポートした整数の集合(ビットベクトル)をサポートします。 疎な集合というのは、目安としては、全体の10パーセントかそれ以下がONになっている集合と考えてください。
このクラスを用いた場合Select操作が \(O(1)\)で可能となります。 Rank操作はNを定義域の大きさ( Init()に渡すbvSize)とすると、おおよそ \(O(\log N)\)となります。
また、集合にある整数が含まれているかどうはを判断する操作(Has())は直観と異なり、Rank操作を実行した後にSelect操作を実行しているので両者より低速になります。
このクラスの利用方法は、以下のとおりです。
  1. コンストラクタでオブジェクトを作成します。
  2. Init()で定義域を設定してビットベクトルを初期化します。
  3. TurnOn()で整数を集合に加えます。
  4. Build()Rank/Select操作を定数時間で行うための辞書を構築します。
  5. 以上でRank/Select操作が利用できるようになります。
データをExport()で書きだした場合はコンストラクタの実行後にImport()を呼び出すことで利用できるようになります。

Sbv.h100 行目に定義があります。

関数詳解

§ Build()

nn::nlib::succinct::SparseSet::Build ( )
noexcept

Rank/Select辞書を構築します。

戻り値
成功した場合はtrue

§ Export()

nn::nlib::succinct::SparseSet::Export ( BinaryWriter w) const
noexcept

オブジェクトを(ファイルに)書き出します。

引数
[in]w書き出し用オブジェクト
戻り値
成功した場合はtrue
説明
書きだしたデータはImport()関数で読みだして復元することができます。 また、データは常にリトルエンディアンで書き出されます。

§ GetBitVectorSize()

nn::nlib::succinct::SparseSet::GetBitVectorSize ( ) const
inlinenoexcept

ビットベクトルのサイズを返します。

戻り値
集合の定義域のサイズ(ビットベクトルのサイズ)
説明
Init()関数に渡した値と同じ値を返します。

Sbv.h141 行目に定義があります。

§ Has() [1/2]

nn::nlib::succinct::SparseSet::Has ( uint64_t  idx,
uint32_t *  rank 
) const
inlinenoexcept

値が集合に含まれているかどうかをテストします。

引数
[in]idx64bit符号なし整数
[out]rankNULLでなければランク値が格納されます
戻り値
集合にidx が含まれている場合はtrue
説明
内部でRank操作とSelect操作を実行しています。 引数のrankNULLでない場合はRank計算の結果が格納されます。

Sbv.h120 行目に定義があります。

§ Has() [2/2]

nn::nlib::succinct::SparseSet::Has ( uint64_t  idx) const
inlinenoexcept

値が集合に含まれているかどうかをテストします。

引数
[in]idx64bit符号なし整数
戻り値
集合にidx が含まれている場合はtrue

Sbv.h130 行目に定義があります。

§ Import()

nn::nlib::succinct::SparseSet::Import ( BinaryReader r)
noexcept

書き出されたオブジェクトを読み出します。

引数
[in]r読み出し用オブジェクト
戻り値
インポートが成功した場合はtrue

§ Init()

nn::nlib::succinct::SparseSet::Init ( uint64_t  bv_size)
noexcept

オブジェクトを初期化します。

引数
[in]bv_sizeビットベクトルのサイズ。
戻り値
成功した場合はtrue
説明
0以上bvSize 未満の値を集合に加えることができるようになります。

§ MemSize()

nn::nlib::succinct::SparseSet::MemSize ( ) const
noexcept

このクラスが明示的に確保するメモリ量を返します。

戻り値
バイト数
説明
実際にシステムが確保するメモリ量はアライメントやヒープの管理領域の関係上この関数の返り値より大きい可能性があります。

§ Rank0()

nn::nlib::succinct::SparseSet::Rank0 ( uint64_t  idx) const
inlinenoexcept

Rank操作を行います。

引数
[in]idx64bit符号なし整数
戻り値
集合に含まれないidx 以下の値の数
説明
idx 以下の値で集合に含まれない要素の数を返します。 すわなち、ビットベクトル[0 .. idx]内に含まれる1の数を返します。 この操作は \(O(1)\)で行われます。

Sbv.h134 行目に定義があります。

§ Rank1()

nn::nlib::succinct::SparseSet::Rank1 ( uint64_t  idx) const
noexcept

Rank操作を行います。

引数
[in]idx64bit符号なし整数
戻り値
集合に含まれるidx 以下の値の数
説明
集合内のidx 以下の値の数を返します。 すわなち、ビットベクトル[0 .. idx]内に含まれる1の数を返します。 この操作は \(O(1)\)で行われます。

§ Select1()

nn::nlib::succinct::SparseSet::Select1 ( uint32_t  nth) const
noexcept

nth 番目の要素の値を返します。nthは0から開始します。

引数
[in]nth0以上の32bit整数
戻り値
nth 番目(基数は0)の要素が存在するならばその値。なければ-1
説明
すなわち、ビットベクトルのnth 番目のONになっっているビットの位置を返します。 この操作は \(O(1)\)で行われます。64bitの値を返す可能性がある場合にはSelect1Ex() 関数を利用してください。

§ Select1Ex()

nn::nlib::succinct::SparseSet::Select1Ex ( uint32_t  nth) const
noexcept

nth 番目の要素の値を返します。nth は0から開始します。

引数
[in]nth0以上の整数
戻り値
nth 番目(基数は0)の要素が存在するならばその値。なければ-1
説明
すなわち、ビットベクトルのnth 番目のONになっっているビットの位置を返します。 この操作は \(O(1)\)で行われます。

§ TurnOn()

nn::nlib::succinct::SparseSet::TurnOn ( uint64_t  idx)
noexcept

集合に64bit符号なし整数を追加します。

引数
[in]idx集合に加える整数
戻り値
成功した場合はtrue
説明
具体的にはビットベクトル内のidx に該当する部分をONにします。

このクラス詳解は次のファイルから抽出されました: