场景:
我有三种类型的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,情况会更糟.
在实践中,完全打击问题相当于正则表达式匹配&替换,替换是匹配的函数.当然,这意味着您可能需要开始研究正则表达式算法.
编辑
我忘了完成我的推理.如果该技术由于某种原因不起作用,那么我的建议是使用不可变的基于树的向量.基于树的矢量使得能够以低复制量替换部分序列.
如果不这样做,那么解决方案就是双重链接列表.从一个带有切片替换的库中选择一个 – 否则你最终可能花费太多时间来调试已知但棘手的算法.
精彩评论