1

我最近写了这篇文章：
如何最好地在 c++ 中存储非常大的 2D 浮点列表？错误处理？

一些人建议我将我的 2D 类似列表的浮点结构实现为向量，其他人则说是双端队列。

从我收集到的向量需要连续的内存，但因此效率更高。显然，如果可能的话，这将是可取的。

因此，我的问题是关于基本结构可以有多长的一个好的规则是......

1. float
2. int

...在您应该从向量切换到双端队列以避免内存问题之前？

例如，我正在寻找类似“大约 400 万个浮点数或 800 万个整数，你应该切换......”的答案......如果可能的话。

4

7 回答 7

4

好吧，这里有两个意见。C++ 标准说 (23.1.1/2)：

vector是默认情况下应该使用的序列类型。

list应该在序列中间有频繁的插入和删除时使用。

deque是当大多数插入和删除发生在序列的开头或结尾时选择的数据结构。

Herb Sutter 提出以下观点（文章包含他的基本原理和性能分析）：

我想提出一个和蔼可亲的不同观点：我建议您考虑默认情况下更喜欢 deque 而不是 vector，尤其是当包含的类型是类或结构而不是内置类型时，除非您确实需要容器的内存来是连续的。

于 2010-09-17T19:36:07.197 回答
2

同样，没有大小限制，超过该大小的双端队列优于或不优于向量。在这两种情况下，内存碎片的含义几乎相同，除非您已经完成了大量的分配/解除分配并且没有足够的连续空间留给大向量。但这种情况非常罕见。请记住，内存空间是每个进程的（google for virtual memory）。reserve您可以通过在混乱发生之前（通过方法）为向量分配内存来解决它。

权衡取决于您想用它做什么。如果该结构基本上是不可变的，并且您只想通过索引访问来访问它/覆盖它，请选择向量。

双端队列是当您需要在末尾、开头或中间进行插入时，vector 无法自然地处理某些事情（除了在末尾插入）。

Herb Sutter 的文章总体上质量很好，但是您会注意到，当您在 C++ 中进行“数字运算”时，您在“通用 C++”书籍中学到的大部分内容都必须格外小心。您在使用双端队列时遇到的较差的索引性能可能对您的应用程序很重要。在这种情况下，不要使用双端队列。

于 2010-09-17T19:46:26.070 回答
2

如果您需要在开头插入，请使用双端队列。

否则，我总是喜欢指出这篇关于向量与双端队列的文章（除了 James McNellis 在这里链接的那些）。假设使用基于页面的分配的双端队列实现，本文对带有和不带保留（）的向量与双端队列的分配时间（和释放时间）进行了很好的比较。基本上，使用reserve() 使得向量分配时间与双端队列非常相似。如果您可以提前猜出正确的值以进行保留，则信息丰富且有用。

于 2010-09-17T19:52:15.590 回答
1

要考虑的因素太多，不可能给出明确的答案。机器上的内存量，它有多碎片化，它可能会变得多碎片化等等。我的建议是选择一个并使用它。如果它导致问题切换。无论如何，您可能不会遇到这些边缘情况。

如果你真的很担心，那么你可能会实现一种伪 PIMPL：

template<typename T>
class VectorDeque
{
private:
  enum TYPE { NONE, DEQUE, VECTOR };
  std::deque<T> m_d;
  std::vector<T> m_v;
  TYPE m_type;
  ...
public:
  void resize(size_t n)
  {
    switch(m_type)
    {
      case NONE:
      try
      {
        m_v.resize(n);
        m_type = VECTOR;
      }
      catch(std::bad_alloc &ba)
      {
        m_d.resize(n);
        m_type = DEQUE;
      }
      break;
    }
  }
};

但这似乎完全是矫枉过正。您是否进行过任何基准测试或测试？你有任何理由相信内存分配会失败或者双端队列会太慢吗？

于 2010-09-17T20:00:21.827 回答
1

您在测试后切换，并且分析表明对于您的应用程序来说，其中一个比另一个差。没有“大约 N 个浮点数或 M 个整数”的通用答案。

于 2010-09-17T20:23:32.360 回答
0

好吧，关于内存，我可以分享一些经验，可以帮助您确定连续内存块（malloc 或 std::vector）何时可能变得太大：

我使用的应用程序确实记录了测量数据，主要是 4byte float，为此它分配内部缓冲区来存储数据。这些缓冲区的大小差异很大，但典型的范围可能是几十个 1-10MB 和极少数大于 100MB 的缓冲区。缓冲区总是分配有calloc，即一大块内存。如果缓冲区分配失败，则会记录一个错误，并且用户可以选择重试。

缓冲区大小：假设您想以 100Hz 记录 1000 个频道 10 分钟：4byte x 1000 x 100 x 60x10 == 228 MB（大约）...或 100 个频道以 10Hz 记录 12 小时 == 41 MB

我们（几乎）在分配 40MB 缓冲区（大约 10 百万浮点数）时从来没有遇到过任何问题，而且 200-300 MB 缓冲区有时会失败——所有这些都在具有 4GB RAM 的普通 WinXP/32 位机器上。

于 2010-09-17T20:17:24.063 回答
0

鉴于您在创建后不插入，您可能应该使用普通的 old std::vector，或者如果碎片确实成为一个问题，则使用自定义的类似向量的Sequence实现为指向固定大小数组的向量或指针数组。

于 2010-09-17T20:20:32.300 回答