20/09/2018, 15:33

Giới thiệu Set Class trong Ruby

Set class cũng giống như Array nó có thể chứa những items, tuy nhiên chúng có một số đặc tính đặc biệt chính là tất cả các items lưu trữ trong Set là duy nhất. VÌ vậy trong bài này sẽ giới thiệu cho các bạn sơ qua về Set: Sử dụng Set như thế nào và khi nào thì sử dụng chúng? Sự khác nhau ...

Set class cũng giống như Array nó có thể chứa những items, tuy nhiên chúng có một số đặc tính đặc biệt chính là tất cả các items lưu trữ trong Set là duy nhất.

VÌ vậy trong bài này sẽ giới thiệu cho các bạn sơ qua về Set:

  • Sử dụng Set như thế nào và khi nào thì sử dụng chúng?
  • Sự khác nhau giữa Set và Array
  • Những methods hay dùng với Set

Ví dụ về Set

Set class giúp bạn có thể tạo ra một danh sánh uniq các items. Và dưới đây là ví dụ sao chúng lại hữu ích đến vậy. Ví dụ bạn có nhiều categories, mỗi categories sẽ chứa nhiều sản phẩm khác nhau, một sản phẩm cũng có thể thuộc nhiều category và bạn chỉ muốn lấy ra một danh sách các sản phẩm uniq => Thì bạn có thể đặt tất cả sản phẩm đó trong một Set, nó sẽ đảm bảo cho bạn rằng danh sách sản phẩm đó sẽ luôn uniq mà không cần bất cứ hành động nào khác.

2.5.1 :001 > require 'set'
 => true 
2.5.1 :002 > products = Set.new
 => #<Set: {}> 
2.5.1 :003 > products << 1
 => #<Set: {1}> 
2.5.1 :004 > products << 2
 => #<Set: {1, 2}> 
2.5.1 :005 > products << 1
 => #<Set: {1, 2}> 
2.5.1 :006 > products << 2
 => #<Set: {1, 2}> 
2.5.1 :007 > products << 4
 => #<Set: {1, 2, 4}> 
2.5.1 :009 > products
 => #<Set: {1, 2, 4}> 

Và một điều đặc biệt nữa là việc tra cứu trong một Set sẽ rất nhanh

2.5.1 :011 > products.include?(2)
=> true 
2.5.1 :012 > products.include?(3)
=> false 

Là bởi vì nó là sự kết hợp giữa Array và fast lookup của Hash với độ phức tạp của thuật toán là O(1)(constant time). Và bên dưới chúng ta sẽ so sánh mức độ nhanh, chậm của Set với Array

Sự khác biệt giữa Set và Array

Sự khác biệt chính giữa Set và Array chính là Set không có quyền truy cập trực tiếp vào các elements, ví dụ với 1 array ta có thể gọi trực tiếp products[0]nhưng đói với Set thì không thể

2.5.1 :015 > products
 => #<Set: {1, 2, 4}> 
2.5.1 :016 > products[0]
Traceback (most recent call last):
        2: from /home/framgia/.rvm/rubies/ruby-2.5.1/bin/irb:11:in `<main>'
        1: from (irb):16
NoMethodError (undefined method `[]' for #<Set: {1, 2, 4}>)

Bạn cũng có thể chuyển đổi từ 1 Set sang Arrayhoặc ngược lại từ Array qua Set bất cứ khi nào bạn muốn.

# Array -> Set
2.5.1 :018 > arr_products = [1,2,3]
3.2.5.1 :018 > arr_products.to_set
 => #<Set: {1, 2, 3}> 
# Set -> Array
2.5.1 :020 > products.to_a
 => [1, 2, 4] 

Hầu hết mục đích khi bạn sử dụng Set chính là để sử dụng 2 tính năng đặc biệt của nó:

  • Thời gian tra cứu nhanh (với method include?)
  • Các giá trị trong Set luôn luôn uniq

Nếu bạn cần những điều này thì sử dụng Set sẽ cho bạn một performance tốt mà không cần phải call .uniq như khi bạn sử dụng 1 Array Như trên kia cũng đã đề cập đến việc thời gian tra cứu nhanh, giờ chúng ta sẽ so sánh Benchmark giữa chúng để thấy được nó nhanh như thế nào.

Benchmark giữa Set và Array

Dưới đây chúng ta sẽ so sánh benchmark của method include? giữa Array và Set. Ta sẽ lấy size của array và set là như nhau với 10K elements

