C++ Union-Find解决方案的性能非常差。

Question

( 问题摘要(USACO Gold 2016年2月3日))

给定一个(A,B)维数的直角坐标平面，存在N垂直栅栏和M水平栅栏。显然，在较大的矩形内这些栅栏的交集创建了(n+1)(m+1)区域。给定A,B,N,M，N垂直栅栏的x坐标和M水平栅栏的y坐标，找到要拆除的最小栅栏数量，以创建最小生成树(连接所有区域)。为了拆除一道篱笆，从而将两个相邻地区合并起来，必须拆除它们之间的整个围栏。

解决方案

这显然是一个不相交的集合联合问题( union -find/Kruskals)，但棘手的部分是构建边缘列表和树到并。每条边都由它所连接的两个节点之间的栅栏长度来加权。

下面是代码的简要概述：

1. 以x，y弦表示垂直、水平栅栏(加上0,0，A，B为“篱笆”)
2. 对于每一个栅栏的交点(一些特殊情况在末端)，添加左向和向上的边缘到边缘列表，另外添加两个边之间的区域作为一个节点到联合查找树。
3. 跑Kruskals，追踪距离。

这是一个O(ElogV)算法，它应该足够快，因为N和M小于2000。请注意，给定的解决方案(上面链接的)足够快，在最后的4/10测试用例中，这需要花费很长时间(失败)。

下载测试用例(10)

性能瓶颈在哪里？这又如何改善呢？

#include 
#include 
#include 
#include 
#include 

#define ll long long

using namespace std;

const string PROJ_NAME = "fencedin";

struct edge {
    ll dist;
    int start;
    int finish;
    bool operator< (const edge &rhs) const { return dist < rhs.dist || (!(rhs.dist < dist) && start < rhs.start) || (!(rhs.start < start) && finish < rhs.finish); }
};

struct uf_node {
    int parent;
    int level;
};

ll A, B;
int N, M;
set edge_list;
vector tree;

void make_edge_list(ifstream &fin){
    fin >> A >> B >> N >> M;

    vector vert(N+2);
    vert[0] = 0;
    for(int i = 1; i<=N; i++) fin >> vert[i];
    vert[N+1] = A;
    N++;

    vector hori(M+2);
    hori[0] = 0;
    for(int i = 1; i<=M; i++) fin >> hori[i];
    hori[M+1] = B;
    M++;

    sort(vert.begin(), vert.end());
    sort(hori.begin(), hori.end());

    tree.resize(N*M);
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            int curr = (i-1)*M+(j-1);

            //Add node to DSU tree
            uf_node n = {.parent = curr, .level = 0};
            tree[curr] = n;

            //Add leftward edge if not at bottom
            if(i != N){
                edge left = {.dist = hori[j]-hori[j-1], .start=curr, .finish=curr+M};
                edge_list.insert(left);
            }

            //Add upward edge if not at right
            if(j != M){
                edge up = {.dist = vert[i]-vert[i-1], .start=curr, .finish=curr+1};
                edge_list.insert(up);
            }
        }
    }
}

int find_par(int i) {
    if(i != tree[i].parent) {
        tree[i].parent = find_par(tree[i].parent);
    }
    return tree[i].parent;
}

void do_union(int i, int j) {
    int r = find_par(i);
    int s = find_par(j);
    if(r == s) return;
    else if (tree[r].level > tree[s].level) {
        tree[r].parent = s;
    } else if (tree[s].level > tree[r].level) {
        tree[s].parent = r;
    } else {
        tree[r].parent = s;
        tree[r].level += 1;
    }
}

int main()
{
    ifstream fin (PROJ_NAME + ".in");
    ofstream fout (PROJ_NAME + ".out");

    make_edge_list(fin);

    int total_dist = 0;
    for(edge e: edge_list){
        if(find_par(e.start) != find_par(e.finish)){
            do_union(e.start, e.finish);
            total_dist += e.dist;
        }
    }

    fout << total_dist << endl;
    return 0;
}

Answer 1

这是一个非常有趣的问题！下面是我注意到的关于您的实现的一些事情。

性能

看一看您的代码的概要文件(在macOS High上用Xcode 9.2编译了llvm )，看起来大部分时间都花在以下三个地方：

• 在make_edge_list()中，85%，特别是对set::insert()的2次调用
• 占find_par()的7%
• 在std::tree::iterator::operator++()中占7% (因此在边缘列表中增加一个迭代器，我相信)

我认为，这意味着在这种情况下，std::set可能不是容器的最佳选择。由于您不能像使用set或array那样为项目预先分配空间，所以它必须动态地进行分配，这可能会影响性能。此外，选择插入的位置似乎也是insert()时间接收器的一部分。使用vector，您可以预先分配内存，然后push_back()将其添加到末尾。现在还不清楚在这里使用set会得到什么，所以我说不要使用它了。链接解决方案只使用一个vector和一个静态数组~2000x2000元素，并进行一些排序。所以这可能是一种获胜的策略。

命名

宏有各种各样的问题。但是，即使您能够编写一个不会出现任何这些问题的宏，就像这里所做的那样，如果有更好的方法，也应该使用它。(例如，如果修改这段代码的人创建了一个名为ll的变量，或者写了一个包含单词"all“的字符串，该怎么办？)如果您希望自己的long long名称更短，请执行以下操作：

using ll = long long;

或者至少：

typedef long long ll;

但真的-太懒了不想输入long long？打出来就行了。这是个很有名的类型。

在大多数情况下，我不喜欢一个字母的可变名字。A和B值是维度。我给他们起名叫width和height。N和M是垂直和水平围栏的数目，那么为什么不给它们命名为num_vert_fences和num_horz_fences？甚至只有rows和columns？

避免using namespace std

你真的应该避免使用using namespace std，因为所有的理由都指出了。

Globals

全局词的使用使您很难阅读代码。在do_union()中，我必须一直滚动到文件的顶部，以查看tree的类型。您应该在main()中定义这些变量，并将它们传递给使用它们的函数。这将使您更容易理解程序流程，并避免某些函数更改某个变量时在另一个函数中使用相同变量时没有传递它的问题。

我在评论中提到，全球公司搞砸了我的业绩分析。这是全球性意外后果的一个很好的例子。由于代码运行得太快，无法进行分析，所以我将main()重命名为main2()，然后编写了一个新的main()，只需在一个循环中调用它100次。但是由于tree和edge_list是全球性的，当main2()退出的时候，他们并没有被清除，因为如果他们是本地的话，他们就会离开。因此，这导致了我的分析的数字是不正确的，因为容器可能有不同的特点，当有更多的项目，而不是当有更少。学到的教训。在运行性能测试之前，我应该将变量设置为本地变量。

使用不太知名的工具

时要小心

我非常喜欢这种初始化struct或union成员的方法：

uf_node n = {.parent = curr, .level = 0};

我最近开始使用它，有多年经验的同事一直对此表示惊讶和关注！所以只要知道你可能会把一些读者和它搞混。不过，这是我希望看到的那种东西，因为一旦你理解了它，它就会提高可读性。