Cài đặt mặc định Scala Cài đặt thực hiện

Question

Tôi có thể thấy rằng từ tài liệu Scala.collection.immutable.Set chỉ là một đặc điểm. Cài đặt nào được thực hiện theo mặc định? HashSet hoặc TreeSet (hoặc cái gì khác)?

Tôi muốn biết/lập kế hoạch thời gian chạy của một số chức năng nhất định.

Ví dụ:

scala> val s = Set(1,3,6,2,7,1) 
res0: scala.collection.immutable.Set[Int] = Set(1, 6, 2, 7, 3) 

• Điều gì sẽ là thời gian chạy của s.find (5), O (1) hoặc O (log (n))?

• Vì cùng áp dụng cho Bản đồ, cách tốt nhất để tìm hiểu điều này là gì?

Answer 1

Bằng cách nhìn vào mã nguồn, bạn có thể thấy rằng thiết lập từ bốn yếu tố đã một thực hiện tối ưu hóa được cung cấp bởi EmptySet, Set1, Set2, Set3 và Set4, mà chỉ cần giữ các giá trị duy nhất.

Ví dụ đây là Set2 khai (như của scala 2.11.4):

class Set2[A] private[collection] (elem1: A, elem2: A) extends AbstractSet[A] with Set[A] with Serializable 

Và đây là việc thực hiện contains:

def contains(elem: A): Boolean = 
    elem == elem1 || elem == elem2 

hoặc find thực hiện

override def find(f: A => Boolean): Option[A] = { 
    if (f(elem1)) Some(elem1) 
    else if (f(elem2)) Some(elem2) 
    else None 
} 

Rất đơn giản.

Đối với các bộ có nhiều hơn 4 phần tử, triển khai cơ bản là HashSet. Chúng ta có thể dễ dàng xác minh này trong REPL:

scala> Set(1, 2, 3, 4).getClass 
res1: Class[_ <: scala.collection.immutable.Set[Int]] = class scala.collection.immutable.Set$Set4 

scala> Set(1, 2, 3, 4, 5, 6).getClass 
res0: Class[_ <: scala.collection.immutable.Set[Int]] = class scala.collection.immutable.HashSet$HashTrieSet 

Điều đó đang được nói, find phải luôn lặp trên toàn bộ HashSet, vì nó không được phân loại, vì vậy nó sẽ O(n). Ngược lại, hoạt động tra cứu như contains sẽ là O(1) thay thế.

Here's a more in-depth reference về hiệu suất của bộ sưu tập scala nói chung.

Phát biểu của Map, khá nhiều khái niệm tương tự được áp dụng. Có tối ưu hóa việc triển khai Map tối đa 4 thành phần và sau đó là HashMap.