2.5.1 :030 > arr_products = (1..10000).to_a
2.5.1 :032 > products = arr_products.to_set
2.5.1 :033 > Benchmark.ips do |x|
2.5.1 :034 >       x.report("Set include: ")   { products.include?(9999) }
2.5.1 :035?>     x.report("Array include: ") { arr_products.include?(9999) }
2.5.1 :036?>     x.compare!
2.5.1 :037?>   end
Warming up --------------------------------------
       Set include:    232.522k i/100ms
     Array include:      1.366k i/100ms
Calculating -------------------------------------
       Set include:       6.149M (± 3.8%) i/s -     30.693M in   5.000194s
     Array include:      13.832k (± 2.5%) i/s -     69.666k in   5.040002s

Comparison:
       Set include: :  6148643.9 i/s
     Array include: :    13832.0 i/s - 444.52x  slower

Dựa vào kết quả có thể thấy nó chậm hơn rất nhiều. Và mức độ chậm này còn phục thuộc vào phần tử mình tìm kiếm, vị trí nó ở đâu và size của array như thế nào. Array càng lớn, vị trí càng xa thì mực độ chậm nó sẽ càng tăng, bởi vì Array nó check từng element một, nếu gặp phải mới dừng lại => nếu bạn có 10K phần tử tìm phần tử thứ 9999 => duyệt qua ít nhất 9999 phần tử để tìm thấy nó. (đối với array shorted).

Một vài methods của Set

Hầu hết các methods của Set khá giống với array, bạn có thể tham khảo chúng ở đây. Một số methods hữu ích như là: union(|), difference(-), intersection(&)

2.5.1 :046 > set1 = Set.new(1..5)
 => #<Set: {1, 2, 3, 4, 5}> 
2.5.1 :048 > set1 | (4..7)
 => #<Set: {1, 2, 3, 4, 5, 6, 7}> 
2.5.1 :049 > set2 = Set.new 4..6
 => #<Set: {4, 5, 6}> 
2.5.1 :050 > set1 & set2
 => #<Set: {4, 5}> 
2.5.1 :051 > set1 - set2
 => #<Set: {1, 2, 3}> 

Ngoài ra nó còn có 2 methods là Superset & Subset. Superset là một set chứa những set khác, subset là một phần của một set nào đó.

2.5.1 :055 > set1 >= set2
 => true 
2.5.1 :056 > set2 <= set2
 => true 
2.5.1 :057 > set2 <= set1
 => true 
2.5.1 :058 > set3 = Set.new (4..6)
 => #<Set: {4, 5, 6}> 
2.5.1 :059 > set1 >= set3
 => false 
2.5.1 :060 > set3 <= set1
 => false 

Ngoài ra nếu bạn muốn có 1 Set mà các phần tử luôn luôn trong trạng thái được sắp xếp, bạn có thể dùng SortedSet. Tất cả các element được add trong SortedSet thì đều thực thi method <=> để compare giữa các phần tử còn lại, và tất cả các phần tử phải được so sánh với nhau el1 <=> el2, kết của của việc so sánh không được phép trả về nil, nếu không thì một ArgumentError sẽ được trả về => nếu bạn tạo SortedSet gồm string + integer sẽ gây ra lỗi.

2.5.1 :062 > set = SortedSet.new([2, 1, 5, 6, 4, 5, 3, 3, 3])
 => #<SortedSet: {1, 2, 3, 4, 5, 6}> 
2.5.1 :063 > ary = []
 => [] 
2.5.1 :065 > set.each {|obj| ary << obj}
2.5.1 :069 > p ary
[1, 2, 3, 4, 5, 6]
2.5.1 :071 > set2 = SortedSet.new([1, 2, "3"])
Traceback (most recent call last):
        4: from /home/framgia/.rvm/rubies/ruby-2.5.1/bin/irb:11:in `<main>'
        3: from /home/framgia/.rvm/rubies/ruby-2.5.1/lib/ruby/2.5.0/set.rb:638:in `inspect'
        2: from /home/framgia/.rvm/rubies/ruby-2.5.1/lib/ruby/2.5.0/set.rb:779:in `to_a'
        1: from /home/framgia/.rvm/rubies/ruby-2.5.1/lib/ruby/2.5.0/set.rb:779:in `sort!'
ArgumentError (comparison of Integer with String failed)

Trên đây bạn đã biết thêm được cách dùng Set để có được performance tốt hơn giúp bạn cân nhắc khi nào thì nên sử dụng Set, ngoài ra cũng thấy được sự khác biệt giữa Set và Array. Tùy thuộc vào tình hình thực tế mà bạn có thể tìm được phương pháp tốt nhất cho mình.

Reference

https://ruby-doc.org/stdlib-2.5.1/libdoc/set/rdoc/Set.html

https://www.rubyguides.com/2018/08/ruby-set-class

0