algorithm - 如何使用 O(log²n) 跨度实现这个 parenDist

Question

实现一个功能

val parenPairs : Paren.t Seq.t ! (int * int) Seq.t

其中 ( parenPairs S) 返回一系列索引对，其中每对包含括号的索引及其匹配的伙伴。例如，输入(())()应该产生 的一些排列<(0, 3), (4, 5), (1, 2)>。你的实现应该有 O(|S|log|S|)工作和O(log^2|S|)跨度。

提示：尝试用多少个其他括号将每个括号括起来。您可能还需要在某个时候进行排序...

我只能想出使用堆栈来解决它，但如果是这样，它将花费O(|S|)Work 和O(|S|)Span，这意味着没有并行性。那么如何用O(|S|log|S|)Work 和O(log²|S|)Span 来实现这个功能呢？

顺便说一句，这个练习是在背诵关于scan（或平行iter）。

我的实现如下（0代表'（'，1代表'）'）

t是一个列表栈，i记录当前索引。当x=1和堆栈的顶部是0，它意味着 parenMatch 所以我插入nm=(hd t, i)到结果列表中l。

显然，这个实现没有并行性。T^T

fun parenPairs (parens : int list) =
  let 
    fun pd (_,_,l) [] = l 
      | pd (t,i,l) (x::xs) = 
      if x = 0 then pd (i::t,i+1,l) xs
      else (*x=1*)
        if null t then pd (t,i+1,l) xs
        else let 
             val nm = (hd t, i)
             in pd (tl t,i+1, nm::l) xs end
  in pd ([],0,[]) parens

  end

标签： algorithmsml