Один из способов - это
list.distinct.size != list.size
Есть ли лучший способ? Было бы неплохо иметь метод containsDuplicates
Один из способов - это
list.distinct.size != list.size
Есть ли лучший способ? Было бы неплохо иметь метод containsDuplicates
Предполагая, что "лучше" означает "быстрее", см. альтернативные подходы, ориентированные на этот вопрос, который, кажется, показывает некоторые более быстрые методы (хотя обратите внимание, что в отдельности используется HashSet и уже O (n)). YMMV, конечно, в зависимости от конкретного тестового примера, версии scala и т.д. Возможно, какое-либо значительное улучшение по сравнению с подходом "distinct.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)
Вы также можете написать:
list.toSet.size != list.size
Но результат будет тем же, потому что distinct
уже реализован с Set
. В обоих случаях временная сложность должна быть O (n): вы должны пересечь список, а Set
- O (1).
Я думаю, что это остановится, как только будет найден дубликат, и, вероятно, более эффективен, чем делать 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 }
}
@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 'contains (e)' определяется как 'exists (_ == e)', и существует в TraversableLike:
def exists (p: A => Boolean): Boolean = {
var result = false
breakable {
for (x <- this)
if (p (x)) { result = true; break }
}
result
}
Мне интересно, как ускорить работу с параллельными коллекциями на нескольких ядрах, но я думаю, что это общая проблема с ранним возвратом, в то время как другой поток будет продолжать работать, потому что он не знает, что это решение уже найдено.
Резюме:
Я написал очень эффективную функцию, которая возвращает как List.distinct
, так и List
, состоящую из каждого элемента, который появился более одного раза, и индекс, в котором появился дубликат элемента.
Примечание. Этот ответ является прямой копией ответа по соответствующему вопросу.
Детали:
Если вам нужно немного больше информации о самих дубликатах, как и я, я написал более общую функцию, которая повторяется через List
(как упорядочение была значительна) ровно один раз и возвращает Tuple2
, состоящую из оригинала List
debuped (все дубликаты после первого удаляются, то есть то же самое, что и вызов 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)
}
Ниже приведен пример, который может сделать его более интуитивным. Учитывая этот список значений String:
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
... или если a 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_._
.