工会发现的效率提高 [英] Increasing efficiency of union-find
问题描述
我正在尝试优化联合查找算法，以查找图像中的连接组件。我的图像可以是2d或3d文件，由0和1组成。我在此线程中找到了一个实现：连接的组件标签，并有Dukering用户的回答。
I'm trying to optimize a union-find algorithm for finding connected components in images. My image can be a 2d or 3d file, consisting of 0s and 1s. I found an implementation in this thread: Connected Component Labelling, with the answer by user Dukering.
我修改了该代码以达到我的目的。代码可以工作，但是执行时间很快变得太大。我不明白问题所在。
I adapted that code to my purpose. The code works, but the execution time rapidly becomes too big. I don't understand the problem.
我的代码如下所示。我用来测试的文件链接在这里： https://utexas.box.com/s/k12m17rg24fw1yh1p21hytxwq
这是一个2223x2223大小的文件（在下面的程序中定义）。
My code is shown below. The file I was testing it with is linked here: https://utexas.box.com/s/k12m17rg24fw1yh1p21hytxwq5q8959u That is a 2223x2223 size file (defined in the program below).
如原始用户所述，这是union的基本实现-找到，并且可以提高效率。我不明白另外，我在Matlab中测试了此图像，Matlab的速度要快得多。例如，上面链接的图像在我的计算机上花费约1.5分钟，但是Matlab使用bwlabel在一秒钟内完成了该操作。我检查了bwlabel所使用的算法，这似乎是对联合查找的某种改变，这就是为什么我首先开始这项工作的原因。如何使我的代码以这种速度运行？我还应该提到，我希望在更大的图像（最大1000 ^ 3）上运行我的代码。我的当前版本无法做到这一点。
As the original user mentioned, this is a basic implementation of union-find, and one can make it more efficient. I don't understand how. In addition, I tested this image in Matlab, and Matlab is much faster. For example, the image linked above takes ~1.5 minutes on my computer, but Matlab does it in like a second using bwlabel. I checked the algorithms bwlabel uses, and it seemed to be some variation of union-find, which is why I started this effort in the first place. How do I make my code work as fast as that? I should also mention that I hope to run my code on much larger images (as large as 1000^3). There is no way my current version can do that.
#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);
}
推荐答案
我建议对以下两项进行改进您的联合查找结构：
I would recomment two improvements to your union-find structure:
- 实际上同时实现两个联合并查找！如果您有可行的查找方法，实现联合变得更加简单，因为您不需要
while（component [c]！= c）这种类型的行。作为参考，请查看有关联合查找数据结构的内容丰富的 Wikipedia条目 >
- 实施一些常见的加速启发式方法，例如路径压缩（将
find（x）返回的值存储在组件中[x]，从而减少了第二次调用find（x））所需的时间，并减少了按等级或按等级的工会大小（将较大的集合作为较小集合的父集合）
- Actually implement both union and find! If you have a working find method, implementing union becomes much simpler because you don't need the
while (component[c] != c)kind of lines. For reference, check out the informative Wikipedia entry on union-find data structures - Implement some of the common speedup heuristics like path-compression (store the value that
find(x)returns incomponent[x], thus reducing the time needed in a second call offind(x)) and union-by-rank or union-by-size (make the larger set the parent of the smaller set)
编辑：由于似乎需要对另一个答案进行一些说明，我将自己添加一个最小实现：
Since there seemed to be some clarification needed concerning another answer, I'll add a minimal implementation myself:
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];
}
}
这篇关于工会发现的效率提高的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
