101

我将 Ruby 1.8.6 与 Rails 1.2.3 一起使用,并且需要确定两个数组是否具有相同的元素,无论它们的顺序是否相同。保证其中一个数组不包含重复项(另一个可能,在这种情况下答案是否定的)。

我的第一个想法是

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

但我想知道是否有更有效或更惯用的方式来做到这一点。

4

9 回答 9

151

这不需要转换来设置:

a.sort == b.sort
于 2012-06-06T18:34:50.343 回答
42

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

或者您可以检查: ((A-B) + (B-A)).blank?

同样正如@cort3z 所建议的,这个解决方案 als0 适用于多态数组,即

 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?

于 2012-12-23T14:36:41.137 回答
29

红宝石 2.6+

Rubydifference在 2.6 中引入。

这在这里提供了一个非常快速、非常易读的解决方案,如下所示:

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是单向差异的绝佳选择。

如果你需要双向检查,那就是性能和可读性之间的平衡。对我来说,可读性很重要,但这是一个根据具体情况进行的调用。

希望对某人有所帮助!

于 2019-06-24T15:18:17.473 回答
24

速度比较

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
于 2016-04-21T12:09:52.420 回答
17

当 和 的元素abComparable

a.sort == b.sort

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

于 2014-02-25T04:41:56.783 回答
8

如果你期望[: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
于 2012-06-06T18:27:08.160 回答
7

如果您知道数组的长度相等并且两个数组都不包含重复项,那么这也可以:

( array1 & array2 ) == array1

说明:在这种情况下,&运算符返回 a1 的副本,其中不包含在 a2 中找不到的任何项目,这与原始 a1 相同,前提是两个数组具有相同的内容且没有重复。

Analyis:鉴于顺序没有改变,我猜这是作为一个双迭代实现如此一致O(n*n),特别是对于大型数组来说比a1.sort == a2.sort在最坏情况下应该执行的更糟糕O(n*logn)

于 2013-02-20T13:56:55.000 回答
3

结合起来&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
于 2019-06-21T11:30:22.003 回答
2

一种方法是遍历没有重复的数组

# 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。因此,您必须反转整个事物以确定它是否匹配。

于 2012-06-06T18:30:32.277 回答