Jak w Scali usunąć duplikaty z listy?

Przypuśćmy, że tak

val dirty = List("a", "b", "a", "c")

Czy istnieje operacja na liście, która zwraca „a”, „b”, „c”

Zajrzyj do ScalaDoc dla Seq ,

scala> dirty.distinct
res0: List[java.lang.String] = List(a, b, c)

Aktualizuj . Inni sugerowali użycie Setzamiast List. To dobrze, ale pamiętaj, że domyślnie Setinterfejs nie zachowuje kolejności elementów. Możesz użyć zestawu realizację jawnie nie zachowania porządku, takie jak collection.mutable.LinkedHashSet .

scala.collection.immutable.Listteraz ma .distinctmetodę.

Więc dzwonienie dirty.distinctjest teraz możliwe bez konwertowania na Setlub Seq.

Przed użyciem rozwiązania Kitpon pomyśl o użyciu a, Seta nie a List, zapewnia to, że każdy element jest wyjątkowy.

Jak większość operacji list ( foreach, map, filter, ...) są takie same dla zbiorów i list, zmieniając kolekcji może być bardzo łatwy w kodzie.

Korzystanie z Set w pierwszej kolejności jest oczywiście właściwą drogą, ale:

scala> List("a", "b", "a", "c").toSet.toList
res1: List[java.lang.String] = List(a, b, c)

Pracuje. Lub po prostu toSetobsługujeSeq Traversable berło.

Listy już posortowane

Jeśli chcesz, aby poszczególne elementy listy, o których wiesz, że są już posortowane , jak często potrzebowałem, następujące czynności działają około dwa razy szybciej niż .distinct:

  def distinctOnSorted[V](seq: List[V]): List[V] =
    seq.foldLeft(List[V]())((result, v) =>
      if (result.isEmpty || v != result.head) v :: result else result)
    .reverse

Wyniki wydajności na liście 100 000 000 losowych Intów od 0 do 99:

distinct        : 0.6655373s
distinctOnSorted: 0.2848134s

Wydajność z MutableList lub ListBuffer

Chociaż mogłoby się wydawać, że bardziej zmienne / niefunkcjonalne podejście do programowania może być szybsze niż poprzedzanie niezmiennej listy, praktyka pokazuje inaczej. Niezmienna implementacja konsekwentnie działa lepiej. Domyślam się, że powodem jest to, że scala koncentruje swoje optymalizacje kompilatora na niezmiennych kolekcjach i dobrze sobie z tym radzi. (Zapraszam innych do przesyłania lepszych wdrożeń.)

List size 1e7, random 0 to 1e6
------------------------------
distinct            : 4562.2277ms
distinctOnSorted    : 201.9462ms
distinctOnSortedMut1: 4399.7055ms
distinctOnSortedMut2: 246.099ms
distinctOnSortedMut3: 344.0758ms
distinctOnSortedMut4: 247.0685ms

List size 1e7, random 0 to 100
------------------------------
distinct            : 88.9158ms
distinctOnSorted    : 41.0373ms
distinctOnSortedMut1: 3283.8945ms
distinctOnSortedMut2: 54.4496ms
distinctOnSortedMut3: 58.6073ms
distinctOnSortedMut4: 51.4153ms

Wdrożenia:

object ListUtil {
  def distinctOnSorted[V](seq: List[V]): List[V] =
    seq.foldLeft(List[V]())((result, v) =>
      if (result.isEmpty || v != result.head) v :: result else result)
    .reverse

  def distinctOnSortedMut1[V](seq: List[V]): Seq[V] = {
    if (seq.isEmpty) Nil
    else {
      val result = mutable.MutableList[V](seq.head)
      seq.zip(seq.tail).foreach { case (prev, next) =>
        if (prev != next) result += next
      }
      result //.toList
    }
  }

  def distinctOnSortedMut2[V](seq: List[V]): Seq[V] = {
    val result = mutable.MutableList[V]()
    if (seq.isEmpty) return Nil
    result += seq.head
    var prev = seq.head
    for (v <- seq.tail) {
      if (v != prev) result += v
      prev = v
    }
    result //.toList
  }

  def distinctOnSortedMut3[V](seq: List[V]): List[V] = {
    val result = mutable.MutableList[V]()
    if (seq.isEmpty) return Nil
    result += seq.head
    var prev = seq.head
    for (v <- seq.tail) {
      if (v != prev) v +=: result
      prev = v
    }
    result.reverse.toList
  }

  def distinctOnSortedMut4[V](seq: List[V]): Seq[V] = {
    val result = ListBuffer[V]()
    if (seq.isEmpty) return Nil
    result += seq.head
    var prev = seq.head
    for (v <- seq.tail) {
      if (v != prev) result += v
      prev = v
    }
    result //.toList
  }
}

Test:

import scala.util.Random

class ListUtilTest extends UnitSpec {
  "distinctOnSorted" should "return only the distinct elements in a sorted list" in {
    val bigList = List.fill(1e7.toInt)(Random.nextInt(100)).sorted

    val t1 = System.nanoTime()
    val expected = bigList.distinct
    val t2 = System.nanoTime()
    val actual = ListUtil.distinctOnSorted[Int](bigList)
    val t3 = System.nanoTime()
    val actual2 = ListUtil.distinctOnSortedMut1(bigList)
    val t4 = System.nanoTime()
    val actual3 = ListUtil.distinctOnSortedMut2(bigList)
    val t5 = System.nanoTime()
    val actual4 = ListUtil.distinctOnSortedMut3(bigList)
    val t6 = System.nanoTime()
    val actual5 = ListUtil.distinctOnSortedMut4(bigList)
    val t7 = System.nanoTime()

    actual should be (expected)
    actual2 should be (expected)
    actual3 should be (expected)
    actual4 should be (expected)
    actual5 should be (expected)

    val distinctDur = t2 - t1
    val ourDur = t3 - t2

    ourDur should be < (distinctDur)

    print(s"distinct            : ${distinctDur / 1e6}ms\n")
    print(s"distinctOnSorted    : ${ourDur / 1e6}ms\n")
    print(s"distinctOnSortedMut1: ${(t4 - t3) / 1e6}ms\n")
    print(s"distinctOnSortedMut2: ${(t5 - t4) / 1e6}ms\n")
    print(s"distinctOnSortedMut3: ${(t6 - t5) / 1e6}ms\n")
    print(s"distinctOnSortedMut4: ${(t7 - t6) / 1e6}ms\n")
  }
}

Możesz także użyć rekursji i dopasowania wzorców:

def removeDuplicates[T](xs: List[T]): List[T] = xs match {
  case Nil => xs
  case head :: tail => head :: removeDuplicates(for (x <- tail if x != head) yield x)
}

inArr.distinct foreach println _

Algorytmiczny sposób ...

def dedupe(str: String): String = {
  val words = { str split " " }.toList

  val unique = words.foldLeft[List[String]] (Nil) {
    (l, s) => {
      val test = l find { _.toLowerCase == s.toLowerCase } 
      if (test == None) s :: l else l
    }
  }.reverse

  unique mkString " "
}