我将 Ruby 1.8.6 与 Rails 1.2.3 一起使用,并且需要确定两个数组是否具有相同的元素,无论它们的顺序是否相同。保证其中一个数组不包含重复项(另一个可能,在这种情况下答案是否定的)。
我的第一个想法是
require 'set'
a.to_set == b.to_set
但我想知道是否有更有效或更惯用的方式来做到这一点。
我将 Ruby 1.8.6 与 Rails 1.2.3 一起使用,并且需要确定两个数组是否具有相同的元素,无论它们的顺序是否相同。保证其中一个数组不包含重复项(另一个可能,在这种情况下答案是否定的)。
我的第一个想法是
require 'set'
a.to_set == b.to_set
但我想知道是否有更有效或更惯用的方式来做到这一点。
这不需要转换来设置:
a.sort == b.sort
对于两个数组 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?
红宝石 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
是单向差异的绝佳选择。
如果你需要双向检查,那就是性能和可读性之间的平衡。对我来说,可读性很重要,但这是一个根据具体情况进行的调用。
希望对某人有所帮助!
速度比较
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
如果你期望[: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
如果您知道数组的长度相等并且两个数组都不包含重复项,那么这也可以:
( array1 & array2 ) == array1
说明:在这种情况下,&
运算符返回 a1 的副本,其中不包含在 a2 中找不到的任何项目,这与原始 a1 相同,前提是两个数组具有相同的内容且没有重复。
Analyis:鉴于顺序没有改变,我猜这是作为一个双迭代实现如此一致O(n*n)
,特别是对于大型数组来说比a1.sort == a2.sort
在最坏情况下应该执行的更糟糕O(n*logn)
。
结合起来&
也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
一种方法是遍历没有重复的数组
# 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。因此,您必须反转整个事物以确定它是否匹配。