How to design a flexible container with latest n elements?

Viewed 41

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?

0 Answers
Related