TreeSet của Scala so với TreeSet của Java - cuộc thăm dò ý kiến?

Question

Nếu tôi muốn xóa mục nhập cao nhất trong thời gian log(n) trong Java TreeSet, tôi sử dụng treeSet.pollFirst() - điểm tương đương với lớp học mutable.TreeSet của Scala là gì?

Dù sao, những gì tôi thực sự muốn là cấu trúc dữ liệu xếp hàng ưu tiên giống như heap cho phép tôi removeMax, add và updatePriority trong thời gian logarit. Tôi nhìn vào thư viện bộ sưu tập Scala và tôi bối rối - trong khi mutable.PriorityQueue cho phép tôi deque (tức là removeMax) trong thời gian logarit - nó không cung cấp cách nào để cập nhật ưu tiên trong thời gian đăng nhập (tôi sẽ phải quét và xóa mục một cách dễ dàng và thêm lại thời gian tuyến tính). Tương tự, mutable.TreeSet sẽ cho phép tôi cập nhật ưu tiên trong thời gian logarit (bằng cách xóa và thêm lại), nhưng nó không có hoạt động removeMax (tức là pollFirst). Tôi nên sử dụng bộ sưu tập nào? Vui lòng không giới thiệu tôi với các phụ thuộc bên ngoài.

Answer 1

Bạn có thể sử dụng các phương pháp head và last trong immutable.TreeSet, là O(log n). Các phương pháp tương tự tồn tại trong mutable.TreeSet, nhưng không được ghi đè để cung cấp hiệu quả tốt hơn và thời gian khấu hao (trong Scala 2.10). Phương thức head sẽ là logarit, nhưng có thể khởi tạo một trình lặp khi thực hiện điều đó. Phương pháp last sẽ thực sự đi qua nó, có độ phức tạp tuyến tính. Tin tốt là bạn có thể kiểm soát những gì nhỏ nhất hoặc lớn nhất với một tùy chỉnh Ordering - và dễ dàng có được nó từ một hiện tại Ordering bằng cách gọi Ordering.reverse.

Nếu bạn cần xóa phần tử đó, chỉ cần sử dụng -=. Bạn có thể tạo lớp giá trị tiềm ẩn của riêng bạn để con heo con trở lại phương thức pollFirst trên bộ cây.

implicit class MyExtensions[T](ts: mutable.TreeSet[T]) extends AnyVal { 
    def pollFirst(): T = { 
    val elem = ts.head 
    ts -= elem 
    elem 
    } 
} 

Answer 2

Không phải là câu trả lời, chỉ là một gợi ý :) hãy nhớ rằng bạn có thể truy cập thư viện Java từ scala (tốt, nếu bạn biên dịch để JVM :) vì vậy nếu TreeSet Java làm việc cho bạn, sử dụng nó :)

Bạn cũng có thể làm rõ các yêu cầu của mình; những gì sẽ là các tham số cho phương thức updatePriority của bạn? có ưu tiên nào bạn đang cố cập nhật?