9

我有一个问题，我正在处理我需要使用某种二维数组的地方。该数组是固定宽度（四列），但我需要动态创建额外的行。

为此，我一直在使用向量的向量，并且一直在使用一些包含以下内容的嵌套循环：

array.push_back(vector<float>(4));
array[n][0] = a;
array[n][1] = b;
array[n][2] = c;
array[n][3] = d;
n++

添加行及其内容。问题是我试图创建的元素数量似乎已经耗尽了内存，所以我减少了我正在使用的数量。但后来我开始阅读关于双端队列的内容，并认为它可以让我使用更多的内存，因为它不必是连续的。在这个循环中，我将所有提到的“vector”以及所有声明都更改为“deque”。但后来似乎我的内存又用完了，这一次即使行数减少了。

我查看了我的代码使用了多少内存，当我使用双端队列时，内存稳步上升到 2GB 以上，并且程序很快关闭，即使使用较少的行数也是如此。我不确定内存不足时该循环的确切位置。

当我使用向量时，即使循环退出，内存使用量（对于相同数量的行）仍然低于 1GB。然后它继续进行类似的循环，其中添加了更多行，但仍仅达到约 1.4GB。

所以我的问题是。这对于双端队列使用超过向量两倍的内存是正常的，还是我在认为我可以在声明/初始化和上述代码中将“向量”一词替换为“双端队列”时做出错误的假设？

提前致谢。

我正在使用：MS Visual C++ 2010（32 位）Windows 7（64 位）

4

5 回答 5

6

这里真正的答案与核心数据结构无关。答案是 MSVC 的 std::deque 实现特别糟糕，并且退化为指向单个元素的指针数组，而不是它应该是的数组数组。坦率地说，vector 的内存使用量只有两倍是令人惊讶的。如果你有更好的双端队列实现，你会得到更好的结果。

于 2013-04-27T12:55:19.127 回答
5

这一切都取决于内部实现deque（我不会谈论，vector因为它相对简单）。

事实是，deque它具有完全不同的保证vector（最重要的是它支持两端的 O(1) 插入，而vector只支持后面的 O(1) 插入）。这反过来意味着管理的内部结构deque必须比vector.

为了实现这一点，典型的deque实现会将其内存分成几个不连续的块。但是每个单独的内存块都有一个固定的开销来允许内存管理工作（例如，无论块的大小，系统可能需要另外的 16 或 32 字节或其他任何额外的字节，仅用于簿记）。由于与 a不同vector， adeque需要许多小的独立块，因此开销会累积起来，这可以解释您看到的差异。另请注意，需要管理这些单独的内存块（可能在单独的结构中？），这也可能意味着一些（或很多）额外的开销。

至于解决问题的方法，您可以尝试@BasileStarynkevitch 在评论中建议的方法，这确实会减少您的内存使用量，但它只会让您到目前为止，因为在某些时候您仍然会耗尽内存。如果你试图在只有 256MB RAM 的机器上运行你的程序呢？任何其他旨在减少内存占用同时仍试图将所有数据保存在内存中的解决方案都会遇到同样的问题。

在处理像您这样的大型数据集时，一个适当的解决方案是调整您的算法和数据结构，以便能够在整个数据集的时间处理小分区，并根据需要加载/保存这些分区，以便为其他分区。不幸的是，因为这可能意味着磁盘访问，这也意味着性能的大幅下降，但是嘿，你不能吃蛋糕也有它。

于 2013-04-27T12:52:09.353 回答
5

理论

有两种有效实现双端队列的常用方法：使用修改后的动态数组或使用双向链表。

修改后的动态数组使用基本上是一个可以从两端增长的动态数组，有时称为数组 deques。这些数组双端队列具有动态数组的所有属性，例如恒定时间随机访问，良好的引用局部性，中间插入/删除效率低下，在两端增加了分摊的恒定时间插入/删除，而不是只是一端。

