I want to design a fast container with fixed window size.
Here is the demo:
class SumFish { // i named this class Fish, because fish only has 7 seconds memory, quite like fixed window size
public:
SumFish(size_t N) : n_(N), sum_(0.) {}
void push(double v) {
data.push_back(v);
sum_ += v;
if (data_.size() > n_) {
sum_ -= v.front();
data_.pop_front();
}
}
double sum() const { return sum_; }
std::deque<double> data_;
double sum_;
};
I think it's good, since i can calculate the latest n elements' sum in O(1).
But for a container which need to calculate median in data stream.
I need to use two heap to make it in O(logn), I can do it in the push function, but i think it's not the best design, since if i have a Fish only want sum(), it still have heap operation, which cost more time.
So, i perfer to design a similiar class MedianFish:
class MedianFish {
public:
MedianFish(size_t N) : n_(N), sum_(0.) {}
void push(double v) { // I dont merge this with SumFish
// because it will cost more time, if i only used to calculate sum.
// compare, and do heap operation, i ignored
}
double median() const { return left_heap.front(); }
std::deque<double> data_;
double sum_;
};
I also want another Fish, which record data in my time range. please see the code:
class TimeFish {
public:
TimeFish(size_t N) : n_(N), sum_(0.) {}
void push(double ts, double val) { // please notice here, i use ts to control the container size
time_.emplace_back(ts);
data_.emplace_back(val);
sum_ += val;
if (time_.empty()) return;
double fore_ts = time_.front();
while (!data_.empty() && ts - fore_ts > size_) { // pop data if push ts - data.front.ts > N
double victim = data_.front();
sum_ -= victim;
data_.pop_front();
time_.pop_front();
if (!time_.empty()) fore_ts = time_.front();
}
}
std::deque<double> data_, time_;
};
util now, i have two different push method, TimeFish(pop data when time is > N) and SizeFish (pop when data size > N).
two function, Median and Sum, which i can combine out:
TimeSumFish, TimeMedianFish, SizeSumFish, SizeMedianFish.
i think there may be some design pattern can optimize my code, (decorator pattern seems match, but i dont know how to merge two push functions) because there is some duplicates code. (For example, TimeSumFish and TimeMedianFish will share the same push function)
Can you help on this?