检查两个数组是否具有相同的内容（任意顺序）

Question

我正在使用 Ruby 1.8.6 与 Rails 1.2.3，需要确定两个数组是否具有相同的元素，无论它们是否按照相同的顺序排序。其中一个数组保证不包含重复项（另一个可能包含，此时答案为“否”）。

我的第一反应是：

require 'set'
a.to_set == b.to_set

不过我想知道有没有更加高效或者习惯的方法可以做到这件事。

- Taymon

---

可能是重复的问题：Ruby - 数组A是否包含数组B的所有元素 - fl00r

尝试使用array.should =~ another_array进行检查。请参考https://dev59.com/_nA85IYBdhLWcg3wBOzh。 - Athena

你可以通过以下方式避免很多混淆：1）说明数组元素是否必须可排序；2）提供一个简单的例子来澄清你所说的“两个数组是否具有相同的元素”（例如，[1,2]和[2,1,1]是否具有相同的元素？） - Cary Swoveland

Ruby 2.6引入了difference，提供了一种非常快速和易读的解决方案。更多信息请参见此处。 - SRack

Answer 1

这不需要进行转换即可设置：

a.sort == b.sort

- Mori

---

不进行转换？那么.uniq.sort是什么意思呢？除了uniq在内部类似于to_set外，还有额外的.to_a.sort。 - Victor Moroz

接受这个答案，因为它最接近我最终使用的方法，尽管没有使用 uniq。实际上，我最终使用了 Range#to_a 创建其中一个数组，所以我只需要对另一个数组进行 sort 操作。 - Taymon

如果数组中包含不能简单排序的元素（例如哈希数组），则此方法不起作用。Sahil Dhankhar的解决方案似乎是更通用的解决方案。 - brad

非常简单，适用于小型数组，其中对它们进行排序的性能不太昂贵。谢谢。 - Joshua Pinter

Answer 2

对于两个数组 A 和 B： 如果 (A-B).blank? and (B-A).blank?，则 A 和 B 具有相同的内容。

或者你可以检查 ((A-B) + (B-A)).blank?。

另外，正如 @cort3z 建议的那样，该解决方案也适用于多态数组，即

 A = [1 , "string", [1,2,3]]
 B = [[1,2,3] , "string", 1]
 (A-B).blank? and (B-A).blank? => true
 # while A.uniq.sort == B.uniq.sort will throw error `ArgumentError: comparison of Fixnum with String failed` 

:::::::::::编辑:::::::::::::

根据评论的建议，上面的解决方案对于重复项会失败。尽管根据问题的要求，这甚至不需要，因为提问者并不关心重复项（他在检查之前将数组转换为集合，并且这掩盖了重复项，即使您看一下已接受的答案，他也在使用 .uniq 运算符进行检查，这也掩盖了重复项）。但是如果您关心重复项，只需添加一个计数检查即可解决此问题（根据问题，只有一个数组可以包含重复项）。 因此，最终解决方案为： A.size == B.size and ((A-B) + (B-A)).blank?

- Sahil Dhankhar

---

如果任何一个数组包含重复项，这将失败。例如，如果 A=[1] 和 B=[1,1]，则 (A-B) 和 (B-A) 都将返回空白。请参阅数组文档。 - jtpereyda

@dafrazzman 完全同意你的观点。我已经修改了我的答案以纳入你的反馈。但是，如果你仔细看问题（或接受的答案），提问者正在使用：a.to_set == b.to_set，而接受的答案正在使用a.uniq.sort == b.uniq.sort，并且两者都与((A-B) + (B-A)).blank?给出完全相同的结果，对于A=[1]和B=[1,1]，你同意吗？既然他只是在寻求对他原始解决方案的改进，那么我的原始解决方案仍然有效:)。你同意吗？ - Sahil Dhankhar

这个解决方案非常好，因为它可以处理多种类型的对象。比如你有 A = [123, "test", [], some_object, nil] 和 B = A#because I am lazy，那么 A.uniq.sort 就会抛出错误（字符串和数组的比较失败）。 - Automatico

