Una técnica eficiente para reemplazar una ocurrencia en una secuencia con mutable o inmutable estado

Question

Estoy buscando un eficiente una técnica para encontrar una secuencia de Op ocurrencias en un Seq[Op].Una vez que una ocurrencia se encuentra, quiero reemplazar la ocurrencia con una definida de reemplazo y ejecutar la misma búsqueda de nuevo hasta que la lista no deja de cambiar.

Escenario:

Tengo tres tipos de Op el caso de las clases. Pop() se extiende Op, Push() se extiende Op y Nop() se extiende Op.Quiero reemplazar la ocurrencia de Push(), Pop() con Nop().Básicamente, el código podría parecer seq.replace(Push() ~ Pop() ~> Nop()).

Problema:

Ahora que me llame seq.replace(...) Voy a tener que buscar en la secuencia de una ocurrencia de Push(), Pop().Hasta ahora tan bueno.Me parece la ocurrencia.Pero ahora voy a tener que empalme la ocurrencia de la lista y coloque la sustitución.

Ahora hay dos opciones.Mi lista podría ser mutable o inmutable.Si yo uso una inmutable lista tengo miedo en relación con el rendimiento debido a que las secuencias son generalmente de más de 500 elementos de tamaño.Si puedo reemplazar un montón de ocurrencias como A ~ B ~ C ~> D ~ E Voy a crear una gran cantidad de nuevos objetos, Si no me equivoco.Sin embargo, yo también podría utilizar una secuencia como mutable ListBuffer[Op].

Básicamente a partir de un linked-fondo lista sólo quiero hacer algunas puntero de flexión y después de un total de cuatro operaciones que he hecho con la sustitución sin necesidad de crear nuevos objetos.Es por eso que ahora estoy preocupado por el rendimiento.Especialmente desde que es una operación fundamental para mí.

Pregunta:

¿Cómo implementar el replace() método en la Scala de moda y qué tipo de estructura de datos tendría que utilizar teniendo en cuenta que es una operación crítica?

Estoy contento con las respuestas que me apunte en la dirección correcta o pseudo código.No hay necesidad de escribir un completo método de reemplazo.

Gracias.

Answer 1

Ok, tener en cuenta algunas consideraciones.En primer lugar, recordemos que, en las listas, tail no crea objetos, y anteponiendo (::) sólo crea un objeto para cada elemento antepuesto.Eso es casi tan bueno como usted puede conseguir, generalmente hablando.

Una forma de hacer esto sería este:

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
}

Usted puede aumentar la velocidad mediante el uso de KMP, especialmente si el patrón buscado es largo.

Ahora, ¿cuál es el problema con este algoritmo?El problema es que no se prueba si el sustituido patrón de causas de un partido antes de esa posición.Por ejemplo, si reemplazar ACB con C, y tengo una entrada AACBB, a continuación, el resultado de este algoritmo será ACB en lugar de C.

Para evitar este problema, debe crear un backtrack.En primer lugar, comprobar en qué posición en el patrón de la sustitución puede ocurrir:

val positionOfReplacement = pattern.indexOfSlice(replacement)

A continuación, modifique el reemplazo de parte del algoritmo de esto:

      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 {

Esto va a dar marcha atrás lo suficiente para resolver el problema.

Este algoritmo no hacer frente de manera eficiente, sin embargo, con multiplicar los patrones al mismo tiempo, que supongo que es a donde vas.Por eso, es probable que necesite una adaptación de KMP, para hacerlo de manera eficiente, o, de lo contrario, el uso de un DFA para el control de posibles elecciones.Se pone aún peor si usted desea hacer coincidir ambos AB y ABC.

En la práctica, el golpe de lleno problema es equivalente a regex partido y reemplazar, donde el reemplazo es una función de la coincidencia.Lo que significa, por supuesto, puede que desee empezar a buscar en regex algoritmos.

EDITAR

Me estaba olvidando para completar mi razonamiento.Si esa técnica no funciona por alguna razón, entonces mi consejo es ir con una inmutable basada en el árbol de vector.Árbol de vectores basados en habilitar el reemplazo de las secuencias parciales con baja cantidad de copias.

Y si no, entonces la solución es que las listas doblemente ligadas.Y elegir uno de una biblioteca con rebanada de reemplazo; de lo contrario, usted puede terminar gastando demasiado tiempo depuración de un conocido, pero complicado algoritmo.