c++ - 使用 std::stack 和 std::map 内存使用率意外高

Question

我正在尝试遍历一棵树，以便访问 4x4 滑动拼图的所有可能状态。我写的算法最初是递归的，但由于(显然)非常深的树，这被证明是不可能的。它崩溃并报告了段错误。然后我决定重写算法以迭代地完成它的工作，据我所知，它工作得很好。然而，一段时间后，由于交换，它开始大幅减速。我做了一些计算，但无法弄清楚所有这些内存使用量来自哪里......

代码贴在下面，但这里是重要的功能:

• std::stack<char, std::vector<char>> stack
• std::map<unsigned long long, int> distanceTable

假设 stack 的内存占用与它包含的元素数量成正比，并假设 map 相同(其中一个元素是 pair<unsigned long long, int> )，我打印出预期的内存占用量:

cout << (stack.size() * sizeof(char) +
         distanceTable.size() * sizeof(pair<unsigned long long, int>))/(1<<20) << "MB\n";

并将输出与 top 的输出进行比较.当我自己的程序报告大约 500MB 时，top报告说它使用了我所有内存的一半以上 (4GB)。这是我的推理无法解释的因素 4。我在这里缺少什么？

代码:

#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <sstream>
#include "slider.h"
using namespace std;

typedef Slider<4> Slider4;
typedef Slider4::Move Move;
typedef map<unsigned long long, int> Map;
typedef stack<char, std::vector<char>> Stack;

Move const moves[] = {Slider4::N, Slider4::S, Slider4::E, Slider4::W};
Move const opposite[] = {Slider4::S, Slider4::N, Slider4::W, Slider4::E};

int const moveIdx[] = {0, 1, 2, 3};
int const oppositeIdx[] = {1, 0, 3, 2};


Map generateDistanceTable()
{
    // non-recursive tree-walker to generate the distance-table
    Map distanceTable;
    Stack stack;
    Slider4 slider;
    unsigned long long depth = 1;

    stack.push(-1);
    distanceTable[slider.hash()]= depth;
    while (depth != 0)
    {
        cout << (stack.size() * sizeof(char) + 
                 distanceTable.size() * sizeof(pair<unsigned long long, int>))/(1ULL<<20) << "MB\n";

        int currentMove = stack.top() + 1;

        // find next move
        while (currentMove != 4)
        {
            // Try the move
            if (!slider.move(moves[currentMove]))
            {
                ++currentMove;
                continue;
            }

            // Check the current state of the puzzle
            auto &d = distanceTable[slider.hash()];
            if (d != 0)
            { // already encountered this state -> move back
                int undoMove = oppositeIdx[currentMove];
                slider.moveUnsafe(moves[undoMove]);
                ++currentMove; // try next move
                continue;
            } 

            stack.push(currentMove);
            d = ++depth;
            currentMove = 0;
        }

        if (currentMove == 4)
        {
            int undoMove = oppositeIdx[stack.top()];
            slider.moveUnsafe(moves[undoMove]);
            --depth;
            stack.pop();
        }
    }
}

int main()
{
    Map table = generateDistanceTable();
}

Answer 1

首先，std::map 特别低效内存使用。您插入的每个值都将放在一个单独的节点，除了值之外，通常包含三个指针和一些附加信息(MS 中的 2 char执行)。此外，每个节点通常分配分开，所以分配器所需的额外开销必须被添加。在 32 位系统上，总开销为至少 20 个字节；在 64 位系统上，40。

至于 std::vector(它是你的 std::stack 的基础)，它是好多了，但是如果你不使用 reserve 来预分配，它会不时重新分配，通常将容量乘以 1.5 或 2。这意味着它可能最终占用比必要更多的内存。 (还，根据分配模式，系统可能不会能够有效地重用期间释放的内存重新分配。)

不过，通常更喜欢使用 std::vector，保存在使用 std::lower_bound 而不是 std::map 进行排序。

最后，如果您事先确切知道有多少条目vector 将具有或可以建立一些合理的上限，您可以使用 reserve 进行预分配。这避免了任何风险尺寸加倍。