内存有效的方式来代表最短路径? [英] Memory efficient way to represent shortest path?

问题描述

说我得到了从节点A到节点B的最短路径.该路径只是边的列表，因此一条路径A-> B-> C将表示为[(A，B)，(B，C)].

Say I am given the shortest path from node A to node B. The path is simply a list of edges, so a path A->B->C, will be represented as [(A,B),(B,C)].

当前，每个节点的类型为 string ，从一个节点到另一个节点(例如(A，B))的路径是字符串的 set ，并且该路径是集合的列表.

Currently, each node is of type string, a path from one node to another, say (A, B), is a set of string, and the path is a list of sets.

现在，该路径包含超过60k的边，必须将其保存到数据库中以供以后检索.

Now, the path consists of over 60k edges, and it must be saved to a database for later retrieval.

因此，很明显，我需要一种非常好的方法来用C ++表示此路径:

So obviously, I need a very nice way to represent this path in C++ such that:

1. 与原始路径相比，路径的大小已大大减小
2. 从数据库检索路径时，检索时间足够短.

谁能为我提供一些见识?

Can anyone provide me with some insight?

谢谢.

推荐答案

如果您将很多字符串复制到 c ++ 代码中，并且它们很大，则可以考虑使用指针或智能指针.还可以选择对字符串进行哈希处理，但是这对于比较比较有用.通常，为什么首先要担心使用字符串，除非它们非常大，例如文本文档.

If you copy the strings alot in the c++ code and they are very large you might consider using a pointer or smart pointer instead. There's also the option of hashing the strings, but that will mostly be usefull for comparisons. Generally why worry about using strings in the first place, except if they are very large like text documents.

对于容器，您可以只使用 std :: vector< std :: string>

As for container, you could just use a std::vector<std::string>

最后存储A到B的最短路径的最有效方法是存储端点，然后仅在需要时才计算结果.

The most efficient way of storing the shortest path of A to B in the end is just storing the end points, then only calculate the result when needed.

这篇关于内存有效的方式来代表最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！