c - 提高union-find的效率

Question

我正在尝试优化 union 查找算法以查找图像中的连通分量。我的图像可以是 2d 或 3d 文件，由 0 和 1 组成。我在这个线程中找到了一个实现:Connected Component Labelling , 用户 Dukering 的回答。

我根据自己的目的调整了该代码。该代码有效，但执行时间很快变得太大。我不明白这个问题。

我的代码如下所示。我用来测试它的文件链接在这里:https://utexas.box.com/s/k12m17rg24fw1yh1p21hytxwq5q8959u这是一个 2223x2223 大小的文件(在下面的程序中定义)。

正如原用户提到的，这是 union-find 的基本实现，可以提高效率。我不明白怎么办。另外，我在Matlab中测试了这张图片，Matlab的速度要快很多。例如，上面链接的图像在我的电脑上需要大约 1.5 分钟，但 Matlab 使用 bwlabel 只需一秒钟。我检查了 bwlabel 使用的算法，它似乎是 union-find 的一些变体，这就是我首先开始这项工作的原因。我如何让我的代码运行得那么快？我还应该提到，我希望在更大的图像(大到 1000^3)上运行我的代码。我当前的版本无法做到这一点。

    #include <time.h>
    #include <stdlib.h>
    #include <stdio.h>

    #define w 2223
    #define h 2223

    void writeArrayInt(int *data, int dims[], char *filename)
    {
     FILE *fp;

     fp = fopen(filename,"w"); 

     /* write grid dimensions */
     fwrite(dims, sizeof(int), 3, fp); 

      /* write data array */
      fwrite(data, sizeof(int), w*h, fp);

      fclose(fp);
      }

      void readArrayInt(int *data, int dims[], char *filename)
      {
       FILE *fp;

       fp = fopen(filename,"r"); 

       /* read grid dimensions */
       fread(dims, sizeof(int), 3, fp); 

       /* read data array */
       fread(data, sizeof(int), w*h, fp);

       fclose(fp);
       }

       void doUnion(int a, int b, int *component)
       {
        // get the root component of a and b, and set the one's parent to the other
       while (component[a] != a)
         a = component[a];
       while (component[b] != b)
         b = component[b];
       component[b] = a;
       }

       void unionCoords(int x, int y, int x2, int y2, int *component, int *input)
       {
        int ind1 = x*h + y;
        int ind2 = x2*h + y2;
        if (y2 < h && x2 < w && input[ind1] && input[ind2] && y2 >= 0 && x2 >= 0)
    doUnion(ind1, ind2, component);
        }

       int main()
       {
       int i, j;
       int *input = (int *)malloc((w*h)*sizeof(int));
       int *output = (int *)malloc((w*h)*sizeof(int));
       int dims[3];

       char fname[256];
       sprintf(fname, "phi_w_bin");
       readArrayInt(input, dims, fname); 

       int *component = (int *)malloc((w*h)*sizeof(int));

       for (i = 0; i < w*h; i++)
         component[i] = i;

 for (int x = 0; x < w; x++)
    for (int y = 0; y < h; y++)
    {
        unionCoords(x, y, x+1, y, component, input);
        unionCoords(x, y, x, y+1, component, input);
        unionCoords(x, y, x-1, y, component, input);
        unionCoords(x, y, x, y-1, component, input);
        unionCoords(x, y, x+1, y+1, component, input);
        unionCoords(x, y, x-1, y+1, component, input);
        unionCoords(x, y, x+1, y-1, component, input);
        unionCoords(x, y, x-1, y-1, component, input);
    }

for (int x = 0; x < w; x++)
{
    for (int y = 0; y < h; y++)
    {
        int c = x*h + y;
        if (input[c] == 0)
        {
            output[c] = input[c];
            continue;
        }
        while (component[c] != c) c = component[c];

        int c1 = x*h + y;
        output[c1] = component[c];
    }
}

sprintf(fname, "outputImage2d");
writeArrayInt(output, dims, fname);  

free(input);
free(output);
free(component);  
}

Answer 1

我建议对您的 union 查找结构进行两项改进:

• 实际实现 union 和 find! 如果您有一个有效的 find 方法，实现 union 会变得更加简单，因为您不需要 while (component[c] != c) 类的行。供引用，查看信息Wikipedia entry在 union 查找数据结构上
• 实现一些常见的加速启发式方法，如路径压缩(将 find(x) 返回的值存储在 component[x] 中，从而减少第二次调用 find(x)) 和 union-by-rank 或 union-by-size(使较大的集合成为较小集合的父集合)

编辑:由于似乎需要对另一个答案进行一些澄清，我将自己添加一个最小的实现:

typedef struct {
    int* parent;
    int size;
} union_find;

union_find make_sets(int size) {
    union_find result;
    result.parent = malloc(sizeof(int) * size);
    result.size = size;
    for (int i = 0; i < size; ++i) {
        result.parent[i] = size;
    }

    return result;
}

int find(union_find uf, int i) {
    if (uf.parent[i] < uf.size)
        return uf.parent[i] = find(uf, uf.parent[i]);
    return i;
}

void do_union(union_find uf, int i, int j) {
    int pi = find(uf, i);
    int pj = find(uf, j);
    if (pi == pj) {
        return;
    }
    if (pi < pj) {
        // link the smaller group to the larger one
        uf.parent[pi] = pj;
    } else if (pi > pj) {
        // link the smaller group to the larger one
        uf.parent[pj] = pi;
    } else {
        // equal rank: link arbitrarily and increase rank
        uf.parent[pj] = pi;
        ++uf.parent[pi];  
    }
}