聯盟查找的效率提高

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

請發表評論以獲得進一步的說明。