Eliminar entradas redundantes, scala way

Question

Editar: Se agregó el hecho de que la lista está ordenada, y darse cuenta de que 'duplicado' es engañoso, reemplazó eso con 'redundante' en el título.

Tengo una lista ordenada de entradas que indican un valor de producción en un intervalo determinado. Las entradas que indican el mismo valor en un momento posterior no agregan información y pueden omitirse de manera segura.

case class Entry(minute:Int, production:Double) 
val entries = List(Entry(0, 100.0), Entry(5, 100.0), Entry(10, 100.0), Entry(20, 120.0), Entry(30, 100.0), Entry(180, 0.0)) 

Experimentando con las funciones de recaudación Scala 2.8, hasta ahora tengo esta implementación trabajo:

entries.foldRight(List[Entry]()) { 
    (entry, list) => list match { 
    case head :: tail if (entry.production == head.production) => entry :: tail 
    case head :: tail => entry :: list 
    case List() => entry :: List() 
    } 
} 
res0: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0)) 

Cualquier comentario? ¿Me estoy perdiendo algo de magia scala?

Answer 1

Al comparar las entradas consecutivas en una lista, comience por zip -siguiendo la lista con su cola para obtener una lista de pares de elementos consecutivos.

A continuación, tomo la primera entrada de la lista, y uso collect para filtrar simultáneamente pares donde la producción no se modifica, y para los pares restantes, mapa e2. (collect es nuevo en Scala 2.8, y por un tiempo se llamó partialMap)

scala> entries.head :: ((entries zip entries.tail).collect { 
      case (Entry(_, p1), e2@Entry(_, p2)) if p1 != p2 => e2 
     }) 
res13: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0)) 

ACTUALIZACIÓN Para simplificar, esto supone que las entradas no está vacío.

Answer 2

En lugar de buscar duplicados para cada elemento, que es O (n^2), o comprimir, que es n^2 en la memoria, utilice el mapa [Doble, Int]. Luego solo agregue los elementos con la 'producción' como la clave y el 'minuto' como el valor. El mapa asegurará valores únicos para 'producción'. Es posible que pueda cargar el mapa de forma natural en cualquier parte de su código, pero incluso si tiene que comenzar con la lista anterior, cargar el mapa es lineal en la lista y solo O (n log (n)) en el mapa.

El mapa se reemplazará a medida que agrega "mymap + = production -> minute", de modo que para conservar el primer valor, invierta la lista antes de insertar o use un protector 'contains (key)'. Las comprobaciones serán O (log (n)) por lo que el algoritmo general será O (n log (n)).

Por cierto, podría usar un mapa [Entrada doble] para asignar los valores de producción directamente a sus estructuras de Entrada. A continuación, puede obtener fácilmente una lista, si es necesario, extrayendo los valores del mapa directamente del mapa y clasificando cualquiera de los elementos de la Entrada (si es necesario).

Answer 3

Hay un nuevo método zipped con Tuple2 que es más eficiente (y más lento) que zip en las listas para algunas operaciones. Es posible probar esto en su punto de referencia - No sé si es realmente más rápido, pero sin duda podría ser (y es definitivamente mucho más corto):

entries.take(1) ::: 
(entries,entries.drop(1)).zipped.filter(_.production != _.production)._2 

En lugar de comprimir la lista de pares de todo En el camino, crea una vista de la lista donde las piezas se pueden manipular juntas, y luego regresa las listas manipuladas. Tenga en cuenta el uso de tomar y soltar para manejar la caja vacía.

No es súper eficiente ya que crea dos listas cuando realmente solo necesita una, pero es una clase de solución que aún no ha aparecido.