nlib
succinct/bitvector/bitvector.cpp
SmartBitmapを用いてコンパクトな整数リストを実装するサンプルです。
例えば、何らかのIDの集合を持ちたい場合、リストやstd::setの利用が考えられますが、それらは比較的メモリを消費することと動的なメモリ管理を要するという欠点があります。
ここでIDの最大値が分かっていれば、ビットベクトルを用いることでとてもコンパクトにデータを格納することができます。 SmartBitmapはビットベクトルに対して少量のデータを付加することでデータの数え上げや検索を効率よく行うことができるようにしています。
/*--------------------------------------------------------------------------------*
Project: CrossRoad
Copyright (C)Nintendo All rights reserved.
These coded instructions, statements, and computer programs contain proprietary
information of Nintendo and/or its licensed developers and are protected by
national and international copyright laws. They may not be disclosed to third
parties or copied or duplicated in any form, in whole or in part, without the
prior written consent of Nintendo.
The content herein is highly confidential and should be handled accordingly.
*--------------------------------------------------------------------------------*/
// Implements a list(set) of integers by SmartBitmap
class ItemList {
public:
static const size_t kNumItem = 1024;
int GetNextItem(uint32_t n) const {
// Rank1(n) computes the count of '1' bits in [0, n].
// Select1(r) computes the index for the (r + 1)th '1' bit.
// you can compute the place of the net '1' bit.
return bitmap_.Select1(bitmap_.Rank1(n));
}
int GetPrevItem(uint32_t n) const {
unsigned int r = bitmap_.Rank1(n);
if (r == 0) return -1;
return bitmap_.Select1(r - 1);
}
size_t GetNumItems() const { return bitmap_.Rank1(kNumItem); }
bool Find(uint32_t n) const { return bitmap_.Has(n); }
int FindNth(uint32_t nth) const { return bitmap_.Select1(nth); }
void Set(uint32_t n) { bitmap_.Set(n); }
void Unset(uint32_t n) { bitmap_.Unset(n); }
private:
SmartBitmap<kNumItem> bitmap_;
};
bool SampleMain(int, char**) {
ItemList item_list;
// Set 0, 5, 10, 15, 20, ....., 995
for (int i = 0; i < 200; ++i) item_list.Set(i * 5);
// The size of SmartBitmap<kNumItem> would be about (kNumItem * 1.4 / 8) bytes.
// It is smaller than array or list.
nlib_printf("sizeof NumList: %" PRIuS "\n", sizeof(item_list));
// Gets the count of the numbers 'item_list' has. The time complexity is O(1).
nlib_printf(" %" PRIuS "\n", item_list.GetNumItems());
// Retrieves the 50th smallest value. The time complexity is Log(kNumItem).
nlib_printf("50th value is %d\n", item_list.FindNth(50 - 1));
// The next value of 500 is 505.
nlib_printf("next(500) is %d\n", item_list.GetNextItem(500));
// Inserts 501 into item_list. The time complexity is O(1).
item_list.Set(501);
nlib_printf("501 inserted\n");
// The next value of 500 is 505 now.
nlib_printf("next(500) is %d\n", item_list.GetNextItem(500));
return true;
}
NLIB_MAINFUNC