mardi 21 décembre 2021

How to design a flexible container with latest n elements?

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?

Aucun commentaire:

Enregistrer un commentaire