SCALA: Cấu trúc dữ liệu nào tối ưu trong đó siutations khi sử dụng ".contains()" hoặc ".exists()"?

Question

Tôi muốn biết trong trường hợp nào các cấu trúc dữ liệu là tối ưu để sử dụng kiểm tra "chứa" hoặc "tồn tại".

Tôi hỏi vì tôi đến từ một nền Python và sáng sử dụng để sử dụng các biểu thức if x in something: cho mọi thứ. Ví dụ, trong đó biểu thức được đánh giá là nhanh nhất:

val m = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4) 
              //> m : scala.collection.immutable.Map[Int,Int] = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 
              //| -> 4) 
val l = List(1,2,3,4)      //> l : List[Int] = List(1, 2, 3, 4) 
val v = Vector(1,2,3,4)     //> v : scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4) 

m.exists(_._1 == 3)      //> res0: Boolean = true 
m.contains(3)        //> res1: Boolean = true 
l.exists(_ == 3)       //> res2: Boolean = true 
l.contains(3)        //> res3: Boolean = true 
v.exists(_ == 3)       //> res4: Boolean = true 
v.contains(3)        //> res5: Boolean = true 

trực giác, tôi sẽ giả định rằng vectơ nên là nhanh nhất để kiểm tra ngẫu nhiên, và danh sách sẽ là nhanh nhất nếu ai biết rằng giá trị kiểm tra là vào đầu những và có rất nhiều dữ liệu. Tuy nhiên, một xác nhận hoặc sửa chữa sẽ được chào đón nhiều nhất. Ngoài ra, vui lòng mở rộng sang các cấu trúc dữ liệu khác.

Lưu ý: Vui lòng cho tôi biết nếu bạn cảm thấy câu hỏi này quá mơ hồ vì tôi không chắc tôi đang nói đúng cách.

Answer 1

Set và Map (với triển khai bảng băm mặc định) là nhanh nhất tại contains vì chúng tính toán giá trị băm và chuyển đến đúng vị trí ngay lập tức. Ví dụ: nếu bạn muốn tìm một chuỗi tùy ý trong danh sách một nghìn, contains trên tập hợp nhanh hơn 100x contains trên List hoặc Vector hoặc Array.

Với exists, bạn thực sự chỉ quan tâm đến bộ sưu tập nhanh như thế nào để đi ngang - bạn phải duyệt mọi thứ. Ở đó, List thường là nhà vô địch (trừ khi bạn muốn đi qua một mảng bằng tay), nhưng chỉ Set và thường đặc biệt xấu (ví dụ: exists trên List là ~ 8x nhanh hơn trên Set khi mỗi có 1000 phần tử). Những người khác nằm trong khoảng 2.5x của List (thường là 1.5x, nhưng Vector có cấu trúc cây bên dưới không phải là tất cả nhanh để lướt qua).

Answer 2

Nếu bạn muốn sử dụng rộng rãi contains, bạn nên sử dụng Set (hoặc Map).

AFAIK không có cơ sở hạ tầng thực hiện hiệu quả (tức là nhanh hơn O (n)) exists kể từ khi đóng cửa bạn chuyển vào có thể thậm chí không liên quan đến các yếu tố bên trong.