什么是一个好的数据结构为24小时分钟布尔记录 [英] What's a good data structure for a 24hr minute-by-minute boolean record

问题描述

我的任务是创建一个数据结构，保存最后24小时的每分钟的布尔值。 （事件X发生了吗？）我需要一直保持最后24小时。 （即，将不断添加数据，旧数据弹出。）数据将保留到闪存驱动器。我们在一个嵌入式平台，但内存不限于（我有128MB可用），碎片可能会成为一个问题，虽然。这是一个实时系统，但由于记录是每分钟，因此没有运行时约​​束。

I am tasked to create a data structure that holds a boolean for every minute of the last 24hrs. (Did event X occur?) I need to keep the last 24hrs all the time. (That is, data will constantly be added, old data popped off.) The data is to be persisted to a flash drive. We are on an embedded platform, but memory isn't that limited (I have 128MB available), fragmentation might become a problem, though. This is a realtime system, but since the record is per minute, there's little runtime constraints.

界面可能如下所示：

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 位每个使用60分钟一小时。后者是当前持久化的最爱。

What would be a good data structure to store the actual data in? My current favorites are std::deque<bool> and an array of 24 long long, with 60 of their 64 bits each used for the 60mins of an hour. The latter is the current favorite for persistence.

我想我对这两个想法的利弊有一个很好的想法，但希望你们中的一些能够提供额外的内容，甚至更多的想法。

I think I have a pretty good idea about the pros and cons of both ideas, but would hope some of you could provide additional insides and maybe even more ideas.

P.S .:这是严格的C ++ 03 + TR1 + Boost 1.52，没有C ++ 11/14可用。

P.S.: This is strictly C++03 + TR1 + Boost 1.52, no C++11/14 available.

推荐答案

正如Marius Bancila建议的在注释，然后在答案（请去和upvote答案，他给出的结果是解决方案）， std :: bitset<> 是理想的。但是，由于他的回答相当模糊，我决定发布一个更具体的描述我最后使用：

As was suggested by Marius Bancila first in a comment and then in an answer (please go and upvote that answer, he gave the hint that turned out to be the solution), std::bitset<> is ideal for this. However, since his answer is rather vague, I decided to post a more concrete description of what I ended up using:

class x_record {
  public:
    void record_entry(bool x_occured) {
      record_ <<= 1;
      record_[0] = x_occurred;
    }

    unsigned int x_occurance_minutes() const {
      return record_.count();
    }

    void write_to(std::ostream& os) const {
      os << m_overload_minutes.to_string();
    }

    void read_from(std::istream& is) const {
      std::string bits;
      is >> std::setw(minutes_to_keep) >> bits;
      if( !is || bits.size()!=minutes_to_keep )
        throw std::runtime_error("invalid file format");

      record_ = std::bitset<60*24>(bits);
    }

  private:
    std::bitset<60*24>  record_;
};

正如你所看到的， std :: bitset<> 几乎是我需要的。此外，持久化数据非常容易。

As you can see, std::bitset<> is pretty much exactly what I needed. Also, persisting the data is very easy.

当然，在现实中，这是一个更复杂的 ¹ ，但原则上这是真的。

Of course, in reality, this was a bit more complex¹, but in principle this is indeed the whole thing.

感谢大家努力帮助我！

Thanks to everyone for trying to help me!

¹ 事实证明，每隔几个月调用 x_occurance_minutes（） msecs， record_.count（）似乎有一些开销，所以我在 record_entry（）每分钟一次），并缓存结果。

¹ It turned out that it was easier to call x_occurance_minutes() every few msecs, for which record_.count() seemed quite some overhead, so I called it in record_entry() (called once per minute only) instead and cached the result.

这篇关于什么是一个好的数据结构为24小时分钟布尔记录的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！