我想开发一个在线路径搜索网络服务。它在图 G 中搜索两个顶点 V1、V2 之间的边距离和最小的路径。
问题是G 非常大。它包含近 1000 万条边。
如果 G 足够小，它可能很简单。我宁愿...
- 列出 G 中的所有边/顶点以及它与某些 RDB（例如 MySQL 或 PostgreSQL）的关系。
- 用 PHP 或在 G 中搜索最短路径的东西实现我自己的 Web 服务
我自己的 PHP 脚本将...
- 从 RDB 中选择所有边/顶点，使用 PHP 的类或虚构数组或其他东西在内存上构建 G。
- 将 Dijkstra 算法应用于内存 G，并回复最短路径。
由于以下原因，这种方法不适用于巨大的 G。
- 构建内存 G 需要很多时间。
- 它为每个边缘使用大量内存。PHP 的对象很智能，但现在不需要。
这意味着构建的网络应该在搜索请求之前在内存上准备好，并且每个顶点/边对象应该更轻量级。
我决定用 C 来实现这个服务。我认为实现一个 Apache 模块比从头开始实现一个并发的、高性能的网络守护进程要容易得多（如果有更好的解决方案，我想知道） .
那么，我应该在哪里构建内存 G？
如您所知，Apache Web 服务器是多线程、多处理的守护进程。如果你开发一个为每个进程构建内存 G 的愚蠢模块，它将为 10 个处理的服务器在内存上构建近 1 亿条边（10 个相同的结构）。
我希望模块更智能，无论有多少进程运行，每个进程都共享 1 个单一的内存 G。
您认为在 Apache 模块中构建数据结构的最佳位置是哪里？