这是否是O(n)的，因为它取决于数组大小？（线性） - user3007294

如果数组大小相同但重复元素不同，则无法正常工作。例如，A = [1, 1, 2] 和 B = [1, 2, 2]。 - Boudi

#blank? 是 Rails 特有的。并不是每个人都在 Rails 的世界里...请使用标准库方法 #empty?。 - Huliax

Answer 3

Ruby 2.6+

在Ruby 2.6中引入了 difference 方法。

这提供了一个非常快速、易读的解决方案，如下所示：

a = [1, 2, 3, 4, 5, 6]
b = [1, 2, 3, 4, 5, 6]

a.difference(b).any?
# => false
a.difference(b.reverse).any?
# => false

a = [1, 2, 3, 4, 5, 6]
b = [1, 2, 3]
a.difference(b).any?
# => true

然而，反过来并不成立：

a = [1, 2, 3]
b = [1, 2, 3, 4, 5, 6]
a.difference(b).any?
# => false

这意味着要获取双向差异，需要运行：

a.difference(b).any? || b.difference(a).any?

运行基准测试：

a = Array.new(1000) { rand(100) }
b = Array.new(1000) { rand(100) }

Benchmark.ips do |x|
  x.report('sort')   { a.sort == b.sort }  
  x.report('sort!')  { a.sort! == b.sort! }  
  x.report('to_set') { a.to_set == b.to_set }  
  x.report('minus')  { ((a - b) + (b - a)).empty? }  
  x.report('difference') { a.difference(b).any? }
  x.report('difference two way') { a.difference(b).any? || b.difference(a).any? }
end

                sort     10.175k (± 6.2%) i/s -     50.778k in   5.015112s
               sort!     10.513k (± 6.8%) i/s -     53.212k in   5.089106s
              to_set      4.953k (± 8.8%) i/s -     24.570k in   5.037770s
               minus     15.290k (± 6.6%) i/s -     77.520k in   5.096902s
          difference     25.481k (± 7.9%) i/s -    126.600k in   5.004916s
  difference two way     12.652k (± 8.3%) i/s -     63.232k in   5.038155s

我的理解是，difference 是一个很好的选择来进行单向的差异比较。

如果需要双向检查，则需要在性能和可读性之间做出权衡。对我而言，可读性更重要，但这是需要根据具体情况来决定的。

希望这对某些人有所帮助！

- SRack

Answer 4

速度比较

require 'benchmark/ips'
require 'set'

a = [1, 2, 3, 4, 5, 6]
b = [1, 2, 3, 4, 5, 6]

Benchmark.ips do |x|
  x.report('sort')   { a.sort == b.sort }  
  x.report('sort!')  { a.sort! == b.sort! }  
  x.report('to_set') { a.to_set == b.to_set }  
  x.report('minus')  { ((a - b) + (b - a)).empty? }  
end  

Warming up --------------------------------------
            sort    88.338k i/100ms
           sort!   118.207k i/100ms
          to_set    19.339k i/100ms
           minus    67.971k i/100ms
Calculating -------------------------------------
            sort      1.062M (± 0.9%) i/s -      5.389M in   5.075109s
           sort!      1.542M (± 1.2%) i/s -      7.802M in   5.061364s
          to_set    200.302k (± 2.1%) i/s -      1.006M in   5.022793s
           minus    783.106k (± 1.5%) i/s -      3.942M in   5.035311s

- Morozov

---

顺便提一下，元素的顺序不会影响“sort”的速度。 - Morozov

让我感到惊讶的是...我原本以为由集合比较所需的O(n)时间复杂度查找会胜过其他所有方法。因此，任何良好实现的排序都需要O(n logn)。而将其转换为集合并查找值总体上只需要O(n)时间。 - Oleg Afanasyev

当数组长度足够大，O(n logn) 开始比将数组转换为集合所需的努力更加重要时，我希望 to_set 方法能够开始表现出更好的性能。 - Andrius Chamentauskas

