用于计算括号平衡的分布式算法

Question

这是一个interview question：“如何构建分布式算法来计算括号的平衡?”

通常，平衡算法从左到右扫描字符串，并使用堆栈来确保开括号的数量始终与关闭括号的数量相同，最后是开括号的数量==关闭括号的数量。

您将如何将其分发？

Answer 1

您可以将字符串拆分成块，并分别处理每个块，假设您可以并行读取并发送到其他机器。每个字符串需要两个数字。

1. 相对于字符串起始处达到的最小嵌套深度。
2. 整个字符串的嵌套深度的总增减。

使用这些值，您可以计算多个块的连接的值，如下所示：

minNest = 0
totGain = 0
for p in chunkResults
  minNest = min(minNest, totGain + p.minNest)
  totGain += p.totGain
return new ChunkResult(minNest, totGain)

如果totGain和minNest的最终值为零，则会匹配括号。

Answer 2

我将应用map-reduce算法，在该算法中，map函数将计算字符串的一部分，如果圆括号是对的，则返回空字符串，或者返回最后一个括号剩余的字符串。

然后，reduce函数将两个由map函数返回的字符串的结果连接起来，并再次计算，返回与map相同的结果。在所有计算结束时，要么得到一个空字符串，要么得到一个包含不对称括号的字符串。

Answer 3

我将尝试对@jonderry的答案进行更详细的解释。代码优先，在Scala中

def parBalance(chars: Array[Char], chunkSize: Int): Boolean = {
    require(chunkSize > 0, "chunkSize must be greater than 0")

    def traverse(from: Int, until: Int): (Int, Int) = {
      var count = 0
      var stack = 0
      var nest = 0
      for (n <- from until until) {
        val cur = chars(c)
        if (cur == '(') {
          count += 1
          stack += 1
        }
        else if (cur == ')') {
          count -= 1
          if (stack > 0) stack -= 1
          else nest -= 1
        }
      }
      (nest, count)
    }

    def reduce(from: Int, until: Int): (Int, Int) = {
      val m = (until + from) / 2
      if (until - from <= chunkSize) {
        traverse(from, until)
      } else {
        parallel(reduce(from, m), reduce(m, until)) match {
          case ((minNestL, totGainL), (minNestR, totGainR)) => {
            ((minNestL min (minNestR + totGainL)), (totGainL + totGainR))
          }
        }
      }
    }

    reduce(0, chars.length) == (0,0)
}

给定一个字符串，如果我们去掉对括号，剩下的内容将以)))(((的形式出现，number of )为n，number of (为m，然后是m >= 0，n <= 0(为了更容易计算)。这里n是minNest，m+n是totGain。要生成真正的平衡字符串，我们需要m+n == 0 && n == 0。

在并行操作中，我们如何从节点的左侧和右侧派生出这些节点？对于totGain，我们只需要将它们相加即可。当为节点计算n时，如果n(右)没有贡献，则它只能是n(左)，或者n(right) + left.totGain，取较小的值。