Самый простой способ решить, если список содержит дубликаты?

Question

В одну сторону это

list.distinct.size != list.size

Есть ли лучший способ? Было бы неплохо иметь containsDuplicates метод

Answer 1

Предполагая, что «лучше» означает «быстрее», см. Альтернативные подходы, отмеченные в этом вопросе , который, кажется, показывает некоторые более быстрые методы (хотя обратите внимание, что враздел использует HashSet и уже равен O (n)),Конечно, YMMV, в зависимости от конкретного тестового примера, версии scala и т. Д. Вероятно, любое существенное улучшение по сравнению с подходом «Different.size» появилось бы на раннем этапе, как только будет найден дубликат, но насколько это ускорение.фактически полученный результат будет сильно зависеть от того, насколько часто встречаются дубликаты в вашем сценарии использования.

Если вы имеете в виду «лучше» в том смысле, что вы хотите написать list.containsDuplicates вместо containsDuplicates(list), используйте неявное:

implicit def enhanceWithContainsDuplicates[T](s:List[T]) = new {
  def containsDuplicates = (s.distinct.size != s.size)
}

assert(List(1,2,2,3).containsDuplicates)
assert(!List("a","b","c").containsDuplicates)

Answer 2

Вы также можете написать:

list.toSet.size != list.size

Но результат будет таким же, потому что distinct уже реализован с Set. В обоих случаях временная сложность должна составлять O (n) : вы должны пройти по списку, а Set вставка будет O (1) .

Answer 3

Я думаю, что это прекратится, как только будет найден дубликат, и, вероятно, будет более эффективным, чем distinct.size - поскольку я предполагаю, что distinct также сохраняет набор:

@annotation.tailrec
def containsDups[A](list: List[A], seen: Set[A] = Set[A]()): Boolean = 
  list match {
    case x :: xs => if (seen.contains(x)) true else containsDups(xs, seen + x)
    case _ => false
}

containsDups(List(1,1,2,3))
// Boolean = true

containsDups(List(1,2,3))
// Boolean = false

Я понимаю, что выЯ спрашиваю легко, и теперь я не знаю, есть ли эта версия, но поиск дубликата также позволяет определить, был ли элемент, который был замечен ранее:

def containsDups[A](list: List[A]): Boolean =  {
  list.iterator.scanLeft(Set[A]())((set, a) => set + a) // incremental sets
    .zip(list.iterator)
    .exists{ case (set, a) => set contains a }
}

Answer 4

@annotation.tailrec 
def containsDuplicates [T] (s: Seq[T]) : Boolean = 
  if (s.size < 2) false else 
    s.tail.contains (s.head) || containsDuplicates (s.tail)

Я не измерял это, и думаю, что оно похоже на решение huynhjl, но немного проще для понимания.

Возвращается рано, если найден дубликат, поэтому я посмотрел на источник Seq.contains, возвращается ли он рано - да.

В SeqLike значение «содержит (e)» определяется как «существует (_ == e)», а существует определяется в TraversableLike:

def exists (p: A => Boolean): Boolean = {
  var result = false
  breakable {
    for (x <- this)
      if (p (x)) { result = true; break }
  }
  result
}

Мне любопытно, как ускорить процесс с параллельными коллекциями на нескольких ядрах, но я думаю, что это общая проблема с ранним возвратом, в то время как другой поток продолжит работать, потому что он не знает, что решение уже найден.

Answer 5

Резюме: Я написал очень эффективную функцию, которая возвращает List.distinct и List, состоящие из каждого элемента, который появился более одного раза, и индекса, в котором появился дубликат элемента.

Примечание. Этот ответ представляет собой прямую копию ответа на связанный вопрос .

Подробности: Если вам нужна дополнительная информация оСами же дубликаты, как и я, я написал более общую функцию, которая перебирает List (поскольку порядок был значительным) ровно один раз и возвращает Tuple2, состоящий из дедуплированного исходного List (все дубликаты после первогоудален, т. е. аналогично вызову distinct) и второй List, показывающей каждый дубликат и индекс Int, при котором он произошел в исходном List.

Вот функция:

def filterDupes[A](items: List[A]): (List[A], List[(A, Int)]) = {
  def recursive(remaining: List[A], index: Int, accumulator: (List[A], List[(A, Int)])): (List[A], List[(A, Int)]) =
    if (remaining.isEmpty)
      accumulator
    else
      recursive(
          remaining.tail
        , index + 1
        , if (accumulator._1.contains(remaining.head))
            (accumulator._1, (remaining.head, index) :: accumulator._2)
          else
            (remaining.head :: accumulator._1, accumulator._2)
      )
  val (distinct, dupes) = recursive(items, 0, (Nil, Nil))
  (distinct.reverse, dupes.reverse)
}

Ниже приведен пример, который может сделать его немного более интуитивным.Учитывая этот список значений строк:

val withDupes =
  List("a.b", "a.c", "b.a", "b.b", "a.c", "c.a", "a.c", "d.b", "a.b")

... и затем выполняя следующее:

val (deduped, dupeAndIndexs) =
  filterDupes(withDupes)

... результаты будут такими:

deduped: List[String] = List(a.b, a.c, b.a, b.b, c.a, d.b)
dupeAndIndexs: List[(String, Int)] = List((a.c,4), (a.c,6), (a.b,8))

И если вам просто нужны дубликаты, вы просто map через dupeAndIndexes и вызываете distinct:

val dupesOnly =
  dupeAndIndexs.map(_._1).distinct

... или все за один вызов:

val dupesOnly =
  filterDupes(withDupes)._2.map(_._1).distinct

... или, если предпочтительным является Set, пропустите distinct и вызовите toSet ...

val dupesOnly2 =
  dupeAndIndexs.map(_._1).toSet

... или все в одном вызове:

val dupesOnly2 =
  filterDupes(withDupes)._2.map(_._1).toSet

Это прямая копия функции filterDupes из моей библиотеки Scala с открытым исходным кодом, ScalaOlio .Он расположен на org.scalaolio.collection.immutable.List_._.

Answer 6

Если вы пытаетесь проверить дубликаты в тесте, ScalaTest может быть полезен.

import org.scalatest.Inspectors._
import org.scalatest.Matchers._
forEvery(list.distinct) { item =>
  withClue(s"value $item, the number of occurences") {
    list.count(_ == item) shouldBe 1
  }
}

// example:
scala> val list = List(1,2,3,4,3,2)
list: List[Int] = List(1, 2, 3, 4, 3, 2)

scala> forEvery(list) { item => withClue(s"value $item, the number of occurences") { list.count(_ == item) shouldBe 1 } }
org.scalatest.exceptions.TestFailedException: forEvery failed, because:
  at index 1, value 2, the number of occurences 2 was not equal to 1 (<console>:19),
  at index 2, value 3, the number of occurences 2 was not equal to 1 (<console>:19)
in List(1, 2, 3, 4)