6
\$\begingroup\$

I'm trying to speed up my union-find disjoint set data structure. The idea is that initially n sets of single element sets are made, and put into a vector nodes. Each node has a parent node, and the highest parent of any particular index in the vector is the highest ranking member of set. Two concepts, union by rank and path compression, are used to achieve faster merging and finding times.

There are two querying types: Union of two values (and thus their sets), and checking if 2 members are in the same set.

Nevertheless, when using very large values for n (such as 100,000,000) and and m (such as 1,000,000), the program takes a bit of time to run. Generally around 30 seconds for my machine.

#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>

using namespace std;


int n; //number of total elements
int q; //number of queries

struct node
{
    int data;
    node* parent;
    int rank;
    node(int d);
};

node::node(int d)
{
    data = d;
    rank = 0;
    parent = nullptr;
}

node* find(node* root)
{
    if (root != root->parent)
        root->parent = find(root->parent);
    return root->parent;
}

void merge(node* one, node* two)
{
    node* i = find(one);
    node* j = find(two);
    if (i->rank > j->rank)
        j->parent = i;
    else
        i->parent = j;

    if (i->rank == j->rank)
    {
        i->parent = j;
        j->rank++;
    }
}

int sameSet(int i, int j, vector<node*> v)
{
    if (find(v.at(i - 1))->data == find(v.at(j - 1))->data)
        return 1;
    return 0;
}

int main(int argc, char** argv) {

    cin >> n >> q;

    vector<node*> v (n); //vector holding all pointers to sets of nodes

    for (int i = 0; i < n; i++) //make n sets of 1 element each
    {
        node* n = new node(i);
        n->parent = n;
        v[i] = n;
    }
}

Would using a map instead of a vector, for example, be faster? Am I not compressing the path correctly (so that every member of a sets immediate parent is the highest ranking member) or unionizing by rank? As far as I'm aware, both merge and find should take O(log n) if implemented in the most efficient way, making me think this should be faster than it is.

\$\endgroup\$
  • \$\begingroup\$ Don't edit your code after the question is answered - I've rolled back your edit so it's again consistent with the answer(s). \$\endgroup\$ – Toby Speight May 9 '17 at 16:43
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg May 9 '17 at 18:27
4
\$\begingroup\$

Copying a huge vector by mistake

The reason your program is so slow is because of this line:

int sameSet(int i, int j, vector<node*> v)

This function makes a copy of the vector every time you want to do a simple check on two nodes. If you simply change that line to this:

int sameSet(int i, int j, vector<node*> &v)

then your program will avoid the copy. In my testing, the program ran in 1-2 seconds instead of over a minute with a large n.

Also, that function could be simplified from this:

int sameSet(int i, int j, vector<node*> &v)
{
    if (find(v.at(i - 1))->data == find(v.at(j - 1))->data)
        return 1;
    return 0;
}

to this:

bool sameSet(int i, int j, vector<node*> &v)
{
    return find(v[i-1]) == find(v[j-1]);
}
\$\endgroup\$
1
\$\begingroup\$

So first things first:

Dont use namespace std; It is a bad practice and generally unneeded;

There are some lets say odd things about your code. First thing it feels a lot like some basic C-code rather than C++. On top of that you deviate from standard practices. For example you use recursive function calls to find the parent:

node* find(node* root)
{
    if (root != root->parent)
        root->parent = find(root->parent);
    return root->parent;
}

The more idiomatic version would be a while loop:

node* find(node* root)
{
    while (root != root->parent) {
        root->parent = root->parent->parent;
    }
    return root->parent;
}

However, this function does something really terrible, as it overwrites the parent member of node and all its parents, which is most certainly not what the user expects of a function called "find". So you should rather add a temporary for that

node* find(node* root)
{
    node* temp = root->parent;
    while (temp != root) {
        temp = temp->parent;
    }
    return temp;
}

In your merge function you have an overlap, as i->parent = j; Is set twice. Once in the first else for !(i->rank > j->rank) and once in the second. For clarity i would suggest to use an else if

void merge(node* one, node* two)
{
    node* i = find(one);
    node* j = find(two);
    if (i->rank > j->rank) {
        j->parent = i;
    } 
    else if (i->rank == j->rank)
    {
        i->parent = j;
        j->rank++;
    }
    else {
        i->parent = j;
    }
}

Memory management

You are currently leaking nearly all of the memory allocated in you program. Every node is allocated by a call to new

node* n = new node(i);

However, there is no call to delete that i can see. The C-way would be to cleanup at the end of your main function. However in C++ we have smart pointer, that handle this for you. So rather than simply calling new you can use a std::unique_ptr. While we are at it, you can combine the constructor call with the insertion into you vector and reserve the memory beforehand

std::vector<std::unique_ptr<node>> v;
v.reserve(n);
for (int i = 0; i < n; i++) //make n sets of 1 element each
{
    v[i].emplace_back(std::make_unique<node>(i));
    n->parent = n;
}

What is also apparent is that you are setting n->parent = n whenever you construct the element, so maybe just add it to the constructor?

\$\endgroup\$
  • 2
    \$\begingroup\$ Looks like the idea behind find() is that it will optimize the data-structure. Not doing so is contra-indicated. \$\endgroup\$ – Deduplicator May 9 '17 at 15:13
  • \$\begingroup\$ Then the name find is wrong. SetRoot() or whatever, but find() suggests that no data will be modified \$\endgroup\$ – miscco May 9 '17 at 18:07
  • 2
    \$\begingroup\$ No, it does exactly what it advertizes. And there's no logical change to the data-structure, it just gets optimized, like with caching. \$\endgroup\$ – Deduplicator May 9 '17 at 18:14
  • \$\begingroup\$ Then we disagree, for me "any" change is a change that should be advertized accordingly \$\endgroup\$ – miscco May 9 '17 at 18:18
  • 2
    \$\begingroup\$ @misscco Perhaps you should read this wikipedia article on union find data structures and read the part on "path compression". \$\endgroup\$ – JS1 May 9 '17 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.