Scala: nhanh nhất `xóa (i: Int)` trong chuỗi có thể thay đổi

Question

Việc triển khai nào từ gói scala.collection.mutable tôi nên thực hiện nếu tôi định xóa nhiều chỉ mục, như remove(i: Int), trong môi trường một luồng? Sự lựa chọn rõ ràng nhất, ListBuffer, nói rằng nó có thể mất thời gian tuyến tính tùy thuộc vào kích thước bộ đệm. Có một số bộ sưu tập với log(n) hoặc thậm chí không đổi thời gian cho hoạt động này không?

Answer 1

Toán tử xóa, bao gồm buf remove i, không phải là một phần của Seq, nhưng nó thực sự là một phần của đặc điểm Buffer dưới scala.mutable. (Xem Buffers)

Xem bảng đầu tiên trên Performance Characteristics. Tôi đoán buf remove i có cùng đặc điểm như chèn, là tuyến tính cho cả hai ArrayBuffer và ListBuffer. Theo tài liệu trong Array Buffers, họ sử dụng mảng nội bộ và Link Buffers sử dụng danh sách được liên kết (đó vẫn là O (n) để xóa).

Thay thế, bất biến Vector có thể cung cấp cho bạn thời gian không đổi hiệu quả.

Vectơ được thể hiện dưới dạng cây có hệ số phân nhánh cao. Mỗi nút cây chứa tối đa 32 phần tử của vectơ hoặc chứa tối đa 32 nút cây khác. [...] Vì vậy, đối với tất cả các vectơ có kích thước hợp lý, lựa chọn phần tử bao gồm tối đa 5 lựa chọn mảng nguyên thủy. Đây là những gì chúng tôi có nghĩa là khi chúng tôi viết rằng truy cập phần tử là "thời gian liên tục hiệu quả".

scala> import scala.collection.immutable._ 
import scala.collection.immutable._ 

scala> def remove[A](xs: Vector[A], i: Int) = (xs take i) ++ (xs drop (i + 1)) 
remove: [A](xs: scala.collection.immutable.Vector[A],i: Int)scala.collection.immutable.Vector[A] 

scala> val foo = Vector(1, 2, 3, 4, 5) 
foo: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5) 

scala> remove(foo, 2) 
res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4, 5) 

Lưu ý, tuy nhiên, một thời gian liên tục cao với rất nhiều chi phí có thể không giành được một truy cập nhanh chóng tuyến tính cho đến khi kích thước dữ liệu là lớn đáng kể.

Answer 2

Tùy thuộc vào trường hợp sử dụng chính xác của bạn, bạn có thể sử dụng LinkedHashMap từ scala.collection.mutable.

Mặc dù bạn không thể xóa theo chỉ mục, bạn có thể xóa bằng khóa duy nhất trong thời gian không đổi và duy trì thứ tự xác định khi bạn lặp lại.

scala> val foo = new scala.collection.mutable.LinkedHashMap[String,String] 
foo: scala.collection.mutable.LinkedHashMap[String,String] = Map() 

scala> foo += "A" -> "A" 
res0: foo.type = Map((A,A)) 

scala> foo += "B" -> "B" 
res1: foo.type = Map((A,A), (B,B)) 

scala> foo += "C" -> "C" 
res2: foo.type = Map((A,A), (B,B), (C,C)) 

scala> foo -= "B" 
res3: foo.type = Map((A,A), (C,C))