c++ - 向图形添加边时占用大量内存

Question

我有一个结构 node 和一个类 graph 它们看起来像这样:

struct node {
    node(const std::string &s) : id(std::hash<std::string>()(s)) { }
    node(node &&) = default;
    node(const node &) = default;

    friend bool operator<(node lhs, node rhs){
        return lhs.id < rhs.id;
    }
    mutable bool visited{false};
    const std::size_t id;
    mutable std::set<node> neighbors;
    mutable std::set<node> back_edges;
};

class graph {
    private:
        std::set<node> node_set;
    public:
        size_t add_edge(node from, node to){

            //auto start = std::chrono::system_clock::now();

            auto iter_from = node_set.insert(from).first;
            auto iter_to = node_set.insert(to).first;


            iter_from->neighbors.insert(*iter_to);
            iter_to->back_edges.insert(*iter_from);

            //auto duration = std::chrono::duration_cast<std::chrono::milliseconds>
            //      (std::chrono::system_clock::now() - start);

            //return duration.count();
            return -1;
        }

        std::size_t size(){
            return node_set.size();
        }

};

现在我想通过生成随机图来测试 add_edge 方法。为此，我有一个函数可以生成长度为 SIZE 的随机字母数字字符串:

constexpr size_t SIZE{2};

graph g1;
for (int i = 0; i < 100000; i++){
    g1.add_edge(random_string(SIZE), random_string(SIZE));

如果我选择 SIZE 不太小，比如超过 5，一切正常，但如果我尝试选择 SIZE 小，比如 2 甚至 1，我会得到一个巨大的内存占用和测试需要永远。由于图应该更小 SIZE(对于 SIZE = 1 -> 26^2)我真的不明白为什么会这样。

编辑:对于较小的 SIZE，add_edge 在循环中的每次迭代中变得越来越慢。

编辑:这是生成随机字符串的函数:

std::string random_string(size_t length) {
    static bool initialized{false};
    if (!initialized) {
        std::srand(std::time(0));
        initialized = true;
    }
    auto randchar = []() -> char {
        static const char charset[] =
                "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        const size_t max_index = (sizeof(charset) - 1);
        return charset[std::rand() % max_index];
    };
    std::string str(length, 0);
    std::generate_n(str.begin(), length, randchar);
    return str;
}

Answer 1

您当前正在neighbors 和back_edges 中存储节点拷贝。这可能非常昂贵，因为 neighbors 和 back_edges 中的每个 node 都可以包含自己的一组 neighbors 和后边。您可能希望存储指向节点的指针。

例如，您可以使用:

std::set<node *, Comparator> neighbors;
std::set<node *, Comparator> back_edges;

代替:

std::set<node> neighbors;
std::set<node> back_edges;

Comparator 是:

struct Comparator {
  bool operator () (const node * a, const node * b) const {
    return !a || b ? *a < *b : false;
  }
};

更进一步，您可以更新 graph 类以包含:

std::set<std::shared_ptr<node>, Comparator> node_set;

代替:

std::set<node> node_set;

Comparator 是:

struct Comparator {
  bool operator () (
    const std::shared_ptr<const node> & a,
    const std::shared_ptr<const node> & b
  ) const {
    return !a || b ? *a < *b : false;
  }
};

然后 node 可以更新为包含:

std::set<std::shared_ptr<node>, Comparator> neighbors;
std::set<std::shared_ptr<node>, Comparator> back_edges;

另一种替代方法是使用邻接矩阵来表示图形。