Array or Set?

Mình học và sử dụng Ruby khoảng 1 năm rồi, nhưng chỉ gần đây (vài ngày trước, khi lang thang trên mạng tìm chủ đề cho Study Report tháng này, mình vô tình nhìn thấy ở chỗ nào đó mà tác giả sử dụng class Set). Thú thật khi lập trình, mỗi khi cần store 1 list các đối tượng, 99/100 lần mình nghĩ đến Array, 1 lần còn lại mình nghĩ đến Hash. Ở bài viết này mình chỉ muốn cùng các bạn ôn lại 1 chút kiến thức về kiểu dữ liệu (môn cấu trúc dữ liệu và giải thuật thì LTV nào cũng phải học rồi) cụ thể là kiểu Set. À thêm nữa mình cũng đảm bảo là không có trường hợp nào mà bạn bắt buộc phải dùng Set thay vì Array hay Hash đâu nhé. Đọc for fun thôi. Okay?

Nếu bạn còn nhớ về 1 kiểu dữ liệu mà: Không quan tâm đến trật tự sắp xếp của phần tử bên trong Không cho phép 2 phần từ giống nhau Thì đấy là mô tả ngắn gọn nhất về kiểu Set đấy. Cùng nhìn xem những method cơ bản nhất của class Set trong Ruby nào.

require 'set' #khi nào muốn dùng Set thì bắt buộc phải require nhé

# Union. Vì set không cho phép duplicated values nên phép union sẽ cho kết quả như sau
Set[1,2,3] | Set[3,4,5]
#=> #{1,2,3,4,5}

# Intersection. Tìm tập con chung của 2 tập hợp.
Set[1,2,3] & Set[2,3,4,5]
#=> #{2,3}

# Subtraction. 
Set[1,2,3,4] - Set[3,4,5]
#=> #{1,2}

# Kiểm tra 2 set có giống nhau hay không, chỉ quan tâm values chứ ko phải là values + orders như Array
Set[1,2,3] == Set[3,1,2]
#=> true

# Set class cũng cho phép kiểm tra một Set khác có phải là subset hay superset ban đầu hay không.
# Subsets and Supersets
Set[1,2,3].subset?(Set[1,2,3,4])
#=> true

Set[1,2,3].superset(Set[3,6,9])
#=> false

Set[1,2,3].proper_subset?(Set[1,2,3])
#=> false

# Set class cho phép partitioning 1 set thành nhiều set nhỏ hơn bằng cách sử dụng block trong #divide
# Partitioning using divide
Set[1,2,3,4,5,6,7,8,9].divide {|el| el%3 }
#=> #{ #{1,4,7},
#      #{2,5,8},
#      #{3,6,9}
#      }

z = Set["alpha", "bravo", "charlie", "delta", "echo", "apple", "code"]

z.divide {|str| str[0]}
#=>  { {"alpha", "apple"},
#      {"bravo"},
#      {"charlie", "code"},
#      {"delta"},
#      {"echo"}
#     }

Rồi, và Set class cũng implement module Enumerable nữa. Có nghĩa là #each được, tức là bất cứ khi nào Set cũng có thể thành Array được. Ví dụ như method #sort chẳng hạn, nó chẳng có ý nghĩa gì với Set (unordered list cơ mà) sẽ trả lại một Array. Tiện quá!

Mình chắc chắn là đã rất nhiều lần bạn gặp phải những trường hợp như một trong hai case dưới đây rồi:

1. Khi muốn tạo 1 array mà không cho phép giá trị trùng nhau thì dùng cách nào là tốt nhất? Giơ tay nếu bạn đã từng viết thế này nhé =)).

array_of_things << thing unless array_of_things.includes?(thing)
# Tin hay không tùy bạn nhưng code này smells vãi =)) 

1. Làm cách nào hay nhất để so sánh 2 arrays có giống nhau về giá trị phần tử bên trong hay không, thứ tự không quan trọng (nếu để ý thì trường hợp này cũng hay gặp lắm nhé). Mình không rõ lắm nhưng mình đoán Ruby nó #uniq xong nó #sort xong nó #each rồi nó #==. Cũng khá vất vả nhỉ.

Ruby support cho mình đến tận răng rồi thì không nói làm gì, chỉ một dòng là giải quyết được vấn đề thôi. Nhưng thử tưởng tượng bạn đang code bằng một ngôn ngữ khác chẳng hạn, hoặc là thử nghĩ đến under the hood Ruby xử lý vất vả thế nào nếu array có số lượng phần tử từ 6 con số trở lên (à cái này thì lại ít gặp =)) )

Khó tin nhưng đúng thế, không tin thì soi source code mà xem. Mình xem rồi nhưng không bookmark lại địa chỉ nên bạn nào muốn điều tra lại thì tự tìm nhé =)) ở #initialize ý. Lại một điểm cộng nữa ngoài 2 cái ở trên dành cho Set vì nó search rất là nhanh luôn (Hash mà). Để mình làm rõ ý vừa nói nhé, đề bài là tìm vị trí của phần tử có giá trị X trong tập hợp