这很有帮助，但本身并不是一个答案？或许更好的方法是将其添加到现有的解决方案中？ - SRack

在minus中，建立联合是可惜的。(a - b).empty? && (b - a).empty?。 - undefined

Answer 5

当 a 和 b 的元素 Comparable 时，

a.sort == b.sort

根据@steenslag的评论更正@mori的答案。

- Jared Beck

---

当 a 和 b 能够被排序时。 - Cary Swoveland

Answer 6

如果你期望[:a, :b] != [:a, :a, :b]，那么使用to_set就行不通了。你可以使用频率代替：

class Array
  def frequency
    p = Hash.new(0)
    each{ |v| p[v] += 1 }
    p
  end
end

[:a, :b].frequency == [:a, :a, :b].frequency #=> false
[:a, :b].frequency == [:b, :a].frequency #=> true

- Victor Moroz

---

如果他关心频率，为什么不只是用a.sort == b.sort呢？ - fl00r

如果项目无法进行比较，会怎样呢？["", :b].frequency == [:b, ""].frequency #=> true - Victor Moroz

你可以执行类似于 a.group_by{|i| i} == b.group_by{|i| i} 这样的功能。 - fl00r

Answer 7

如果您知道数组的长度相等且两个数组都不包含重复元素，则以下方法也可行：

( array1 & array2 ) == array1

说明：在这种情况下，& 运算符返回 a1 的一个副本，其中不包含在 a2 中找到的任何项，当且仅当两个数组具有相同的内容且没有重复项时，它与原始 a1 相同。

分析：考虑到顺序不变，我猜测这是通过双重迭代实现的，因此时间复杂度一致为 O(n*n)，对于大型数组而言，明显比 a1.sort == a2.sort 更差，后者的最坏情况下性能应该为 O(n*logn)。

- Nat

---

有时候不起作用：a1 = [1,2,3]，a2 = [2, 1, 3] a1 && a2 对我来说返回 [2,1,3]，这与 a1 不相等。 - Kalyan Raghu

@Kaylan，你是不是指只有当a1==a2时才能正常工作？如果将等式右侧的array1替换为array2，它可能会起作用，但我怀疑&返回的元素顺序是否得到保证。 - Cary Swoveland

@KalyanRaghu & 是数组的集合交集运算符，&& 是逻辑 AND 运算符 - 它们非常不同！ - Kimball

Answer 8

结合使用&和size也可能更快。

require 'benchmark/ips'
require 'set'

Benchmark.ips do |x|
  x.report('sort')   { a.sort == b.sort }  
  x.report('sort!')  { a.sort! == b.sort! }  
  x.report('to_set') { a.to_set == b.to_set }  
  x.report('minus')  { ((a - b) + (b - a)).empty? }
  x.report('&.size') { a.size == b.size && (a & b).size == a.size }  
end  

Calculating -------------------------------------
                sort    896.094k (±11.4%) i/s -      4.458M in   5.056163s
               sort!      1.237M (± 4.5%) i/s -      6.261M in   5.071796s
              to_set    224.564k (± 6.3%) i/s -      1.132M in   5.064753s
               minus      2.230M (± 7.0%) i/s -     11.171M in   5.038655s
              &.size      2.829M (± 5.4%) i/s -     14.125M in   5.010414s

- Todoroki

---

& 从 Ruby 官方文档中的描述 Set Intersection — 返回一个包含两个数组共有的唯一元素的新数组。顺序保持与原始数组相同。 - buncis

Answer 9

一种方法是在没有重复项的情况下遍历数组

# assume array a has no duplicates and you want to compare to b
!a.map { |n| b.include?(n) }.include?(false)

这将返回一个由true组成的数组。如果出现任何false，则外部的include?将返回true。因此，您必须反转整个过程以确定它是否匹配。

- Ron

---

@Victor Moroz，你是正确的，频率计数只是O(n)。 - Ron

当b包含a的所有元素以及一些额外元素时，这种方法将无法运行。 - Toby 1 Kenobi