如何理解Apache GraphX的pregel实现中的maxIterations

Question

官方解释是maxIterations将用于非收敛算法。我的问题是：如果我不知道算法的收敛性，应该如何设置maxIterations的值？而且，如果有收敛算法，那么该值的含义是什么？

顺便说一句，我也对预凝胶的“重复”感到困惑。 代码如何执行计为迭代？

这里是pregel源代码的一部分：

// Loop
var prevG: Graph[VD, ED] = null
var i = 0
while (activeMessages > 0 && i < maxIterations) {
  // Receive the messages and update the vertices.
  prevG = g
  g = g.joinVertices(messages)(vprog)
  graphCheckpointer.update(g)

  val oldMessages = messages
  // Send new messages, skipping edges where neither side received a message. We must cache
  // messages so it can be materialized on the next line, allowing us to uncache the previous
  // iteration.
  messages = GraphXUtils.mapReduceTriplets(
    g, sendMsg, mergeMsg, Some((oldMessages, activeDirection)))
  // The call to count() materializes `messages` and the vertices of `g`. This hides oldMessages
  // (depended on by the vertices of g) and the vertices of prevG (depended on by oldMessages
  // and the vertices of g).
  messageCheckpointer.update(messages.asInstanceOf[RDD[(VertexId, A)]])
  activeMessages = messages.count()

  logInfo("Pregel finished iteration " + i)

  // Unpersist the RDDs hidden by newly-materialized RDDs
  oldMessages.unpersist(blocking = false)
  prevG.unpersistVertices(blocking = false)
  prevG.edges.unpersist(blocking = false)
  // count the iteration
  i += 1
}

感谢您的慷慨答谢：）

Answer 1

maxIterations用于确保算法终止。请注意，Pregel只是一个范例，因此其收敛取决于您的算法（sendMessage和vertexProgram）。因此，当我们确定算法会收敛时，将Int.MaxValue用作最大迭代次数。

如果不确定算法的终结点，最好根据经验测试进行设置。例如，如果您的算法是一种可以优化某些值的启发式算法，则显而易见，最大值越大，越接近是你的目标。在这里，您可以根据需要使用多少时间和资源来决定何时停止（例如100次迭代）。

最后，代码使用变量i来计算迭代次数，并在每次迭代时递增。当i达到最大迭代次数时，或者甚至在没有消息交换时（算法收敛时），Pregel都会停止。