Scala: Xóa các mục trùng lặp trong danh sách các đối tượng

Question

Tôi đã có một danh sách các đối tượng List[Object] được khởi tạo từ cùng một lớp. Lớp này có trường phải là duy nhất Object.property. Cách sạch nhất để lặp lại danh sách các đối tượng và loại bỏ tất cả các đối tượng (nhưng đối tượng đầu tiên) với cùng một thuộc tính là gì?

Answer 1

list.groupBy(_.property).map(_._2.head) 

Giải thích: Phương pháp groupBy chấp nhận chức năng chuyển đổi phần tử thành khóa để nhóm. _.property chỉ là viết tắt của elem: Object => elem.property (trình biên dịch tạo ra một tên duy nhất, chẳng hạn như x$1). Vì vậy, bây giờ chúng tôi có một bản đồ Map[Property, List[Object]]. A Map[K,V] mở rộng Traversable[(K,V)]. Vì vậy, nó có thể được duyệt qua như một danh sách, nhưng các phần tử là một bộ tuple. Điều này tương tự như của Java Map#entrySet(). Phương thức bản đồ tạo ra một bộ sưu tập mới bằng cách lặp lại từng phần tử và áp dụng một hàm cho nó. Trong trường hợp này, hàm là _._2.head là viết tắt của elem: (Property, List[Object]) => elem._2.head. _2 chỉ là một phương thức Tuple trả về phần tử thứ hai. Yếu tố thứ hai là Danh sách [Object] và head trả về phần tử đầu tiên

Để có được kết quả là một loại mà bạn muốn:

import collection.breakOut 
val l2: List[Object] = list.groupBy(_.property).map(_._2.head)(breakOut) 

Để giải thích ngắn gọn, map thực sự hy vọng hai đối số, một chức năng và một đối tượng được sử dụng để xây dựng kết quả. Trong đoạn mã đầu tiên bạn không thấy giá trị thứ hai vì nó được đánh dấu là ngầm định và do trình biên dịch cung cấp từ một danh sách các giá trị được xác định trước trong phạm vi. Kết quả thường thu được từ vùng chứa được ánh xạ. Đây thường là một điều tốt. map trên List sẽ trả về List, map trên Array sẽ trả về Array… Trong trường hợp này tuy nhiên, chúng ta muốn thể hiện container mà chúng ta muốn là kết quả. Đây là nơi mà phương thức breakOut được sử dụng. Nó xây dựng một người xây dựng (điều mà xây dựng kết quả) bằng cách chỉ nhìn vào kiểu kết quả mong muốn. Nó là một phương pháp chung chung và trình biên dịch suy luận kiểu generic của nó bởi vì chúng tôi đã gõ một cách rõ ràng l2 là List[Object] hoặc, giữ gìn trật tự (giả sử Object#property là loại Property):

list.foldRight((List[Object](), Set[Property]())) { 
    case (o, cum@(objects, props)) => 
    if (props(o.property)) cum else (o :: objects, props + o.property)) 
}._1 

foldRight là một phương pháp mà chấp nhận một kết quả ban đầu và một hàm chấp nhận phần tử và trả về kết quả được cập nhật. Phương thức lặp lại từng phần tử, cập nhật kết quả theo áp dụng hàm cho mỗi phần tử và trả về kết quả cuối cùng. Chúng tôi đi từ phải sang trái (chứ không phải từ trái sang phải với foldLeft) bởi vì chúng tôi đang chờ thêm objects - đây là O (1), nhưng phụ thêm là O (N). Cũng quan sát phong cách tốt ở đây, chúng tôi đang sử dụng một mẫu phù hợp để trích xuất các yếu tố.

Trong trường hợp này, kết quả ban đầu là một cặp (tuple) của danh sách trống và một bộ. Danh sách là kết quả mà chúng tôi quan tâm và tập hợp được sử dụng để theo dõi những thuộc tính mà chúng tôi đã gặp phải. Trong mỗi lần lặp chúng tôi kiểm tra xem tập hợp props đã chứa thuộc tính (trong Scala, obj(x) được dịch sang obj.apply(x). Trong Set, phương pháp apply là def apply(a: A): Boolean. Tức là chấp nhận một phần tử và trả về true/false nếu nó tồn tại hay không). Nếu thuộc tính tồn tại (đã gặp phải), kết quả sẽ được trả về.Nếu không kết quả được cập nhật để chứa các đối tượng (o :: objects) và tài sản được ghi nhận (props + o.property)

