最近讀一些論文的時候，學到 Sparse Set 資料結構。我覺得這個資料結構的設計還蠻有趣的，所以花一點時間把他記錄下來。
Sparse Set 是一個儲存非負整數集合 {0, 1, 2, ... n - 1} 的資料結構。
- 初始化的時間複雜度是 O(M)。這個資料結構本身只需要 O(1) 的初始化時間。M 是記憶體分配器配罝大小為
2 * n * sizeof(unsigned)位元組的未初始化空間所需的時間。對大多數記憶體分配器而言，O(M) 可以視同 O(1)。 - 增加一個成員的時間複雜度為 O(1)
- 刪除一個成員的時間複雜度為 O(1)
- 刪除所有成員的時間複雜度為 O(1)
- 列舉所有成員所需的時間複雜度為 O(k)，其中 k 是成員的個數。
C++ 的類別定義如下：
class SparseSet {
private:
std::unique_ptr<unsigned[]> sparse_;
std::unique_ptr<unsigned[]> dense_;
unsigned num_members_;
public:
SparseSet(unsigned n);
bool has(unsigned x) const;
void insert(unsigned x);
void remove(unsigned x);
void clear();
const unsigned *begin() const;
const unsigned *end() const;
};
這個資料結構的重點是：
- 如果整數 x 在集合內，則
dense_[sparse_[x]] == x。
更準確的說，這個資料結構會維護以下的不變量（Invariant）：
num_members_是在集合內元素的個數。dense_[i]- 如果
i < num_members_，則一定是一個在集合內的整數。 - 如果
i >= num_members_，則應視為一個垃圾值。
- 如果
sparse_[i]可能是成員i在dense_陳列的索引，也可能是一個垃圾值。這個值只有在sparse_[i] < num_members_且dense_[sparse_[i]] == i時是有意義的。
初始化的程式碼如下：
SparseSet::SparseSet(unsigned n)
: sparse_(new unsigned[n]),
dense_(new unsigned[n]),
num_members_(0) {}
值得一提，上面的程式碼是使用 new unsigned[n] 配置記憶體。它回傳的是未初始化的記憶體。我們的建構式並不需要初始化他。
判斷整數 x 是否在集合內的程式碼如下：
bool SparseSet::has(unsigned x) const {
unsigned idx = sparse_[x];
return (idx < num_members_ && dense_[idx] == x);
}
增加一個成員的程式碼如下：
void SparseSet::insert(unsigned x) {
unsigned idx = sparse_[x];
if (idx >= num_members_ || dense_[idx] != x) {
sparse_[x] = num_members_;
dense_[num_members_] = x;
++num_members_;
}
}
刪除一個成員的程式碼如下：
void SparseSet::remove(unsigned x) {
unsigned idx = sparse_[x];
if (idx < num_members_ && dense_[idx] == x) {
if (idx < num_members_ - 1) {
int other = dense_[num_members_ - 1];
sparse_[other] = idx;
dense_[idx] = other;
}
--num_members_;
}
}
附帶一提，這段程式碼處理了二個不同的情況：
- 被刪掉的成員是
dense_的最後一個元素時，減少num_members_即可。 - 被刪掉的成員不是
dense_的最後一個元素時，我們必須要交換dense_[idx]和dense_[num_members_ - 1]。
因為第一個情況中，自己和自己交換並不影響正確性。所以我們也可以把 --num_members_ 移到 if 判斷之前，並以 num_members_ 取代 num_members_ - 1，最後再省掉 if 判斷。
接下來，刪除所有成員的程式碼如下：
void SparseSet::clear() {
num_members_ = 0;
}
要迭代所有成員，只需走訪 dense_ 陣列：
const unsigned *SparseSet::begin() const {
return dense_.get();
}
const unsigned *SparseSet::end() const {
return dense_.get() + num_members_;
}
參考資料
- Preston Briggs and Linda Torczon, An Efficient Representation for Sparse Sets
