algorithm – 一种有效的技术,用于替换具有可变或不可变状态的序列中的出现

我正在寻找一种有效的技术来找到Seq [Op]中的Op出现序列.一旦发现,我想用已定义的替换替换出现并再次运行相同的搜索,直到列表停止更改.

场景：

我有三种类型的Op案例类. Pop()扩展Op,Push()扩展Op和Nop()扩展Op.我想用Nop()替换Push(),Pop()的出现.基本上代码看起来像seq.replace(Push()~Pop()〜> Nop()).

问题：

现在我调用seq.replace(…)我将不得不在序列中搜索Push(),Pop()的出现.到现在为止还挺好.我发现了这个问题.但是现在我必须将列表中的出现拼接并插入替换.

现在有两种选择.我的列表可能是可变的或不可变的.如果我使用不可变列表,我害怕性能,因为这些序列通常是500个元素.如果我替换很多像A~B~C~>的事件. D~E我会创造很多新物体如果我没有弄错的话.但是我也可以使用像ListBuffer [Op]这样的可变序列.

基本上从链接列表背景我只会做一些指针弯曲,并且在总共四次操作之后,我完成了替换而没有创建新对象.这就是我现在关注表现的​​原因.特别是因为这对我来说是一项对性能至关重要的操作.

题：

您将如何以Scala方式实现replace()方法以及您将使用哪种数据结构,请记住这是一个性能关键的操作？

我很满意那些指向正确方向或伪代码的答案.无需编写完整的替换方法.

谢谢.

好的,需要考虑一些事项.首先,回想一下,在列表中,tail不会创建对象,而prepending(：:)只为每个前置元素创建一个对象.一般来说,这几乎和你能得到的一样好.

这样做的一种方法是：

def myReplace(input: List[Op], pattern: List[Op], replacement: List[Op]) = {
  // This function should be part of an KMP algorithm instead, for performance
  def compare(pattern: List[Op], list: List[Op]): Boolean = (pattern, list) match {
    case (x :: xs, y :: ys) if x == y => compare(xs, ys)
    case (Nil, Nil)                   => true
    case _                            => false
  }

  var processed: List[Op] = Nil
  var unprocessed: List[Op] = input
  val patternLength = pattern.length
  val reversedReplacement = replacement.reverse

  // Do this until we finish processing the whole sequence
  while (unprocessed.nonEmpty) {

    // This inside algorithm would be better if replaced by KMP

    // Quickly process non-matching sequences
    while (unprocessed.nonEmpty && unprocessed.head != pattern.head) {
      processed ::= unprocessed.head
      unprocessed = unprocessed.tail
    }

    if (unprocessed.nonEmpty) {
      if (compare(pattern, unprocessed)) {
        processed :::= reversedReplacement
        unprocessed = unprocessed drop patternLength
      } else {
      processed ::= unprocessed.head
      unprocessed = unprocessed.tail
      }          
    }
  }

  processed.reverse
}

您可以通过使用KMP获得速度,特别是如果搜索的模式很长.

现在,这个算法有什么问题？问题是它不会测试被替换的模式是否在该位置之前引起匹配.例如,如果我用C替换ACB,并且我有一个输入AACBB,那么这个算法的结果将是ACB而不是C.

要避免此问题,您应该创建一个回溯.首先,检查模式中的哪个位置可能发生替换：

val positionOfReplacement = pattern.indexOfSlice(replacement)

然后,您修改算法的替换部分：

if (compare(pattern, unprocessed)) {
        if (positionOfReplacement > 0) {
          unprocessed :::= replacement
          unprocessed :::= processed take positionOfReplacement
          processed = processed drop positionOfReplacement 
        } else {
          processed :::= reversedReplacement
          unprocessed = unprocessed drop patternLength
        }
      } else {

这将足够回溯以解决问题.

然而,这个算法不能有效地处理多个模式,我猜你就是这样.为此,您可能需要对KMP进行一些调整,以便有效地进行,或者使用DFA来控制可能的匹配.如果你想匹配AB和ABC,情况会更糟.

在实践中,完全打击问题相当于正则表达式匹配&替换,替换是匹配的函数.当然,这意味着您可能需要开始研究正则表达式算法.

编辑

我忘了完成我的推理.如果该技术由于某种原因不起作用,那么我的建议是使用不可变的基于树的向量.基于树的矢量使得能够以低复制量替换部分序列.

如果不这样做,那么解决方案就是双重链接列表.从一个带有切片替换的库中选择一个 – 否则你最终可能花费太多时间来调试已知但棘手的算法.