The power of sets in Swift

Mặc dù Set là một trong core data structure của hầu hết các ngôn ngữ lập trình. Nhưng đôi khi chúng ta rất hay bỏ qua không lựa chọn nó để lưu trữ collections mà chỉ toàn sử dụng Array (non-keyed objects) hay Dictionary (keyed objects).

Hôm nay mình sẽ giới thiệu các lợi ích mà Set mang lại để mọi người có thể dùng nó hiệu quả hơn trong những tình huống thích hợp chứ không phải mặc định lúc nào cũng dùng Array.

Constant time

Một trong những đặc điểm chính của Set là nó lưu trữ members dựa trên hash value thay vì dựa trên index giống Array. Tức là, Set hy sinh việc đảm bảo thứ tự sắp xếp của members để đảm bảo thời gian tra cứu không đổi (O(1)).

Ví dụ: Khi bạn lưu một mảng lớn các giá trị không cần sắp xếp, giống như theo dõi tất cả IDs của bạn bè chẳng hạn.

struct User {
    var friendIDs = Set<UUID>()
}

Bằng cách sử dụng Set thay vì dùng Array chúng ta có thể tránh bất kỳ tắc nghẽn nào về hiệu suất khi số lượng friends lớn.

Để kiểm tra user là friend của một user khác không chúng ta có thể sử dụng contains API

• Đối với Array thì bắt buộc phải kiểm tra từng phần tử dẫn đến khi kích thước collections tăng thì sẽ ảnh hưởng đến tốc độ tra cứu.
• Trong khi tra cứu theo hash value đối với Set thì luôn nhanh và time tra cứu không đổi bất kể kích thước của collections.

Indexing

Set rất tuyệt khi bạn không quan tâm thứ tự của collections. Tuy nhiên, khi có một collection đã được sắp xếp nó cũng rất hữu ích, nếu chúng ta có thể tối ưu hoá code để thể tận dụng được.

Ví dụ: Xây dựng một app cho phép user xếp hạng cho movie. Yêu cầu: List ra toàn bộ movie đã được xếp hạng theo thứ tự.

1. Lưu trữ ratings theo cách giữ nguyên thứ tự.

   class RatingsManager {
       private typealias Rating = (score: Int, movieID: UUID)
   
       private var ratings = [Rating]()
   }
   

2. Kiểm tra movie đã được đánh rate hay chưa.

   extension RatingsManager {
       func containsRating(for movie: Movie) -> Bool {
           for rating in ratings {
               if rating.movieID == movie.id {
                   return true
               }
           }
   
           return false
       }
   }
   

==> Not good. Vì phải duyệt từng phần tử của mảng nếu mảng có size lớn thì phiền phức.