对于24小时一分钟的布尔记录,什么是良好的数据结构

Question

我的任务是创建一个数据结构,在过去24小时的每一分钟都保存一个布尔值.(事件X发生了吗？)我需要一直保持最后24小时.(即,将不断添加数据,弹出旧数据.)数据将持久保存到闪存驱动器.我们在嵌入式平台上,但内存不是那么有限(我有128MB可用),但碎片可能会成为一个问题.这是一个实时系统,但由于记录是每分钟,因此几乎没有运行时限制.

界面看起来像这样:

class x_record {
  public:
    // record whether or not x occurred this minute
    void record_entry(bool x_occured);

    // how many minutes has x occured in the last 24hrs? 
    unsigned int x_occurance_minutes() const;

  private:
    // HERE BE DRAGONS 
};

存储实际数据的好数据结构是什么？我目前最喜欢的是std::deque<bool>24个阵列,long long其64个中的60个每个用于60分钟的一小时.后者是目前持久性的最爱.

我想我对这两个想法的优点和缺点都有一个很好的想法,但希望你们中的一些人可以提供额外的内部,甚至更多的想法.

PS:这是严格的C++ 03 + TR1 + Boost 1.52,没有C++ 11/14可用.

Answer 1

要详细说明vector<bool>版本,我认为这是一个非常好的主意,因为你总是存储相同数量的数据(这至少是我理解的):

class x_record {
   vector<bool> data;
   unsigned int currentMinute;

public:
   x_record(): data(24*60, false), currentMinute(0){}

   // record whether or not x occurred this minute
   void record_entry(bool x_occured){
      data[currentMinute] = x_occured;
      currentMinute = (currentMinute+1)%data.size();
   }

};

这样,向量大小是常量,因此不应该被分段(因为它是同时分配的).您可以使用currentMinute变量跟踪当前分钟.当您填写的所有字段,你只需将其设置为0与%(24*60)和覆盖旧数据,因为你不需要它.

您也可以使用普通数组而不是a vector<bool>,但是这需要更多的空间(因为通常C++ bool以与a相同的方式存储值char),或者在我看来 - 在我们看到的时候重新发明轮子的一些位操作vector<bool>专业化.

Answer 2

循环缓冲区:

int countBits(std::uint32_t v) {
  // source: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
  typedef std::uint32_t T;
  v = v - ((v >> 1) & (T)~(T)0/3);                           // temp
  v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
  v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
  return (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count
}

class x_record {
  public:
    x_record() { std::memset(&history, 0, sizeof(history)); }

    // record whether or not x occurred this minute
    void record_entry(bool x_occured) {
      uint64_t mask = 1 << (bit % 32);
      uint64_t set = x_occured ? mask : 0;
      history[bit / 32] = (history[bit / 32] & ~mask) | set;

      bit = (bit + 1) % (24*60);
    }

    // how many minutes has x occured in the last 24hrs? 
    int x_occurance_minutes() const {
      int count = 0;
      for (int i=0; i<45; ++i) {
        count += countBits(history[i]);
      }
      return count;
    }

  private:
    std::uint32_t history[45];
    short bit = 0;
};