修改后的动态数组有几种实现：

  1. 从底层数组的中心分配双端队列内容，并在到达任一端时调整底层数组的大小。这种方法可能需要更频繁地调整大小并浪费更多空间，尤其是当元素仅插入一端时。

  2. 将双端队列内容存储在循环缓冲区中，并且仅在缓冲区变满时调整大小。这降低了调整大小的频率。

  3. 将内容存储在多个较小的数组中，根据需要在开头或结尾分配额外的数组。索引是通过保持一个包含指向每个较小数组的指针的动态数组来实现的。

结论

不同的库可能以不同的方式实现双端队列，但通常作为修改后的动态数组。您的标准库很可能使用方法#1 来实现std::deque，并且由于您仅从一端附加元素，因此最终会浪费大量空间。因此，它会产生一种std::deque比平时占用更多空间的错觉std::vector。

此外，如果std::deque将实现为双向链表，这也会导致空间浪费，因为除了自定义数据之外，每个元素还需要容纳 2 个指针。

使用方法#3（修改后的动态数组方法）的实现将再次导致空间浪费以容纳额外的元数据，例如指向所有这些小数组的指针。

无论如何，std::deque就存储而言，效率不如普通 old std::vector。在不知道您想要实现什么的情况下，我无法自信地建议您需要哪种数据结构。但是，您似乎甚至不知道双端队列的用途，因此，您在这种情况下真正想要的是std::vector. 通常，双端队列有不同的应用。

于 2013-04-27T12:52:29.167 回答
3

与向量相比，双端队列可能有额外的内存开销，因为它是由几个块而不是连续的块组成的。

从en.cppreference.com/w/cpp/container/deque：

与 相反std::vector，a 的元素deque不是连续存储的：典型的实现使用一系列单独分配的固定大小的数组。

于 2013-04-27T12:50:16.890 回答
1

主要问题是内存不足。

那么，您是否需要一次将所有数据存储在内存中？
你可能永远无法做到这一点。

部分处理

您可能需要考虑将数据处理成“块”或更小的子矩阵。例如，使用标准矩形网格：

  • 读取第一象限的数据。
  • 处理第一象限的数据。
  • 存储第一象限的结果（在文件中）。
  • 对剩余的象限重复。

搜索

如果您正在搜索一个粒子或一组数据，则无需将整个数据集读入内存即可。

  1. 分配一个内存块（数组）。
  2. 将部分数据读入这块内存。
  3. 搜索数据块。
  4. 重复步骤 2 和 3，直到找到数据。

流数据

如果您的应用程序从输入源（不是文件）接收原始数据，您将需要存储数据以供以后处理。

这将需要一个以上的缓冲区，并且使用至少两个执行线程更有效。

读取线程将数据读取到缓冲区中，直到缓冲区已满。当缓冲区已满时，它会将数据读入另一个空的缓冲区。

写入线程最初将等待，直到第一个读取缓冲区已满或读取操作完成。接下来，写入线程从读取缓冲区中取出数据并写入文件。然后写入线程从下一个读取缓冲区开始写入。

这种技术称为双缓冲或多缓冲。

稀疏数据

如果矩阵中有很多零数据或未使用的数据，您应该尝试使用稀疏矩阵。本质上，这是一个保存数据坐标和值的结构列表。当大多数数据是非零的公共值时，这也适用。这样可以节省大量内存空间；但会花费更多的执行时间。

数据压缩

您还可以更改算法以使用数据压缩。这里的想法是存储数据位置、值和数量或连续相等的值（又名运行）。因此，您将存储（运行的）起始位置、值和 100 作为数量，而不是存储 100 个相同值的连续数据点。这节省了大量空间，但在访问数据时需要更多的处理时间。

内存映射文件

有些库可以将文件视为内存。本质上，它们将文件的“页面”读入内存。当请求离开“页面”时，它们会读入另一个页面。所有这一切都是在“幕后”进行的。您需要做的就是将文件视为内存。

概括

数组和双端队列不是您的主要问题，数据量才是。您的主要问题可以通过一次处理小块数据、压缩数据存储或将文件中的数据视为内存来解决。如果您正在尝试处理流数据，请不要。理想情况下，应将流数据放入文件中，然后再进行处理。文件的历史目的是包含不适合内存的数据。

于 2013-04-27T16:59:02.910 回答