Scala: Usuń duplikaty na liście obiektów

Question

Mam listę obiektów List[Object], które są wszystkie utworzone z tej samej klasy. Ta klasa ma pole, które musi być unikatowe: Object.property. Jaki jest najczystszy sposób na iterowanie listy obiektów i usuwanie wszystkich obiektów (ale tych pierwszych) o tej samej właściwości?

Answer 1

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

Objaśnienie: Metoda groupBy akceptuje funkcję, która konwertuje element na klucz w celu grupowania. _.property jest skrótem dla elem: Object => elem.property (kompilator generuje unikalną nazwę, podobną do x$1). Teraz mamy mapę Map[Property, List[Object]]. A Map[K,V] rozciąga się na Traversable[(K,V)]. Tak więc można go przemierzać jak listę, ale elementy są krotką. Jest to podobne do Javy Map#entrySet(). Metoda map tworzy nową kolekcję poprzez iterowanie każdego elementu i stosowanie do niego funkcji. W tym przypadku funkcją jest _._2.head, która jest skrótem dla elem: (Property, List[Object]) => elem._2.head. _2 to tylko metoda Tuple, która zwraca drugi element. Drugim elementem jest Lista [Obiekt] i head zwraca pierwszy element

Aby uzyskać wynik za typ chcesz:

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

krótko wyjaśnić, map faktycznie oczekuje dwóch argumentów funkcji i obiekt, który jest używany do konstruowania wyniku. W pierwszym fragmencie kodu nie widzisz drugiej wartości, ponieważ jest ona oznaczona jako niejawna, a więc podana przez kompilator z listy wstępnie zdefiniowanych wartości w zakresie. Wynik jest zwykle uzyskiwany z odwzorowanego kontenera. Zazwyczaj jest to dobre. mapa na liście zwróci listę, mapa na tablicy zwróci tablicę itp. W tym przypadku jednak chcemy wyrazić kontener, który chcemy jako wynik. Tutaj jest używana metoda breakOut. Konstruuje konstruktora (rzecz, która buduje wyniki), patrząc tylko na pożądany typ wyniku. Jest to sposób ogólny i kompilator wyprowadza swoje ogólne typy ponieważ wyraźnie określony L2 być List[Object] lub zachowania kolejności (zakładając Object#property jest typu 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 jest metodą, która przyjmuje wstępną rezultat i funkcja, która akceptuje element i zwraca zaktualizowany wynik. Metoda iteruje każdy element, aktualizując wynik zgodnie z zastosowaniem funkcji do każdego elementu i zwracając końcowy wynik. Przechodzimy od prawej do lewej (zamiast od lewej do prawej z foldLeft), ponieważ mamy przedrostek objects - jest to O (1), ale dołączenie to O (N). Zwróć też uwagę na dobrą stylizację, używamy dopasowania wzoru, aby wyodrębnić elementy.

W tym przypadku początkowy wynik to para (krotka) pustej listy i zestawu. Lista jest wynikiem, który nas interesuje, a zestaw służy do śledzenia właściwości, które już napotkaliśmy. W każdej iteracji sprawdzamy, czy zestaw props już zawiera właściwość (w Scali, obj(x) jest tłumaczony na obj.apply(x). W Set, metoda apply jest def apply(a: A): Boolean. Oznacza to, że akceptuje element i zwraca true/false, jeśli istnieje lub nie). Jeśli właściwość istnieje (już się pojawiła), wynik jest zwracany w stanie, w jakim się znajduje.W przeciwnym razie wynikiem jest aktualizowana zawierać obiekt (o :: objects), a nieruchomość jest rejestrowana (props + o.property)

Aktualizacja: @andreypopp chciał metoda rodzajowa:

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) 

do wykorzystania:

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

Zauważ, że jest to całkiem efektywne, ponieważ korzystamy z programu budującego. Jeśli masz naprawdę duże listy, możesz użyć zmiennego HashSet zamiast zwykłego zestawu i porównać wydajność.

Answer 2

Tutaj jest trochę podstępne ale szybkie rozwiązanie, które zachowuje kolejność:

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

Choć używa wewnętrznie var, myślę, że łatwiej jest zrozumieć i odczytać niż foldLeft roztworu.

Answer 3

Jeszcze rozwiązanie

@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

nie wiem, która wersja Scali używasz, ale 2.8.2 pewno ma

list.distinct 

Edycja (fixing głosów w dół)

list.distinctBy 

Answer 5

Znalazłem sposób na to, aby działało z groupBy, z jednym w termediary krok:

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) 
} 

Używaj go tak:

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

Podobnie do pierwszego rozwiązania IttayD, ale filtruje oryginalną kolekcję w oparciu o zestaw unikatowych wartości. Jeśli moje oczekiwania są poprawne, wykonuje się trzy traversals: jeden dla groupBy, jeden dla map i jeden dla filter. Utrzymuje porządek oryginalnej kolekcji, ale niekoniecznie pobiera pierwszą wartość dla każdej właściwości. Na przykład mógł zamiast niego powrócić List(bluePrius, redLeon).

Oczywiście, rozwiązanie IttayD jest jeszcze szybsze, ponieważ wykonuje tylko jedno przejście.

Moje rozwiązanie ma także tę wadę, że jeśli kolekcja ma takie same zbiory, oba będą na liście wyjściowej. Można to naprawić, usuwając filter i zwracając bezpośrednio uniqueValues, z typem From[T]. Jednak wydaje się, że CanBuildFrom[Map[P, From[T]], T, From[T]] nie istnieje ... sugestie są mile widziane!

Answer 6

Z zachować porządek:

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)