0

我正在使用 callgrind 来分析一段代码，我注意到在函数结束后计算了大量指令。这是有问题的输出

         4    cout << "computing cut" << endl;
     8,126  => ???:global constructors keyed to a (1x)
         6    vector<hole_node*> cut = residual_reachable(s, &cap, &f);
18,006,296  => mtlib.cpp:residual_reachable(hole_node*, std::__1::unordered_map<hole_node_edge, int, hole_node_edge_hash, std::__1::equal_to<hole_node_edge>, std::__1::allocator<std::__1::pair<hole_node_edge const, int> > >*, std::__1::unordered_map<hole_node_edge, int, hole_node_edge_hash, std::__1::equal_to<hole_node_edge>, std::__1::allocator<std::__1::pair<hole_node_edge const, int> > >*) (1x)
         .    return cut;
        14  }
2,327,827,246  => ???:global constructors keyed to a (3x)
     4,950  vector<hole_node*> find_interior(hole_node* root, int prev_width=0) {

这是整个函数的代码。它只是 Edmonds–Karp 算法的一个实现。

    typedef unordered_map<hole_node_edge, int, hole_node_edge_hash> edge_hashmap;
typedef unordered_map<hole_node*, hole_node*, hole_node_hash, hole_node_eq> vertex_hashmap;

vector<hole_node*> min_cut(vector<hole_node*> srcs, vector<hole_node*> tgts, 
                               hole_node** graph, int rows, int cols) {
      cout << "making edges" << endl;
      edge_hashmap f, cap;
      vertex_hashmap p;
      for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
          hole_node* cur = graph[r*cols + c];
          if (cur != NULL) {
            int size = graph[r*cols + c]->neighbors.size();
            for (int i = 0; i < size; i++) {
              hole_node_edge e(cur, cur->neighbors[i]);
              pair<hole_node_edge, int> tmp1(e, 0);
              pair<hole_node_edge, int> tmp2(e, 1);
              f.insert(tmp1);
              cap.insert(tmp2);
            }
          }
        }
      }

      cout << "making new vertices" << endl;
      hole_node * s = new hole_node(-1, -1, 0, -1);
      hole_node * t = new hole_node(-1, -2, 0, -1);
      s->id = -1;
      t->id = -2;
      cout << "adding src edges" << endl;
      for (int i = 0; i < srcs.size(); i++) {
        hole_node_edge fwd(s, srcs[i]);
        hole_node_edge bak(srcs[i], s);
        s->neighbors.push_back(srcs[i]);
        srcs[i]->neighbors.push_back(s);
        f.insert(pair<hole_node_edge, int>(fwd, 0));
        f.insert(pair<hole_node_edge, int>(bak, 0));
        cap.insert(pair<hole_node_edge, int>(fwd, 8));
        cap.insert(pair<hole_node_edge, int>(bak, 0));
      }
      cout << "adding tgt edges" << endl;
      for (int i = 0; i < tgts.size(); i++) {
        hole_node_edge fwd(t, tgts[i]);
        hole_node_edge bak(tgts[i], t);
        t->neighbors.push_back(tgts[i]);
        tgts[i]->neighbors.push_back(t);
        f.insert(pair<hole_node_edge, int>(fwd, 0));
        f.insert(pair<hole_node_edge, int>(bak, 0));
        cap.insert(pair<hole_node_edge, int>(fwd, 0));
        cap.insert(pair<hole_node_edge, int>(bak, 8));
      }
      cout << "done construction graph" << endl;
      cout << "running main loop" << endl;
      while (residual_path(s, t, rows, cols, &cap, &f, &p)) {
        cout << "found path " << p.size() << endl;
        vertex_hashmap::const_iterator cur_it = p.find(t);
        while (cur_it != p.end()) {
          hole_node * u = cur_it->first;
          hole_node * v = cur_it->second;
          int fwd_flow = (f.find(hole_node_edge(u, v)))->second;
          int bck_flow = (f.find(hole_node_edge(v, u)))->second;
          f[hole_node_edge(v, u)] = fwd_flow + 1;
          f[hole_node_edge(u, v)] = bck_flow - 1;
          cur_it = p.find(cur_it->second);
        }
        p.clear();
      }
      cout << "computing cut" << endl;
      vector<hole_node*> cut = residual_reachable(s, &cap, &f);
      return cut;
    }

如果我正确解释了输出，那么在方法结束后大约有 20 亿条指令正在执行。这些是什么以及如何减少它们？通常，“全局构造函数键入...”行是什么意思？

4

0 回答 0