如何有效地存储等价物(来自连接组件标记算法)？

Question

我想存储来自Connected-component labeling algorithm的等价物。它基本上是从一个值(一个标签的ID)到多个值(标签中的ID与前者等价)的一种映射。

我已经做过这样的事情，但效果不是很好：

std::map<unsigned short, std::list<unsigned int>> equivalences;
for(int i = 0; i < MAX_NUMBER_OF_LABELS; ++i )
{
    std::list<unsigned int> temp;
    temp.push_back(i);
    // note that a label is equivalent to itself
    equivalences.insert( std::pair< int, std::list<unsigned int>>(i, temp) );
}

然后，我通过以下方式添加适当的等价性：

equivalences.at( i ).push_back( equivalent_labels_int );

这种方法的主要缺点是我必须预先声明map的大小(它必须足够大)，然后对于较大的大小(例如9999)，初始化时间大约是2.5s。

谁有更好的主意？

Answer 1

您不需要在C++ (或大多数语言)中预先确定map的大小。map可以通过向其中添加新元素来动态增长，因此，如果找到新的键，可以随时将其添加到映射中。例如：

equivalences[i].push_back(equivalent_labels_int);

这之所以有效，是因为map的方括号运算符(operator[])会自动向map添加一个新的键/值对，其中包含给定的键和默认值(如果不存在的话)。

此外，我建议不要使用list作为存储连接的blobs序列的容器。当您不需要随机访问并且经常删除序列中间的元素时，list是很好的，我认为您实际上并没有在这里这样做。相反，我建议使用vector或deque，因为这些结构更节省空间，并且具有更好的局部性。

最后，根据您的特定需求，您可能希望完全切换数据结构。如果您的算法通过从某个起点运行深度优先搜索，然后存储它遇到的所有结果来工作，那么您现在拥有的方法可能非常好。但是，如果您的算法是通过查找相似的点对，然后将它们包含的斑点合并在一起来工作，那么您可能会对disjoint-set forest data structure感兴趣，它具有简单的实现，但性能非常好。也就是说，使用这种结构会失去检查哪些点连接到给定点的能力，但效率的提高是相当显著的。

希望这能有所帮助！

Answer 2

我认为Disjoint set forests是你正在寻找的东西。下面是这个数据结构的a better description：