Check if two arrays have the same contents (in any order)
RubyArraysComparisonRuby Problem Overview
I'm using Ruby 1.8.6 with Rails 1.2.3, and need to determine whether two arrays have the same elements, regardless of whether or not they're in the same order. One of the arrays is guaranteed not to contain duplicates (the other might, in which case the answer is no).
My first thought was
require 'set'
a.to_set == b.to_set
but I was wondering if there was a more efficient or idiomatic way of doing it.
Ruby Solutions
Solution 1 - Ruby
This doesn't require conversion to set:
a.sort == b.sort
Solution 2 - Ruby
for two arrays A and B:
A and B have same contents if:
(A-B).blank? and (B-A).blank?
or you can just check for:
((A-B) + (B-A)).blank?
Also as suggested by @cort3z this solution als0 works for polymorphic arrays i.e
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`
::::::::::: EDIT :::::::::::::
As suggested in the comments, above solution fails for duplicates.Although as per the question that is not even required since the asker is not interested in duplicates(he is converting his arrays to set before checking and that masks duplicates and even if you look at the accepeted answer he is using a .uniq operator before checking and that too masks duplicates.). But still if duplicates interests you ,Just adding a check of count will fix the same(as per the question only one array can contain duplicates). So the final solution will be:
A.size == B.size and ((A-B) + (B-A)).blank?
Solution 3 - Ruby
Ruby 2.6+
Ruby's introduced difference in 2.6.
This gives a very fast, very readable solution here, as follows:
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
However, the reverse isn't true:
a = [1, 2, 3]
b = [1, 2, 3, 4, 5, 6]
a.difference(b).any?
# => false
This means to get the difference in both directions it is necessary to run:
a.difference(b).any? || b.difference(a).any?
Running the benchmarks:
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
My takeaway would be that difference is a great choice for a one directional diff.
If you need to check in both directions, it's a balance between performance and readability. For me, the readability pips it, but that's a call to be made on a case by case basis.
Hope that helps someone!
Solution 4 - Ruby
Speed comparsions
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
Solution 5 - Ruby
When the elements of a and b are Comparable,
a.sort == b.sort
Correction of @mori's answer based on @steenslag's comment
Solution 6 - Ruby
If you expect [:a, :b] != [:a, :a, :b] to_set doesn't work. You can use frequency instead:
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
Solution 7 - Ruby
If you know the arrays are of equal length and neither array contains duplicates then this works too:
( array1 & array2 ) == array1
Explanation: the & operator in this case returns a copy of a1 sans any items not found in a2, which is the same as the original a1 iff both arrays have the same contents with no duplicates.
Analyis: Given that the order is unchanged, I'm guessing this is implemented as a double iteration so consistently O(n*n), notably worse for large arrays than a1.sort == a2.sort which should perform with worst-case O(n*logn).
Solution 8 - Ruby
combining & and size may be fast too.
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
Solution 9 - Ruby
One approach is to iterate over the array with no duplicates
# assume array a has no duplicates and you want to compare to b
!a.map { |n| b.include?(n) }.include?(false)
This returns an array of trues. If any false appears, then the outer include? will return true. Thus you have to invert the whole thing to determine if it's a match.