如何高效地存储等值（来自连接组件标记算法）？

我想存储Connected-component labeling algorithm的等价值。它基本上（从相当于前者的标签标识。）制作样图从一个值（一个标签的ID）到多个值如何高效地存储等值（来自连接组件标记算法）？

我已经做了这样的事情，但它不工作非常好：

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

这种方法的主要缺点是，我要在前面声明map的大小（它必须足够大），然后大：

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

然后，我通过添加适当的等价大小（例如9999）的初始化时间是a大约2.5s。

任何人有更好的主意吗？

来源

2012-01-15 Patryk

您不需要在C++（或大多数语言）中预先设置大小map。 map可以通过添加新元素来动态增长，所以如果您找到新的密钥，您可以随时将其添加到地图中。例如：

equivalences[i].push_back(equivalent_labels_int);

这样做是因为，如果一个已经不存在的map的方括号运算符（operator[]）会自动添加一个新的键/值对的map用给定密钥和一个默认值。

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

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

希望这会有所帮助！

来源

2012-01-15 20:40:04 templatetypedef

非常感谢！你能解释我2件事情：1）'.at（...）'和'[]运算符'有什么区别？ 2）我不关心元素的顺序，也不会从中间移除元素，因此我正确理解'vector'会很好吗？ – Patryk 2012-01-15 20:58:55

当然！ '.at'成员函数将查找与关键字相关的值，并在关键字不存在时抛出'out_of_range'异常。当钥匙应该存在时，它主要用于在地图中查找。 'operator []'成员函数也会查找一个值，但如果指定的键不存在，它将自动插入一个新的键/值对。成语'myMap [myKey]'因此可以用来表示“查找与myKey相关的内容，如果它不存在，则创建一个默认值。”是的，你应该在这种情况下使用'vector'。 – templatetypedef 2012-01-15 21:01:08

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

来源

2012-01-15 20:37:29

打我吧，我会建议一样的。 – john 2012-01-15 20:39:38

如何高效地存储等值（来自连接组件标记算法）？

回答

相关问题