4

Opa 内の一連の出現を見つけるための効率的な a 手法を探していますSeq[Op]。出現が見つかったら、その出現を定義済みの置換に置き換え、リストが変化しなくなるまで同じ検索を再度実行したいと考えています。

シナリオ：

3 種類のOpケース クラスがあります。Pop()拡張Opし、Push()拡張Opし、 Nop()拡張しますOp。Push(), Pop()の発生をに置き換えたいNop()。基本的に、コードは次のようになりますseq.replace(Push() ~ Pop() ~> Nop())。

問題：

を呼び出しseq.replace(...)たので、シーケンス内で の出現を検索する必要がありPush(), Pop()ます。ここまでは順調ですね。発生を見つけます。しかし今、私は出現をリストからスプライスし、置換を挿入する必要があります.

現在、2 つのオプションがあります。私のリストは変更可能または不変です。不変リストを使用する場合、これらのシーケンスのサイズは通常 500 以上の要素であるため、パフォーマンスが心配です。多くのオカレンスを置き換えるとA ~ B ~ C ~> D ~ E、多くの新しいオブジェクトが作成されます。間違っていなければ。ただし、のような可変シーケンスを使用することもできますListBuffer[Op]。

基本的に、リンクされたリストのバックグラウンドから、ポインター曲げを行うだけで、合計 4 つの操作の後、新しいオブジェクトを作成せずに置換が完了します。だからこそ、私は今、パフォーマンスについて心配しています。特に、これは私にとってパフォーマンスが重要な操作であるためです。

質問：

メソッドを Scala 方式でどのように実装しreplace()ますか? また、これがパフォーマンス クリティカルな操作であることを念頭に置いて、どのような種類のデータ構造を使用しますか?

正しい方向または疑似コードに私を向ける答えに満足しています。完全な置換メソッドを記述する必要はありません。

ありがとうございました。

4

1 に答える 1

4

わかりました、いくつかの考慮事項があります。最初に、リストでtailは はオブジェクトを作成せず、先頭に ( ::) を追加すると、先頭に追加された要素ごとに 1 つのオブジェクトしか作成されないことを思い出してください。一般的に言えば、それはあなたが得ることができるのと同じくらい良いです.

これを行う1つの方法は次のとおりです。

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 を使用すると速度が向上する可能性があります。

では、このアルゴリズムの問​​題点は何でしょうか? 問題は、置換されたパターンがその位置の前に一致するかどうかをテストしないことです。たとえば、ACB を C に置き換え、入力 AACBB がある場合、このアルゴリズムの結果は C ではなく ACB になります。

この問題を回避するには、バックトラックを作成する必要があります。まず、パターンのどの位置で置換が発生するかを確認します。

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 の両方を一致させたい場合は、さらに悪化します。

実際には、完全な問題は、置換が一致の関数である正規表現の一致と置換と同等です。つまり、もちろん、正規表現アルゴリズムの調査を開始することをお勧めします。

編集

推論を完了するのを忘れていました。その手法が何らかの理由で機能しない場合、私のアドバイスは不変のツリーベースのベクトルを使用することです。ツリーベースのベクトルにより、少ないコピー量で部分シーケンスを置換できます。

それでもうまくいかない場合、解決策は二重にリンクされたリストです。そして、スライス置換を使用してライブラリから 1 つを選択します。そうしないと、既知であるがトリッキーなアルゴリズムのデバッグに多くの時間を費やしてしまう可能性があります。

于 2010-01-07T16:38:59.390 に答える