Phi*_*ßen 9 algorithm time-complexity apache-spark connected-components spark-graphx
我没有找到关于其实现复杂性的声明.
通常,查找连通分量可以在线性时间内完成,例如通过广度优先搜索或深度优先搜索(参见维基百科文章).但是,假设您可以将图形保留在内存中.GraphX实现了一个分布式的核外算法,因此我认为它不具有可比性.
你知道他们的算法如何工作以及它有多复杂性？
我认为图与非图解决方案的主要目标是减少解决问题所需的连续步骤的数量。这与复杂性不同——事实上，图形解决方案可能需要更多的总 CPU 指令来执行，但如果它减少了顺序步骤的数量，它仍然是正确的解决方案。
在查找连通分量方面，广度优先和深度优先方法都具有相同数量的连续步骤，即图中顶点数量的某个倍数。必须按顺序将相同的逻辑应用于每个顶点。这就是整个解决方案。
即使您的图表有两个或多或少相等大小的集群，您也无法将工作分成两个工作人员并从一端开始并在中间相遇。你不知道终点在哪里。你不知道中间在哪里。
如果你知道进去就知道出来，那么你的连续步骤总数可能会减少一半。如果有帮助，您可以将其视为理论上您可以按顺序步骤执行的最佳操作。它完全取决于图表的形状。
如果您有很多独立的离散集群，并且没有一个集群超过 10 人，那么理论上您可以执行的最佳步骤是 10 个连续步骤。无论您拥有多少并行处理能力，您最多只能执行 10 个连续步骤。
图算法不仅能让你更接近理论最小值——根据集群的形状，它实际上会击败它。
那么Spark算法是如何工作的呢？这相当简单——每个节点只是将其广播VertexId给它的邻居，而它的邻居也做同样的事情。任何收到VertexId低于自己的广播的节点将进行下一轮广播；如果不是，顶点将保持沉默。
如果您有一个集群，其中每个顶点都连接到其他每个顶点，那么在一轮消息之后，每个顶点都知道谁是最低的 VertexID，并且在下一轮中它们都会保持沉默。一个连续的步骤，整个集群。
另一方面，如果簇中的每个顶点仅连接到最多 2 个其他顶点，则在所有顶点知道最小值是多少之前，可能需要执行 N 个连续步骤VertexID。
显然，图算法中的顺序步骤具有不同的性质，甚至图与图之间的顺序步骤也不同。连接良好的图将生成大量消息，并花费更多时间合并它们等。但它不会像连接较差的图那样需要那么多的顺序步骤。
长话短说，图解决方案的性能完全取决于图的形状，但它的并行性应该比广度优先或深度优先的解决方案好得多。