设置在红宝石中的优点

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.

Answer 1

当然,无论你做什么Set,都有办法做到这一点Array.使用a的优点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

Answer 2

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

数组

• 可以有重复的元素
• 维持订单
• 可以按顺序迭代
• 搜索元素很慢,附加元素并从位置获取元素很快
• 保持元素的独特性很慢

集

• 不能有重复的元素
• 没有订购(理论背景:https://en.wikipedia.org/wiki/Partially_ordered_set)
• 搜索元素的存在是快速的,附加元素是快速的
• 独特性是由设计给出的

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

在Ruby内部设置使用哈希存储,如文档中所述:

Set使用Hash作为存储,因此您必须注意以下几点:

元素的相等性是根据Object#eql确定的？和Object #hash.Set假定每个元素的标识在存储时不会更改.修改集合的元素会将集合呈现为不可靠状态.当要存储字符串时,将存储字符串的冻结副本,除非原始字符串已被冻结.

当您查看代码时,它在内部存储为哈希,用户给定的对象作为键,布尔值作为值(确切地说:添加对象时为true).

为什么要使用套装？如果您想要强制执行唯一性而且您不需要任何订购 - 套装是您的最佳选择.当您不关心唯一性并且订购很重要时 - Array是您的选择.

否则 - 你需要仲裁决定;)

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在可能的情况下使用。