Cách dễ nhất để quyết định xem Danh sách có chứa các bản sao không?

Question

Một chiều là

list.distinct.size != list.size 

Có cách nào tốt hơn không? Nó sẽ được tốt đẹp để có một phương pháp

Answer 1

Giả sử "tốt hơn" có nghĩa là "nhanh hơn", xem các phương pháp thay thế được đánh giá trong this question, có vẻ như hiển thị một số phương pháp nhanh hơn (mặc dù lưu ý rằng sử dụng riêng biệt HashSet và đã là O (n)). YMMV tất nhiên, tùy thuộc vào trường hợp thử nghiệm cụ thể, phiên bản scala vv Có lẽ bất kỳ cải tiến đáng kể nào đối với phương pháp "distinct.size" sẽ xuất phát từ sớm khi phát hiện trùng lặp, nhưng tốc độ tăng lên là bao nhiêu thực sự thu được sẽ phụ thuộc mạnh mẽ vào cách các bản sao phổ biến thực sự nằm trong trường hợp sử dụng của bạn.

Nếu bạn có nghĩa là "tốt hơn" ở chỗ bạn muốn viết list.containsDuplicates thay vì containsDuplicates(list), sử dụng một ẩn:

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

containsDuplicates Bạn cũng có thể viết:

list.toSet.size != list.size 

Nhưng kết quả sẽ giống nhau vì distinct đã là implemented with a Set. Trong cả hai trường hợp độ phức tạp thời gian phải là O (n): bạn phải duyệt qua danh sách và chèn Set là O (1).

Answer 3

Tôi nghĩ rằng đây sẽ dừng lại càng sớm càng một bản sao đã được tìm thấy và có lẽ là hiệu quả hơn làm distinct.size - kể từ khi tôi giả định distinct tục một tập cũng như:

@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 

tôi nhận ra bạn yêu cầu dễ dàng và tôi làm không phải bây giờ mà phiên bản này, nhưng việc tìm kiếm một bản sao cũng được tìm nếu có một el ement đã được thấy trước đây:

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) 

Tôi không biện pháp này, và nghĩ rằng đó là tương tự như giải pháp huynhjl, nhưng đơn giản hơn một chút để hiểu được.

Nó trả về sớm, nếu tìm thấy trùng lặp, vì vậy tôi đã xem xét nguồn gốc của Seq.contains, cho dù điều này có trả về sớm hay không.

Trong SeqLike, 'chứa (e)' được định nghĩa là 'tồn tại (_ == e)', và tồn tại được định nghĩa trong TraversableLike:

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

tôi tò mò làm thế nào để điều tốc độ lên với các bộ sưu tập song song trên nhiều lõi, nhưng tôi đoán đó là một vấn đề chung với việc trả về sớm, trong khi một luồng khác sẽ tiếp tục chạy, bởi vì nó không biết, rằng giải pháp đã được tìm thấy.

Answer 5

Tóm tắt: Tôi đã viết một chức năng rất hiệu quả mà trả cả List.distinct và List gồm mỗi phần tử xuất hiện nhiều hơn một lần và chỉ số mà tại đó các yếu tố trùng lặp xuất hiện.

Lưu ý: Câu trả lời này là straight copy of the answer on a related question.

chi tiết: Nếu bạn cần thêm một chút thông tin về các bản sao bản thân, giống như tôi đã làm, tôi đã viết một hàm tổng quát hơn mà lặp qua một List (như đặt hàng là đáng kể) đúng một lần và trả về một Tuple2 gồm của bản gốc List được khấu trừ (tất cả các bản sao sau lần đầu tiên được loại bỏ; tức là giống như cách gọi distinct) và một số thứ hai List hiển thị từng bản sao và chỉ mục Int mà nó xảy ra trong bản gốc List.

Dưới đây là các chức năng:

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

Một dưới đây là một ví dụ mà có thể làm cho nó trực quan hơn một chút. Với này Danh sách giá trị String:

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

... và sau đó thực hiện như sau:

val (deduped, dupeAndIndexs) = 
    filterDupes(withDupes) 

... kết quả là:

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

Và nếu bạn chỉ muốn trùng lặp, bạn chỉ cần map trên dupeAndIndexes và gọi distinct:

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

... hoặc tất cả trong một cuộc gọi duy nhất:

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

... hoặc nếu một Set được ưa thích, bỏ qua distinct và gọi toSet ...

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

... hoặc tất cả trong một cuộc gọi duy nhất:

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

Đây là bản sao thẳng của filterDupes functio n trong thư viện Scala nguồn mở của tôi, ScalaOlio. Nó nằm ở org.scalaolio.collection.immutable.List_._.