4

我正在寻找一种有效的技术来Op查找Seq[Op]. 找到一个事件后，我想用定义的替换替换该事件并再次运行相同的搜索，直到列表停止更改。

设想：

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

问题：

既然我打电话，seq.replace(...)我将不得不在序列中搜索Push(), Pop(). 到现在为止还挺好。我发现了这种情况。但现在我将不得不从列表中拼接出现并插入替换。

现在有两种选择。我的列表可能是可变的或不可变的。如果我使用不可变列表，我会担心性能，因为这些序列的大小通常为 500 多个元素。如果我替换了很多事件，A ~ B ~ C ~> D ~ E如果我没记错的话，我会创建很多新对象。但是，我也可以使用可变序列，例如ListBuffer[Op].

基本上从链表背景来看，我只需做一些指针弯曲，在总共四次操作之后，我完成了替换而不创建新对象。这就是为什么我现在关心性能。特别是因为这对我来说是一个性能关键的操作。

问题：

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

我很高兴答案指出我正确的方向或伪代码。无需编写完全替换方法。

谢谢你。

4

1 回答 1

4

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

这样做的一种方法是：

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，情况会变得更糟。

在实践中，全面的问题等同于正则表达式匹配和替换，其中替换是匹配的函数。这意味着，当然，您可能想开始研究正则表达式算法。

编辑

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

如果不这样做，那么解决方案就是双向链表。并从带有切片替换的库中选择一个 - 否则您最终可能会花费太多时间来调试已知但棘手的算法。

于 2010-01-07T16:38:59.390 回答