从Boost图中删除100,000个节点-Java 学习之路

我有一个图表（adjacency_list（listS，vecS，bidirectionalS，VertexVal）），我需要删除100,000个节点 . 每个节点还包含2个64位整数和另一个64位整数的结构 . 下面代码中发生的guid检查是检查结构中的第一个整数 .

根据VTune，在我的笔记本电脑（i7 2.7GHz，16GB RAM）上大约需要88秒 .

以下是我删除节点的方法：

vertex_iterator vi,vi_end;
  boost::tie(vi, vi_end) = boost::vertices(m_graph);
  while (vi!=vi_end) {
    if (m_graph[*vi].guid.part1 == 0) {
      boost::remove_vertex(*vi,m_graph);
      boost::tie(vi, vi_end) = boost::vertices(m_graph);
    } else 
      ++vi;
  }

Vtune显示boost :: remove_vertex（）调用需要88.145秒 . 有没有更有效的方法来删除这些顶点？
Vtune data for boost::remove_vertex_dispatch(). This is the breakdown of the 88 seconds

3 回答

0
在你的删除分支中你重新编译迭代器：
```
boost::tie(vi, vi_end) = boost::vertices(m_graph);
```
这将导致每次重新启动循环时重新启动循环 . 这正是Schlemiel The Painter .

我会发现你是否可以信任 remove_vertex 而不是触发重新分配 . 如果是这样，它需要一个基于索引器的循环而不是基于迭代器的循环 . 或者你可能能够处理原始容器（虽然我记得这是一个私人成员） .

Update 使用 vecS 作为顶点的容器会导致性能不佳：

如果adjacency_list的VertexList模板参数是vecS，则此操作将使图形的所有顶点描述符，边描述符和迭代器无效 . <...>如果需要经常使用remove_vertex（）函数，则listS选择器是VertexList模板参数的更好选择 .

这个small benchmark test.cpp比较：
- with -DSTABLE_IT （ listS ）
```
$ ./stable 
Generated 100000 vertices and 5000 edges in 14954ms
The graph has a cycle? false
starting selective removal...
Done in 0ms
After: 99032 vertices and 4916 edges
```
- 没有 -DSTABLE_IT （ vecS ）
```
$ ./unstable 
Generated 100000 vertices and 5000 edges in 76ms
The graph has a cycle? false
starting selective removal...
Done in 396ms
After: 99032 vertices and 4916 edges
```
- 使用 filtered_graph （感谢评论中的 @cv_and_he ）
```
Generated 100000 vertices and 5000 edges in 15ms
The graph has a cycle? false
starting selective removal...
Done in 0ms
After: 99032 vertices and 4916 edges
Done in 13ms
```
您可以清楚地看到 listS 的删除速度更快 much 但生成速度慢了 much .
回复于 2024-05-12T17:07:35+08:00
2

我能够使用Boost序列化例程将图形成功序列化为字符串，解析字符串并删除我不需要的节点并对已修改的字符串进行反序列化 . 对于图表中的200,000个节点和需要删除的100,000个节点，我能够在不到2秒的时间内成功完成操作 .

对于我的特定用例，每个顶点有3个64位整数 . 当需要删除时，我将其中2个整数标记为0 . 一个有效的顶点永远不会有0.当点清理图形时 - 要删除“已删除”的顶点，我遵循上面的逻辑 .

在下面的代码中，removeDeletedNodes（）执行字符串解析并删除顶点并映射边数 .

回复于 2024-05-12T17:07:35+08:00
8

看到更多的Vtune数据会很有趣 .

我的经验是，删除成千上万的小对象时，默认的Microsoft分配器可能是一个很大的瓶颈 . 您的Vtune图表是否显示删除或免费的大量时间？

如果是这样，请考虑切换到第三方分配器 . 据说Nedmalloc很好：http://www.nedprod.com/programs/portable/nedmalloc/

Google有一个tcmalloc，它几乎在每个平台上都非常受欢迎，并且比内置分配器快得多 . https://code.google.com/p/gperftools/ tcmalloc不是Windows的插件 .

回复于 2024-05-12T17:07:35+08:00

从Boost图中删除100,000个节点

3 回答

相关问题