1. Search trong tập hợp là Array. Best case: O(n), worst case cũng O(n). Haiz 1 điểm về chỗ. .
2. Search trong Set/Hash, Best case là O(1). Khá hơn rồi, nhưng tại sao nhỉ. Vì Hash là key-value mà, mà bản chất khi đi tìm X hash nó đã chỉ cho bạn biết phải tìm ở vị trí nào rồi, vào đấy tìm, có hay không có cũng kết thúc tìm kiếm luôn, vì không giống Array cho phép các giá trị duplicates.

Ờ, nhưng mà tại sao Hash lại chỉ cho ta biết vị trí để đi tìm X. Nếu muồn biết thì đọc tiếp nhé.

Cần biết Hash trong Ruby được xây dựng dư lào đã. Thế thì hãy tưởng tượng 1 ngày mà chưa có Hash class và ta phải đi xây dựng một kiểu mảng chứa dữ liệu dạng key-value. Ta sẽ bắt đầu như thế nào. Đầu tiên ta phải có một đối tượng kiểu key-value cái đã.

HashEntry = Struct.new(:key, :value)

Ồ kê. Giờ cần một class để chứa nhưng cái entry kia.

class HashTable
  attr_accessor :bins

  def initialize
    self.bins = []
  end
end

Giả dụ bins ở mức độ sơ khai nhất là 1 array, nó sẽ chứa các entry kể trên (chưa có kì diệu xảy ra đâu). Tiếp theo một method để đưa element vào bins:

class HashTable
  attr_accessor :bins

  def initialize
    self.bins = []
  end

  def <<(entry)
    self.bins << entry
  end
end

Giờ ta có thể đưa element vào HashTable được rồi:

entry = HashEntry.new :foo, :bar
table = HashTable.new
table << entry
Yêu cầu đặt ra là phải tìm được element theo key. Ta sẽ implement như thế nào?
def [](key)
  self.bins.detect { |entry| entry.key == key }
end

Điều mà ta đang làm nó có khác gì tìm kiếm trong Array không: duyệt từng phần tử một và so sánh :key. Benmark cái để xem thuật toán này nó tệ đến mức độ nào

require 'benchmark'

#
# HashTable instance
#
table = HashTable.new

#
# Tạo 1,000,000 entries và đưa nó vào HashTable
#

(1..1000000).each do |i|
  entry = HashEntry.new i.to_s, "bar#{i}"

  table << entry
end

#
# Tìm kiếm phần tử ở đầu, giữa và cuối của một HashTable.
# Đo kết quả
#
%w(100000 500000 900000).each do |key|
  time = Benchmark.realtime do
    table[key]
  end

  puts "Finding #{key} took #{time * 1000} ms"
end

Và đây là kết quả

Finding 100000 took 33.641 ms
Finding 500000 took 192.678 ms
Finding 900000 took 345.329 ms

Dễ nhận ra là thời gian để tìm kiếm tăng theo số lượng phần tử và index càng về cuối thì càng lâu. Giờ xem Hash xử lý cái này như thé nào nhé. Thay vì dùng mảng 1 chiều, bins sẽ là mảng 2 chiều (mảng của mảng)

Thuật toán như thế này, mình xin quote lại thôi

First, it calculates a unique integer value for each entry. For this example we will use Object#hash. Then, Ruby divides this hash integer by the total number of bins and obtains the remainder or modulus. This modulus will be used as the bin index for that specific entry. When you lookup for a key, you calculate its bin index again using the same algorithm and you look for the corresponding object directly on that bin.

Giờ class HashTable sẽ có thêm một attributes là bin_count, ban đầu cứ để một giá trị be bé đã xem như thế nào

class HashTable
  # ...

  attr_accessor :bin_count

  def initialize
    self.bin_count = 500
    self.bins = []
  end

  # ...
end

Giờ viết hàm #bin_for để tính xem cái bin nào chứa cái element với value đã cho.

class HashTable
  # ...

  def bin_for(key)
    key.hash % self.bin_count
  end

  # ...
end

Khi đưa element vào Table, thay vì như lúc trước, ta lưu nó vào array tương ứng với bin index với index là kết quả của #bin_for

class HashTable
  # ...

  def <<(entry)
    index = bin_for(entry.key)
    self.bins[index] ||= []
    self.bins[index] << entry
  end

  # ...
end

Cuối cùng, khi tìm element, ta trước hết tính lại index của nó theo #bin_for, với index ta đã biết chính xác nơi ta muốn tìm element rồi.

def [](key)
  index = bin_for(key)
  self.bins[index].detect do |entry|
    entry.key == key
  end
end.

Khi chạy lại benmark, ta có kết quả tốt hơn rõ rệt luôn

Finding 100000 took 0.025 ms
Finding 500000 took 0.094 ms
Finding 900000 took 0.112 ms

Vẫn còn có thể improve được, nếu ta set bin_count lớn hơn như là 300000 chẳng hạn

class HashTable
  # ...

  def initialize
    self.bin_count = 300000
    self.bins = []
  end

  # ...
end

Kết quả sẽ như thế nào nhỉ

Finding 100000 took 0.014 ms
Finding 500000 took 0.016 ms
Finding 900000 took 0.005 ms

Nghĩa là càng nhiều bin thì tìm kiếm càng nhanh hơn. Để cân bằng giữa performance và bộ nhớ. Hash của Ruby còn có một cơ chế thông minh là set cái bin_count dynamically luôn cơ. Ý tức là tùy theo số lượng của element, element tăng lên thì bin_count tăng theo chứ không phải một con số fixed ban đầu nữa.