Xóa các mục thừa, cách scala

Question

Chỉnh sửa: Đã thêm thực tế, danh sách được sắp xếp và nhận ra 'trùng lặp' là gây hiểu nhầm, thay thế bằng 'dư thừa' trong tiêu đề.

Tôi có danh sách các mục nhập được sắp xếp cho biết giá trị sản xuất trong một khoảng thời gian nhất định. Các mục nhập chỉ ra cùng một giá trị chính xác vào một thời điểm sau sẽ không thêm thông tin nào và có thể bỏ đi một cách an toàn.

case class Entry(minute:Int, production:Double) 
val entries = List(Entry(0, 100.0), Entry(5, 100.0), Entry(10, 100.0), Entry(20, 120.0), Entry(30, 100.0), Entry(180, 0.0)) 

Thử nghiệm với các chức năng thu thập scala 2.8, cho đến nay tôi có thực hiện công tác này:

entries.foldRight(List[Entry]()) { 
    (entry, list) => list match { 
    case head :: tail if (entry.production == head.production) => entry :: tail 
    case head :: tail => entry :: list 
    case List() => entry :: List() 
    } 
} 
res0: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0)) 

Bất kỳ ý kiến? Tôi có bỏ lỡ một số phép thuật scala không?

Answer 1

Khi bạn so sánh các mục nhập liên tiếp trong danh sách, hãy bắt đầu bằng cách zip -nhập danh sách bằng đuôi của nó để có danh sách các cặp phần tử liên tiếp.

Dưới đây, tôi lấy mục nhập đầu tiên từ danh sách và sử dụng collect để đồng thời lọc ra các cặp nơi sản xuất không thay đổi và đối với các cặp còn lại, bản đồ e2. (collect là mới trong Scala 2.8, và trong một thời gian được gọi là partialMap)

scala> entries.head :: ((entries zip entries.tail).collect { 
      case (Entry(_, p1), e2@Entry(_, p2)) if p1 != p2 => e2 
     }) 
res13: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0)) 

CẬP NHẬT Để đơn giản, này giả định rằng mục không rỗng.

Answer 2

Thay vì tìm kiếm các mục trùng lặp cho mỗi mục, là O (n^2) hoặc nén, bộ nhớ là n^2, hãy sử dụng bản đồ [Double, Int]. Sau đó, chỉ cần thêm các mục có 'sản xuất' làm khóa và 'phút' làm giá trị. Bản đồ sẽ đảm bảo các giá trị duy nhất cho 'sản xuất'. Bạn có thể tải bản đồ một cách tự nhiên ở nơi khác trong mã của bạn, nhưng ngay cả khi bạn phải bắt đầu với danh sách như trên, tải bản đồ là tuyến tính trên danh sách và chỉ O (n log (n)) trên bản đồ.

Bản đồ sẽ thay thế khi bạn thêm "mymap + = production -> minute" để giữ giá trị đầu tiên, đảo ngược danh sách trước khi bạn chèn hoặc sử dụng bảo vệ 'contains (key)'. Các kiểm tra sẽ là O (log (n)) vì vậy thuật toán tổng thể sẽ là O (n log (n)).

BTW, bạn có thể sử dụng bản đồ [Double, Entry] để ánh xạ từ giá trị sản xuất trực tiếp đến cấu trúc Entry của bạn. Sau đó, bạn có thể dễ dàng có được một danh sách, nếu cần thiết, bằng cách kéo các giá trị của bản đồ trực tiếp từ bản đồ và sắp xếp trên một trong hai phần tử của Entry (nếu cần).

Answer 3

Có phương pháp zipped mới với Tuple2 hiệu quả hơn (và lazier) hơn zip trên danh sách cho một số thao tác. Bạn có thể thử này trên điểm chuẩn của bạn - Tôi không biết nếu nó thực sự nhanh hơn, nhưng chắc chắn nó thể được (và nó chắc chắn rất nhiều ngắn hơn):

entries.take(1) ::: 
(entries,entries.drop(1)).zipped.filter(_.production != _.production)._2 

Thay vì nén danh sách cặp tất cả thông qua, nó tạo ra một cái nhìn của danh sách, nơi các mảnh có thể được thao tác với nhau, và sau đó trả về các danh sách thao tác. Lưu ý việc sử dụng lấy và thả để xử lý trường hợp trống.

Nó không siêu hiệu quả vì nó xây dựng hai danh sách khi bạn thực sự chỉ cần một danh sách, nhưng nó là một lớp giải pháp chưa xuất hiện.