scala - 创建括号平衡器的并行处理

Question

我正在参加并行编程的 coursera scala 类(class)。我有一项任务是解决顺序和并行的括号平衡器问题。我已经解决了顺序功能。对于并行函数，我怀疑如何跨并行线程维护当前的括号数据。

这是我的顺序函数:

def balance(chars: Array[Char]): Boolean = {

    def helper( arr: Array[Char], acc: Int): Boolean = {
      if (arr.isEmpty && acc ==0)
        true
      else if (arr.isEmpty  || arr.head == ')' && acc <=0)
        false
      else if (arr.head == '(')
        helper( arr.tail,  acc +1)
      else if (arr.head == ')' )
        helper( arr.tail,  acc - 1)
      else
        helper(arr.tail, acc)
    }

    helper(chars, 0)
  }

现在，我的整个逻辑都基于 acc 值。当我跨多个线程运行它们时，我应该关注什么？并行方法将具有范围开始和结束索引。到目前为止我唯一理解的是所有这些操作的总和应该是 acc==0。

请让我知道这方面的一些指示。

谢谢

Answer 1

由于Coursera规则，我不会给你确切的解决方案，而是给出一些建议。

我记得这个作业建议你在递归结果中使用两个值。通常学生认为这是“(”和“)”的计数，但正确的解决方案是另一个。您应该在每个递归步骤中计算两个值:

1. 当前步长的增量= countOf "("- countOf ")"
2. 当前步骤的最小“深度”。 IE。增量的最小值，如果尝试在当前 block 上从左到右遍历。它可以低于 delta。

几个例子(假设这是一些中间步骤):“((())”:增量= 0，最小深度= 0")))(": 增量 = -2, 最小深度 = -3

然后，在进行典型的平行遍历后，您将需要正确减小这两个值。你自己很容易猜到这一点。

如果平衡，你最终会得到 (0,0)。

例如 case ")("会给你 (0,-1)