联盟查找的效率提高

Question

我正在尝试优化联合查找算法以查找映像中的连接组件。我的图像可以是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

我会电子书籍两处改进，您的合并 - 查找结构：

• 真正实现两者结合，找到！如果你有一个工作的查找方法，实现联合会变得更简单，因为你不需要while (component[c] != c)类型的行。作为参考，检查出信息Wikipedia entry上合并 - 查找数据结构
• 实现一些常见的加速启发式像路径压缩（存储值find(x)回报component[x]，从而减少在find(x)的第二呼叫所需要的时间）的按大小或按工会大小（使较大集合为较小集合的父级）

编辑：由于似乎有一些关于另一个答案需要澄清，我将添加一个最小自己实施：

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]; 
    } 
} 

Answer 2

如果正确实施，联盟查找应该在一段时间内运行。

这里有一些想法：

- 修改find使得每个当你，直到你到达根（根是与物业NODE.up = NODE节点）上树的时候，你更新所有UP您遵循的所有节点的节点上升。换句话说，当您查找2个节点的连接组件时，您将更新该组件（表示为其根节点的索引），以查找该路径上所遵循的所有节点。

- 第二次发现某个节点的组件时，它不仅是本身，而且是中间节点的恒定时间。

- 工会应时刻都要花时间array[node] = parent_node。

Answer 3

一个使用工会的等级 和路径压缩相交集合的良好工作的算法如下：

实现，采用struct Node component[]。其中包含所有元素的数组。

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

struct Node 
{ 
    // Needed for union and find. 
    int parent; 
    int rank; 
}; 

// Find implementation using path compression, NOTE: a is index of the element to be found. 
int find (struct Node *component, int a) 
{ 
    if (component[a].parent != a) 
     return component[a].parent = find(component[a], component[a].parent) 
    return a; 
} 

// Union implementation using rank. NOTE: a and b are index of the element 
void union(struct Node *component, int a, int b) 
{ 
    if (find(component, a) != find(component, b)) 
    { 

     if (component[a].rank == component[b].rank) 
      component[a].rank += 1; 

     if (component[a].rank >= component[b].rank) 
      component[b].parent = a; 
     else 
      component[a].parent = b; 
    }  
} 

您可以使用上述功能，在常量时间（摊销）中进行联合查找。应该清楚的是，您可能必须修改结构，因为它适合您的数据。

您还可以使用模板在C++中实现它。但是因为问题是用C标记的，所以我提供了这个解决方案。

如果你想了解上述算法，这个链接可能会有所帮助。 Union-Find Algorithm

请发表评论以获得进一步的说明。