Di Scala bagaimana cara menghapus duplikat dari daftar?

Misalkan saya punya

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

Apakah ada operasi daftar yang mengembalikan "a", "b", "c"

Lihat ScalaDoc untuk Seq ,

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

Perbarui . Orang lain menyarankan untuk menggunakan Setdaripada List. Tidak apa-apa, tetapi ketahuilah bahwa secara default, Setantarmuka tidak mempertahankan urutan elemen. Anda mungkin ingin menggunakan implementasi Set yang secara eksplisit tidak mempertahankan ketertiban, seperti collection.mutable.LinkedHashSet .

scala.collection.immutable.Listsekarang punya .distinctmetode.

Jadi, panggilan dirty.distinctsekarang dapat dilakukan tanpa mengubah ke Setatau Seq.

Sebelum menggunakan solusi Kitpon, pertimbangkan untuk menggunakan a Setdaripada a List, ini memastikan setiap elemen unik.

Seperti kebanyakan daftar operasi ( foreach, map, filter, ...) adalah sama untuk set dan daftar, mengubah koleksi bisa sangat mudah dalam kode.

Menggunakan Set di tempat pertama adalah cara yang tepat untuk melakukannya, tentu saja, tetapi:

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

Bekerja. Atau hanya toSetkarena mendukung fileSeq Traversable antarmuka.

Untuk Daftar yang Sudah Disortir

Jika Anda kebetulan ingin item berbeda dari daftar yang Anda tahu sudah diurutkan , seperti yang sering saya butuhkan, berikut ini bekerja sekitar dua kali kecepatannya .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

Hasil kinerja pada daftar 100.000.000 Ints acak dari 0-99:

distinct        : 0.6655373s
distinctOnSorted: 0.2848134s

Performa dengan MutableList atau ListBuffer

Meskipun tampaknya pendekatan pemrograman yang lebih dapat diubah / tidak berfungsi mungkin lebih cepat daripada mempersiapkan ke daftar yang tidak dapat diubah, praktik menunjukkan sebaliknya. Implementasi yang tidak dapat diubah secara konsisten berkinerja lebih baik. Dugaan saya untuk alasannya adalah bahwa scala memfokuskan pengoptimalan kompilernya pada koleksi yang tidak dapat diubah, dan melakukan pekerjaan dengan baik. (Saya menyambut orang lain untuk mengirimkan implementasi yang lebih baik.)

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

Implementasi:

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

Uji:

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

Anda juga dapat menggunakan rekursi dan pencocokan pola:

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 untuk setiap println _

Cara algoritmik ...

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