Skip to content

Instantly share code, notes, and snippets.

@takei-yuya

takei-yuya/SlidingWindow.cpp Secret

Last active May 13, 2020
Embed
What would you like to do?
class SlidingWindow {
public:
explicit SlidingWindow(size_t least_docnum) : least_docnum_(least_docnum) {}
size_t Add(size_t lcp_len, uint64_t docid) {
docid_queue_.Push(docid);
lcp_len_queue_.Push(lcp_len);
if (docid_queue_.Cardinality() >= least_docnum_) { // enough docs
while (docid_queue_.Cardinality() >= least_docnum_) Shrink();
// LCP DOCID SEQUENCE Pre-Shrink Window Shrinked Window
// 0 1 AXXXX |
// 1 0 ABCDX |
// 4 1 ABCDY | |
// 3 2 ABCZ | |
// expected is 3
// LCPの先頭は無視したいので「条件を満たさなくなる直前」ではなくて、1つ進めた「条件を満たさなくなった直後」でLCPの最小値を取る。
return lcp_len_queue_.Min();
}
return 0; // not enough docs
}
private:
void Shrink() {
docid_queue_.Pop();
lcp_len_queue_.Pop();
}
size_t least_docnum_;
CardinalityQueue<size_t> docid_queue_;
MinQueue<size_t> lcp_len_queue_;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.