最簡單的方法來決定列表是否包含重複？

Question

一種方法是這樣的

list.distinct.size != list.size 

有沒有什麼更好的辦法？這本來是很高興有一個containsDuplicates方法

Answer 1

假設「更好」意味着「更快」，請參見this question中的基準測試方法，該方法似乎顯示了一些更快的方法（儘管注意不同的方法使用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) 

Answer 2

你也可以這樣寫：

list.toSet.size != list.size 

但結果是一樣的，因爲distinct已經implemented with a 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 

我知道你要的容易，我現在這個版本是不這樣做，但要找到一個副本也發現，如果有一個EL以前已經被視爲EMENT：

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。

注意：這個答案是一個straight copy of the answer on a related question。

詳情： 如果您需要一點點關於重複自己的詳細信息，像我一樣，我已經寫了這迭代跨越List（如排序是顯著）一次，以及返回Tuple2由一個更一般的功能的原始List（第一個被刪除後的所有副本都被刪除;即與調用distinct相同），第二個List顯示了每個副本以及在原始List內發生的Int索引。

這裏的功能：

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功能的直接副本n我的開源Scala庫，ScalaOlio。它位於org.scalaolio.collection.immutable.List_._。