Scala: удалить дубликаты в списке объектов

Ответ 1

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(). Метод карты создает новую коллекцию путем итерации каждого элемента и применения к нему функции. В этом случае функция _._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 фактически ожидает два аргумента: функцию и объект, которые используются для построения результата. В первом фрагменте кода вы не видите второе значение, потому что оно помечено как неявное и предоставлено компилятором из списка предопределенных значений в области. Результат обычно получается из сопоставленного контейнера. Обычно это хорошо. карта в списке вернет список, карта на массиве вернет Array и т.д. В этом случае мы хотим выразить контейнер, который мы хотим в качестве результата. Здесь используется метод breakOut. Он создает построитель (то, что создает результаты), только глядя на желаемый тип результата. Это общий метод, и компилятор передает свои общие типы, потому что мы явно набрали l2 как List[Object] или, чтобы сохранить порядок (предполагая, что Object#property имеет тип Property):

list.foldRight((List[Object](), Set[Property]())) {
  case (o, [email protected](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))

Также обратите внимание, что это довольно эффективно, поскольку мы используем построитель. Если у вас действительно большие списки, вы можете использовать измененный HashSet вместо обычного набора и оценивать производительность.

Ответ 2

Вот немного проницательное, но быстрое решение, которое сохраняет порядок:

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

Хотя он использует внутренне var, я думаю, что его легче понять и прочитать, чем решение foldLeft.

Ответ 3

Еще одно решение

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

Ответ 4

С порядком сохранения:

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)

Ответ 5

Начиная Scala 2.13, большинство коллекций теперь снабжены B):C rel="nofollow noreferrer"> distinctBy методами, который возвращает все элементы последовательности, игнорируя дубликаты после применения данной функции преобразующей:

list.distinctBy(_.property)

Например:

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

Ответ 6

Я нашел способ заставить его работать с groupBy с одним промежуточным шагом:

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

Используйте его следующим образом:

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

Аналогично первому решению IttayD, но он фильтрует исходную коллекцию на основе набора уникальных значений. Если мои ожидания верны, это делает три обхода: один для groupBy, один для map и один для filter. Он поддерживает порядок первоначальной коллекции, но не обязательно принимает первое значение для каждого свойства. Например, он мог бы вернуть List(bluePrius, redLeon).

Конечно, решение IttayD по-прежнему выполняется быстрее, поскольку он выполняет только один обход.

Мое решение также имеет тот недостаток, что, если коллекция имеет Car, которые на самом деле одинаковы, оба будут в списке вывода. Это можно устранить, удалив filter и возвращая uniqueValues напрямую, с типом From[T]. Однако, похоже, что CanBuildFrom[Map[P, From[T]], T, From[T]] не существует... предложения приветствуются!

Ответ 7

Много хороших ответов выше. Однако distinctBy уже в Scala, но в не столь очевидном месте. Возможно, вы можете использовать его как

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

Ответ 8

Я не знаю, какую версию Scala вы используете, но 2.8.2 определенно имеет

list.distinct

Изменить (фиксировать вниз голоса)

list.distinctBy