Scala : 개체 목록에서 중복 제거

Scala : 개체 목록에서 중복 제거

---

List[Object]동일한 클래스에서 모두 인스턴스화 된 개체 목록이 있습니다 . 이 클래스에는 고유해야하는 필드가 있습니다 Object.property. 객체 목록을 반복하고 동일한 속성을 가진 모든 객체 (첫 번째)를 제거하는 가장 깨끗한 방법은 무엇입니까?

---

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

설명 : groupBy 메소드는 그룹화를 위해 요소를 키로 변환하는 함수를 승인합니다. _.property단지 속기이다 elem: Object => elem.property(컴파일러, 같은 것을 고유 한 이름을 생성합니다 x$1). 이제지도가 생겼습니다 Map[Property, List[Object]]. A는 Map[K,V]확장 Traversable[(K,V)]. 따라서 목록처럼 순회 할 수 있지만 요소는 튜플입니다. 이것은 Java의 Map#entrySet(). map 메서드는 각 요소를 반복하고 여기에 함수를 적용하여 새 컬렉션을 만듭니다. 이 경우, 함수는 _._2.head속기이다 elem: (Property, List[Object]) => elem._2.head. _2두 번째 요소를 반환하는 Tuple의 메서드 일뿐입니다. 두 번째 요소는 List [Object]이며 head첫 번째 요소를 반환합니다.

원하는 유형이되도록 결과를 얻으려면 :

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

간단히 설명하기 위해 map실제로는 결과를 구성하는 데 사용되는 함수와 객체라는 두 개의 인수가 필요합니다. 첫 번째 코드 조각에서는 두 번째 값이 암시 적으로 표시되고 컴파일러가 범위의 미리 정의 된 값 목록에서 제공하므로 두 번째 값이 표시되지 않습니다. 결과는 일반적으로 매핑 된 컨테이너에서 가져옵니다. 이것은 일반적으로 좋은 것입니다. map on List는 List를 반환하고, map on Array는 Array 등을 반환합니다. 그러나이 경우 원하는 컨테이너를 결과로 표현하고 싶습니다. 브레이크 아웃 방법이 사용되는 곳입니다. 원하는 결과 유형 만보고 빌더 (결과를 빌드하는 것)를 구성합니다. 이것은 제네릭 메서드이고 컴파일러는 List[Object]순서를 유지하기 위해 l2를 명시 적으로 형식화했기 때문에 제네릭 형식을 유추합니다 ( Object#property형식이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초기 결과를 받아들이는 메서드와 요소를 받아들이고 업데이트 된 결과를 반환하는 함수입니다. 이 메서드는 각 요소를 반복하여 각 요소에 함수를 적용하고 최종 결과를 반환하여 결과를 업데이트합니다. 우리 foldLeft는 앞에 붙기 때문에 오른쪽에서 왼쪽으로 이동합니다 (를 사용하여 왼쪽에서 오른쪽으로 이동하지 않음) objects-이것은 O (1)이지만 추가는 O (N)입니다. 또한 여기서 좋은 스타일링을 관찰하고 패턴 일치를 사용하여 요소를 추출합니다.

이 경우 초기 결과는 빈 목록과 집합의 쌍 (튜플)입니다. 목록은 우리가 관심있는 결과이며 집합은 우리가 이미 발견 한 속성을 추적하는 데 사용됩니다. 각 반복에서 집합에 props이미 속성이 포함되어 있는지 확인합니다 (Scala에서는 . 에서 obj(x)로 번역됨 obj.apply(x). Set에서 메서드 apply는 def apply(a: A): Boolean입니다. 즉, 요소를 받아들이고 존재 여부에 따라 true / false를 반환합니다). 속성이 존재하는 경우 (이미 발생한 경우) 결과는있는 그대로 반환됩니다. 그렇지 않으면 결과가 객체 ( o :: objects) 를 포함하도록 업데이트되고 속성이 기록됩니다 ( props + o.property).

업데이트 : @andreypopp는 일반적인 방법을 원했습니다.

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)

쓰다:

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

Also note that this is pretty efficient as we are using a builder. If you have really large lists, you may want to use a mutable HashSet instead of a regular set and benchmark the performance.

---

Here is a little bit sneaky but fast solution that preserves order:

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

Although it uses internally a var, I think it is easier to understand and to read than the foldLeft-solution.

---

Starting Scala 2.13, most collections are now provided with a distinctBy method which returns all elements of the sequence ignoring the duplicates after applying a given transforming function:

list.distinctBy(_.property)

For instance:

List(("a", 2), ("b", 2), ("a", 5)).distinctBy(_._1) // List((a,2), (b,2))
List(("a", 2.7), ("b", 2.1), ("a", 5.4)).distinctBy(_._2.floor) // List((a,2.7), (a,5.4))

---

One more solution

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

---

With preserve order:

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)

---

I found a way to make it work with groupBy, with one intermediary step:

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

Use it like this:

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

Similar to IttayD's first solution, but it filters the original collection based on the set of unique values. If my expectations are correct, this does three traversals: one for groupBy, one for map and one for filter. It maintains the ordering of the original collection, but does not necessarily take the first value for each property. For example, it could have returned List(bluePrius, redLeon) instead.

Of course, IttayD's solution is still faster since it does only one traversal.

My solution also has the disadvantage that, if the collection has Cars that are actually the same, both will be in the output list. This could be fixed by removing filter and returning uniqueValues directly, with type From[T]. However, it seems like CanBuildFrom[Map[P, From[T]], T, From[T]] does not exist... suggestions are welcome!

---

A lot of good answers above. However, distinctBy is already in Scala, but in a not-so-obvious place. Perhaps you can use it like

def distinctBy[A, B](xs: List[A])(f: A => B): List[A] =
  scala.reflect.internal.util.Collections.distinctBy(xs)(f)

ReferenceURL : https://stackoverflow.com/questions/3912753/scala-remove-duplicates-in-list-of-objects