java - 如何提高分布式图算法的性能？

我有一个图形问题，如下所示，我需要优化其执行时间性能。我只在寻找编程技术，而不在寻找算法优化来提高性能。问题如下:给定一个图G(V，E)，每个节点u构造其邻居N(u)的子集，称为多集中继(M_r(u))，这样u的每个2跳邻居都是一个邻居到M_r(u)中的至少一个节点。节点u的M_r(u)的构造如下。

construct_mr(u)
1) M_r(u) is initially empty.
1') The set of non-covered 2-hop of neighbors of u is the set of all 2-hop neighbors of u.
// a covered 2-hop neighbor of u: is a 2-hop neighbor of u that is also a neighbor to at least one of the nodes of M_r(u).
2) while (M _r(u) is not a multiset relay set)
 2a) update the set of non-covered 2-hop neighbors of u.
 2b) add to M_r(u) a neighbor v that cover the most non-covered 2-hop neighbors of u.

现在，我做了以下工作:

for each node u \in V: construct_mr(u).

这里的问题是它是序列化的实现，并且在图形较大且密集时具有可怕的执行时间。我正在寻找一种可以提高此类算法性能的方法-最好使用Java或C++。我虽然是多线程的，但是我应该使用线程调度来获得良好的性能吗？ [请注意，消息传递编程模型不会产生任何影响，因为我们没有传递任何消息]

最佳答案

我怀疑分布式实现是否会有所帮助。

问题的核心是图遍历过程，在此过程中您可以确定每个2跳邻居。为此，该算法的分布式版本中的每个实例都需要一个图的拷贝:

在niave的情况下，每个实例都需要整个图。您可能会发现，将图形分发到实例所花费的时间超过了纯粹并行阶段的任何加速。

替代方法是对图形进行分区，然后将每个实例发送给图形的一部分。但是随后您引入了一个问题，即一个实例需要与其他实例进行对话以找出不在其图部分中的图节点，这很可能会否定并行性。

(根据经验，如果您不必在实例之间移动大量数据，并且如果计算可以在很大程度上由实例执行而无需与其他人交谈，则分布式解决方案最有效。通信成本和实例间同步往往会扼杀并行性。)

否。如果要对此进行并行化，最好的选择是在单个JVM中使用多线程。为了在给定的算法实现中获得最佳性能，请将线程数设置为与可用处理器数相同。创建更多线程将使情况变得更糟，而不是更好。 (并且不要弄乱线程调度……这将无济于事。)

话虽如此，我怀疑您的计算速度较慢的真正原因在于算法的细节以及实现数据结构的方式。

没有一种神奇的“编程技术”可以使慢速算法快速……而无需对其进行更改。

(一种行之有效的方法是分析您的代码，确定大部分时间都花在哪里，然后……在深思熟虑之后……重新设计代码/数据结构以改进它。但是没有这里有任何魔力。只要努力，再思考。)