Cập nhật: @andreypopp muốn có một phương pháp chung:

import scala.collection.IterableLike 
import scala.collection.generic.CanBuildFrom 

class RichCollection[A, Repr](xs: IterableLike[A, Repr]){ 
    def distinctBy[B, That](f: A => B)(implicit cbf: CanBuildFrom[Repr, A, That]) = { 
    val builder = cbf(xs.repr) 
    val i = xs.iterator 
    var set = Set[B]() 
    while (i.hasNext) { 
     val o = i.next 
     val b = f(o) 
     if (!set(b)) { 
     set += b 
     builder += o 
     } 
    } 
    builder.result 
    } 
} 

implicit def toRich[A, Repr](xs: IterableLike[A, Repr]) = new RichCollection(xs) 

sử dụng:

scala> list.distinctBy(_.property) 
res7: List[Obj] = List(Obj(1), Obj(2), Obj(3)) 

Cũng lưu ý rằng điều này khá hiệu quả vì chúng tôi đang sử dụng trình tạo. Nếu bạn có danh sách thực sự lớn, bạn có thể muốn sử dụng một HashSet có thể thay đổi thay vì một tập hợp thông thường và đánh giá hiệu suất.

Answer 2

Dưới đây là một giải pháp lén lút nhưng nhanh chút mà giữ gìn trật tự:

list.filterNot{ var set = Set[Property]() 
    obj => val b = set(obj.property); set += obj.property; b} 

Mặc dù nó sử dụng trong nội bộ một var, tôi nghĩ rằng đó là dễ dàng hơn để hiểu và đọc hơn foldLeft-giải pháp.

Answer 3

Thêm một giải pháp

@tailrec 
def collectUnique(l: List[Object], s: Set[Property], u: List[Object]): List[Object] = l match { 
    case Nil => u.reverse 
    case (h :: t) => 
    if (s(h.property)) collectUnique(t, s, u) else collectUnique(t, s + h.prop, h :: u) 
} 

Answer 4

Tôi không biết phiên bản nào của Scala bạn đang sử dụng, nhưng chắc chắn có 2.8.2

list.distinct 

Chỉnh sửa (sửa chữa các phiếu xuống)

list.distinctBy 

Answer 5

Tôi tìm thấy cách để làm cho nó hoạt động với groupBy, với một trong bước termediary:

def distinctBy[T, P, From[X] <: TraversableLike[X, From[X]]](collection: From[T])(property: T => P): From[T] = { 
    val uniqueValues: Set[T] = collection.groupBy(property).map(_._2.head)(breakOut) 
    collection.filter(uniqueValues) 
} 

Sử dụng nó như thế này:

scala> distinctBy(List(redVolvo, bluePrius, redLeon))(_.color) 
res0: List[Car] = List(redVolvo, bluePrius) 

Tương tự như giải pháp đầu tiên IttayD, nhưng nó lọc bộ sưu tập ban đầu dựa trên các thiết lập của giá trị duy nhất. Nếu kỳ vọng của tôi là chính xác, điều này thực hiện ba lần duyệt qua: một cho groupBy, một cho map và một cho filter. Nó duy trì thứ tự của bộ sưu tập gốc, nhưng không nhất thiết phải lấy giá trị đầu tiên cho mỗi thuộc tính. Ví dụ: thay vào đó, nó có thể đã trả về List(bluePrius, redLeon).

Tất nhiên, giải pháp của IttayD vẫn nhanh hơn vì nó chỉ có một lần truyền tải.

Giải pháp của tôi cũng có bất lợi là, nếu bộ sưu tập có Car s thực sự giống nhau, cả hai sẽ nằm trong danh sách đầu ra. Điều này có thể được khắc phục bằng cách xóa filter và trả lại trực tiếp uniqueValues, với loại From[T]. Tuy nhiên, có vẻ như CanBuildFrom[Map[P, From[T]], T, From[T]] không tồn tại ... đề xuất được hoan nghênh!

Answer 6

Với giữ gìn trật tự:

def distinctBy[L, E](list: List[L])(f: L => E): List[L] = 
    list.foldLeft((Vector.empty[L], Set.empty[E])) { 
    case ((acc, set), item) => 
     val key = f(item) 
     if (set.contains(key)) (acc, set) 
     else (acc :+ item, set + key) 
    }._1.toList 

distinctBy(list)(_.property)