Scala: Eliminar duplicados en la lista de objetos

Question

Tengo una lista de objetos List[Object] que están todos instanciados de la misma clase. Esta clase tiene un campo que debe ser único Object.property. ¿Cuál es la forma más limpia de iterar la lista de objetos y eliminar todos los objetos (excepto el primero) con la misma propiedad?

Answer 1

list.groupBy(_.property).map(_._2.head) 

Explicación: El método groupBy acepta una función que convierte un elemento en una clave para la agrupación. _.property es solo una abreviatura de elem: Object => elem.property (el compilador genera un nombre único, algo así como x$1). Entonces ahora tenemos un mapa Map[Property, List[Object]]. A Map[K,V] extiende Traversable[(K,V)]. Entonces puede atravesarse como una lista, pero los elementos son una tupla. Esto es similar al Java Map#entrySet(). El método de mapa crea una nueva colección al iterar cada elemento y aplicarle una función. En este caso, la función es _._2.head, que es la abreviatura de elem: (Property, List[Object]) => elem._2.head. _2 es solo un método de Tuple que devuelve el segundo elemento. El segundo elemento es la lista [Objeto] y head devuelve el primer elemento

Para obtener el resultado ser un tipo que desee:

import collection.breakOut 
val l2: List[Object] = list.groupBy(_.property).map(_._2.head)(breakOut) 

explicar brevemente, map realidad espera dos argumentos, una función y una objeto que se utiliza para construir el resultado. En el primer fragmento de código no se ve el segundo valor porque está marcado como implícito y así lo proporciona el compilador a partir de una lista de valores predefinidos en el alcance. El resultado generalmente se obtiene del contenedor mapeado. Esto usualmente es algo bueno. map on List devolverá List, map on Array devolverá Array, etc. En este caso, sin embargo, queremos expresar el contenedor que queremos como resultado. Aquí es donde se usa el método breakOut. Construye un generador (lo que genera resultados) solo mirando el tipo de resultado deseado. Es un método genérico y el compilador infiere sus tipos genéricos debido a que el tipo explícito de L2 para ser List[Object] o, para preservar el orden (suponiendo Object#property es de tipo Property):

list.foldRight((List[Object](), Set[Property]())) { 
    case (o, cum@(objects, props)) => 
    if (props(o.property)) cum else (o :: objects, props + o.property)) 
}._1 

foldRight es un método que acepta un resultado inicial y una función que acepta un elemento y devuelve un resultado actualizado. El método itera cada elemento, actualizando el resultado de acuerdo con la aplicación de la función a cada elemento y devolviendo el resultado final. Vamos de derecha a izquierda (en lugar de izquierda a derecha con foldLeft) porque estamos anteponiendo a objects - esto es O (1), pero se agrega O (N). También observe el buen diseño aquí, estamos usando una coincidencia de patrón para extraer los elementos.

En este caso, el resultado inicial es un par (tupla) de una lista vacía y un conjunto. La lista es el resultado que nos interesa y el conjunto se utiliza para realizar un seguimiento de las propiedades que ya hemos encontrado. En cada iteración, comprobamos si el conjunto props ya contiene la propiedad (en Scala, obj(x) se traduce a obj.apply(x). En Set, el método apply es def apply(a: A): Boolean. Es decir, acepta un elemento y devuelve verdadero/falso si existe o no). Si la propiedad existe (ya se encontró), el resultado se devuelve tal cual.De lo contrario, el resultado se actualiza para contener el objeto (o :: objects) y la propiedad se registra (props + o.property)

Actualización: @andreypopp quería un método genérico:

import scala.collection.IterableLike 
import scala.collection.generic.CanBuildFrom 

class RichCollection[A, Repr](xs: IterableLike[A, Repr]){ 
    def distinctBy[B, That](f: A => B)(implicit cbf: CanBuildFrom[Repr, A, That]) = { 
    val builder = cbf(xs.repr) 
    val i = xs.iterator 
    var set = Set[B]() 
    while (i.hasNext) { 
     val o = i.next 
     val b = f(o) 
     if (!set(b)) { 
     set += b 
     builder += o 
     } 
    } 
    builder.result 
    } 
} 

implicit def toRich[A, Repr](xs: IterableLike[A, Repr]) = new RichCollection(xs) 

de usar:

scala> list.distinctBy(_.property) 
res7: List[Obj] = List(Obj(1), Obj(2), Obj(3)) 

También tenga en cuenta que esto es bastante eficiente ya que estamos usando un generador. Si tiene listas realmente grandes, puede utilizar un HashSet mutable en lugar de un conjunto regular y comparar el rendimiento.

Answer 2

Aquí es una solución rápida, pero astuto poco que preserva el orden:

list.filterNot{ var set = Set[Property]() 
    obj => val b = set(obj.property); set += obj.property; b} 

A pesar de que utiliza internamente una var, creo que es más fácil de entender y de leer que el foldLeft-solución.

Answer 3

Una solución más

@tailrec 
def collectUnique(l: List[Object], s: Set[Property], u: List[Object]): List[Object] = l match { 
    case Nil => u.reverse 
    case (h :: t) => 
    if (s(h.property)) collectUnique(t, s, u) else collectUnique(t, s + h.prop, h :: u) 
} 

Answer 4

No sé qué versión de Scala está utilizando, pero sin duda tiene 2.8.2

list.distinct 

Editar (fijación de los votos abajo)

list.distinctBy 

Answer 5

Encontré una manera de hacerlo funcionar con groupBy, con uno termediary paso:

def distinctBy[T, P, From[X] <: TraversableLike[X, From[X]]](collection: From[T])(property: T => P): From[T] = { 
    val uniqueValues: Set[T] = collection.groupBy(property).map(_._2.head)(breakOut) 
    collection.filter(uniqueValues) 
} 

utilizar de esta manera:

scala> distinctBy(List(redVolvo, bluePrius, redLeon))(_.color) 
res0: List[Car] = List(redVolvo, bluePrius) 

Al igual que en la primera solución de IttayD, pero filtra la colección original basado en el conjunto de valores únicos. Si mis expectativas son correctas, esto hace tres cruces: uno para groupBy, uno para map y uno para filter. Mantiene el orden de la colección original, pero no necesariamente toma el primer valor para cada propiedad. Por ejemplo, podría haber devuelto List(bluePrius, redLeon) en su lugar.

Por supuesto, la solución de IttayD es aún más rápida ya que solo realiza un recorrido.

Mi solución también tiene la desventaja de que, si la colección tiene Car s que son realmente iguales, ambos estarán en la lista de salida. Esto podría solucionarse eliminando filter y devolviendo uniqueValues directamente, con el tipo From[T]. Sin embargo, parece que CanBuildFrom[Map[P, From[T]], T, From[T]] no existe ... ¡las sugerencias son bienvenidas!

Answer 6

Con preservar el orden:

def distinctBy[L, E](list: List[L])(f: L => E): List[L] = 
    list.foldLeft((Vector.empty[L], Set.empty[E])) { 
    case ((acc, set), item) => 
     val key = f(item) 
     if (set.contains(key)) (acc, set) 
     else (acc :+ item, set + key) 
    }._1.toList 

distinctBy(list)(_.property)