1

这是一个名为 的类的构造函数Graph。在构造函数中，我试图初始化一些东西，这是可以工作的构造函数，即它运行并完成：

Graph(const float density, const int numVertex = 50): numEdges(0) {
        graph.resize(numVertex, vector<Vertex>(numVertex));
        for (int s = 0; s < numVertex; ++s) {
            for (int k = 0; k < s; ++k )
                if (edge_exist(density)) {
                    graph[s][k].visited = graph[k][s].visited = false;
                    graph[s][k].distance = graph[k][s].distance = _MAX;
                    ++numEdges;
                    int distance = rand() % 10 + 1;
                    graph[s][k].edges.emplace_back(piiv(distance, graph[k][s]));
                    graph[k][s].edges.emplace_back(piiv(distance, graph[s][k]));
                }
        }       
    }
typedef pair<int, Vertex> piiv;
vector<vector<Vertex> > graph;

该类有一个名为的字段graph，它是名为 的结构向量的向量Vertex。

typedef struct vert {
    std::list<std::pair<int, vert> > edges;
    int distance;
    bool visited;
} Vertex;

现在，如果我让顶点结构保持原样，而是使向量只是一个一维向量

vector<Vertex> graph;

并将构造函数更改为：

Graph(const float density, const int numVertex = 50): numEdges(0) {
        graph.resize(numVertex);
        for (int s = 0; s < numVertex; ++s) {
            for (int k = 0; k < s; ++k )
                if (edge_exist(density)) {
                    graph[s].visited = graph[k].visited = false;
                    graph[s].distance = graph[k].distance = _MAX;
                    ++numEdges;
                    int distance = rand() % 10 + 1;
                    graph[s].edges.emplace_back(piiv(distance, graph[k]));
                    graph[k].edges.emplace_back(piiv(distance, graph[s]));
                }
        }       
    }

现在，这种更改导致代码运行的时间比它通常在向量是二维时的运行时间要长得多。我没有耐心弄清楚它运行了多长时间，但我知道它的运行速度比第一个慢得多，而且没有明显的原因。对我来说不是很明显，但我敢打赌这里有人对为什么会这样有一些见解。

所以我的问题是，是什么导致程序出现这种看似不必要的延迟？如果有帮助，这就是构造函数的调用方式：

Graph G(0.4);

我已经跟踪到问题来自第二个构造函数实现中的最后两行：

graph[s].edges.emplace_back(piiv(distance, graph[k]));
graph[k].edges.emplace_back(piiv(distance, graph[s]));

所以我想真正的问题是上面的内容与第一个构造函数中所做的有什么不同？

编辑

答对了！ 在调试时，我决定将 Vertex 结构更改为这样声明：

typedef struct vert {
    std::list<std::pair<int, vert&> > edges;
    int distance;
    bool visited;
} Vertex;

这似乎解决了问题，但为什么呢？与按引用传递相比，为什么按值传递 Vertex 对象不起作用？

4

1 回答 1

0

@Joe Z很好地总结了发生这种情况的原因。

std::list<std::pair<int, vert> > edges;

通过将边声明为other按值Vertex包含 other 的列表，这意味着每次将新顶点添加到列表中时，复制构造函数立即启动并开始制作所有该边的副本，这也意味着复制那个的所有孩子等等......Vertex vertVertex

正如你所看到的，这种永不满足的复制意味着随着图变得越来越密集，我们的复制需要更多的时间，如果我们决定在图中引入一个循环，上帝会帮助我们，因为这意味着我们将在这个程序完成之前耗尽内存.

将属性更改edges为具有此类型：

std::list<std::pair<int, vert&> > edges;

现在这意味着每次我们向图中添加一条新边时，我们只需维护对其他顶点的引用，而不是复制它们。这也意味着我们实际上可以检测到何时从另一个顶点中删除了一条边。

此外，我实际上将这个边缘定义为：

std::list<std::pair<int, const vert&> > edges;

这只是一个好的做法，因为我们要确保边是不可变的，并且对另一个顶点的引用并不意味着能够改变它的属性。

于 2019-11-21T05:53:49.673 回答