Ruby中Set的优势

Question

Set的主要优势似乎在于维护唯一元素。但是，在Array中可以轻松实现这一点，方法如下：

array = [2,3,4]
array | [2,5,6] # => [2,3,4,5,6]

我遇到的唯一显著特征（可能适用于少数用例）是，

set1 = [1,2,3].to_set
set2 = [2,1,3].to_set
set1 == set2 # => true
[1,2,3] == [2,1,3] # => false

由于 Array 具有多种与其相关的功能和操作，那么何时以及为什么我应该使用 Set？

有很多链接比较了 Array 和 Set，但我没有看到过 Set 的重要应用。

- Prashanth

---

这是一个很宽泛的问题，很大程度上取决于个人观点。正如你所说，一切都取决于使用情况。你发现集合的用例很少，并不意味着所有情况都是如此。 - Ed de Almeida

我是编程和Ruby的新手。当我提到“少数用例”时，我只是指我的经验不足。我希望通过观察他人如何实现（应用）集合来更好地理解集合及其应用。谢谢。 - Prashanth

我理解，Prashanth。请不要把它当成个人攻击。我的意思是这是非常私人的事情，很难一概而论。 - Ed de Almeida

Answer 1

当然，你可以用 Array 来完成 Set 可以做的任何事情。使用 Set 的优势在于，由于它是基于 Hash 实现的，对它进行大多数操作的时间复杂度都是 O(1)，而使用 Array 可能会是 O(n)。

例如：

Set.new([1, 2, 3]).include?(2) # O(1) complexity
[1, 2, 3].include?(2) # O(n) complexity

- sawa

---

能够提供 a) 一个证明链接 和 b) 更具体的“大多数”操作列表将会非常棒。 - Aleksei Matiushkin

由于动态调整大小，应该是摊销O(1)复杂度。 - David Bodow

Answer 2

这两个类定义了不同的数据结构：

数组

• 可以有重复元素
• 保持顺序
• 可以按顺序迭代
• 查找元素很慢，附加元素和从位置获取元素很快
• 维护元素的唯一性很慢

集合

• 不能有重复元素
• 没有排序（理论背景：https://en.wikipedia.org/wiki/Partially_ordered_set）
• 查找元素是否存在很快，添加元素很快
• 唯一性由设计确定

集合实际上来自于数学概念：https://en.wikipedia.org/wiki/Set_(mathematics)

在 Ruby 中，Set 内部使用哈希表进行存储，如文档所述：

Set 使用哈希表作为存储，因此您必须注意以下几点：

元素的相等性是根据 Object#eql? 和 Object#hash 来确定的。Set 假定每个元素的标识在存储时不会发生变化。修改集合中的元素将使集合处于不可靠状态。当要存储字符串时，除非原始字符串已经被冻结，否则会存储字符串的冻结副本。

当您查看代码时，它内部以用户提供的对象作为键，并以布尔值作为值（确切地说：当对象被添加时为 true）存储为哈希表。

为什么应该使用集合？如果您想强制唯一性并且不需要任何排序-集合是您的最佳选择。当您真正不关心唯一性而排序很重要时-数组是您的选择。

否则-您需要任意决定 ;)

- Esse

Answer 3

出于显而易见的原因，请参阅此处的其他答案。 出于性能原因，请参见MRI Ruby 1.9.3中此小基准测试的结果：

require 'benchmark' 
require 'set' 

array = (1..100000).to_a 
set = array.to_set 
#hash = Hash[array.map {|x| [x, nil]}] #beter voor heel grote volumes mar trager
hash = Hash[*array]

Benchmark.bmbm do |x| 
  x.report("Set.include?")   { 10000.times { set.include?(99999) } }
  x.report("Array.include?") { 10000.times { array.include?(99999) } } 
  x.report("Hash.include?")  { 10000.times { hash.include?(99999) } } 
end 

这提供了

Rehearsal --------------------------------------------------
Set.include?     0.000000   0.000000   0.000000 (  0.015604)
Array.include?  37.940000   0.000000  37.940000 ( 38.651992)
Hash.include?    0.000000   0.000000   0.000000 (  0.001000)
---------------------------------------- total: 37.940000sec

                     user     system      total        real
Set.include?     0.000000   0.000000   0.000000 (  0.002001)
Array.include?  38.157000   0.000000  38.157000 ( 38.730615)
Hash.include?    0.000000   0.000000   0.000000 (  0.001001)

如果可能的话，使用Set或Hash有足够的理由。

- peter

---

太棒了。谢谢分享。 - Vitor Oliveira

Answer 4

从技术上讲，您可以使用Ruby Arrays和Sets实现相同的结果。但是，对于Ruby的Modules和Classes也可以这样说。您可以在两者中都拥有变量和方法，但它们的用途不同，当其他人阅读代码时，他们将理解其含义，而无需尝试解释您的设计决策。

我想Sets和Arrays的情况也是一样的。您可以使用数组实现相同的结果，但使用集合时，您的变量传达了关于业务逻辑的附加信息（内容必须唯一）。基本上，它们是不同的数据结构。我们之所以有不同的数据结构，是有原因的。

其次，使用集合进行操作（例如.subset?，.superset?，.intersect?等）使您的代码更易读。新手可能会猜测array | array操作的含义，但使用集合则完全清楚。看看哪一个更易读：

([1, 2, 3] & [2, 3]).empty?          # => false
Set[1, 2, 3].intersect? Set[2, 3]    # => true

第三，与集合的交集操作可能已经进行了预优化，运行速度可能更快。

- Uzbekjon