11

我编写了一个 C++ 程序来模拟我正在研究的某个过程。它在模拟的每个时间步输出离散的“状态”。例如：

a
b
c
b
c
b

将是以 a 作为初始条件（由我设置或随机生成）的模拟运行的输出，而 b & c 将是系统不断在其间振荡的状态。

我想将其中的许多运行组合成一个马尔可夫链，以便它变成一个具有以下顶点和边的图。（最好在运行时，因为首先保存输出会占用大量磁盘空间。）括号之间的数字表示遇到某个顶点或边的次数，因此也应该存储它。

Vertices: a(1), b(3) and c(2).

Edges: a->b(1), b->c(2), c->b(2).

真实状态包含 112 位信息，我正在生成数十亿个这样的转换。问题是我还没有找到一个图形库或程序来高效快速地生成马尔可夫链。我一直在玩弄：

  • 谷歌稀疏散列在 C++ 中构建我自己的图形类。
  • Neo4J（我刚刚开始使用这个）
  • 柠檬图书馆

我刚刚完成了“Google 稀疏散列图”，但结果在运行中途变得非常缓慢。大约一天后（内存使用量超过 20 GB，本身不是问题，因为还有更多），它变慢了，大约需要三周才能完成。

我可以使用 12 或 16 核和 256 或 512 GB 内存的计算机，我的感觉是它们应该能够胜任这项工作。

由于我不是受过训练的程序员，而且我的编码速度很慢，所以在我花费大量时间研究另一个不完美的解决方案之前，我正在寻找一些信息。

  • 可以快速接受大量顶点和边来构建马尔可夫链的最佳程序/库是什么？
  • 缓慢是由于使用了错误的工具或不完善的编码（我怀疑）还是我只是试图做一些总是需要很多时间的事情？

我希望我能把我的问题说清楚。提前感谢任何智慧或答案。

编辑：

根据评论中的问题和答案，我想我的问题应该是：什么是适合 C++ 的快速矩阵库？

4

1 回答 1

1

你看过 boost::numeric::ublas 吗？它有一个成员稀疏矩阵，可为您提供类似矩阵的访问权限，但不是在内存中构建 NxN 数组，而是保留每个节点的边列表。

因此，如果 N 是节点数而不是NxN内存中的数组，则保留Nx30-avg num of edges per node-

但是，即使假设您可以使用单个字节来计算边的重复次数，您仍然有 600M 节点，每个节点都有 30 条边的列表。

列表条目是 uint32 的边缘名称，内容至少为 1 个字节。所以列表最少需要 150 个字节。内存至少为 90GB。可能更高，因为列表中的每个元素都有开销。

如果您可以在没有操作系统将数据交换到磁盘的情况下将这一切保存在内存中，那么它没有理由不能快速运行。当然，有序映射可能会胜过 hash_map。这取决于实现和使用的散列函数。

天真std::map<uint32, std::map<uint32, unint8>>如果树是平衡的，大树的长度是 30，而小树的长度很小。所以访问不应该需要很长时间。hash_map 可能会更好地为列工作，但不确定：（hash_map<uint32, std::map<uint32, unint8>>谷歌稀疏散列图针对内存而不是速度进行了调整，列图将非常大，这可能使其不适合）

最后，您应该考虑将这些信息保存在磁盘上而不是内存中。事实上，你可以使用一个外部数据服务，比如一个数据库，每个节点都有一个表（NodeId，NumOfHits）和一个边缘表（NodeId，NodeId，NumOfHits）{这种表示占用更多空间}

我会尝试像 Cassandra 这样的东西，它可以为您管理磁盘与内存缓存，并且可以轻松地扩展到多台计算机。而且您不需要复杂事务模型等的开销。

于 2013-10-30T08:30:24.893 回答