harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "daizi sheng" <daizish...@gmail.com>
Subject [drlvm][jitrino] Problem on the implementation of UnionFind class
Date Thu, 08 Nov 2007 07:16:57 GMT
The file is: working_vm\vm\jitrino\src\shared\unionfind.h .

In this file, one data structure is implemented to support
 the following 3 operations:

         MAKE_SET, FIND_SET, UNION_SET

To achieve high efficiency, there are two heuristics--"union by rank"
and "path compression" to improve the performance.

1. find () function implements two version of "path compression"

2. link () function try to implement the "union by rank" algorithm, but
unfortunately, it does not implement it correctly.

Here is the original code snippet

    void link(UnionFind *other) {
        assert(other);

        UnionFind *aroot = find();
        UnionFind *broot = other->find();

        if (aroot->rank < broot->rank) {
            aroot->parent = broot;
        } else {
            if (aroot->rank == broot->rank) {
                broot->rank += 1;
            }
            broot->parent = aroot;
        }
    };


And you can check the original algorithm on the following page for more
details if
you want: section 22.3 in page


http://acm2.ustc.edu.cn/~daizisheng/algorithm/clrs/clrs_1st/book6/chap22.htm

Generally, the algorithm try to link the node with lower rank to the node
with higher
 rank (rank is the height of the sub-tree rooted at current node, e.g.
height of
one-node-tree is 1), If both tree owns same rank (the if statement), we
break the
tie arbitrarily, here we set broot to be a child of aroot, and SO,

      rank of node aroot should be increased by 1, not rank of node broot.

What we need to do to fix it is just changing the statement

                broot->rank += 1;
into

                aroot->rank += 1;

ANYWAY, such error does not lead to any invalidation, but it do lead an
efficiency problem.

Not sure whether it is a real bug, but at least, it

   does not work as what the author expected.

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message