Efficient way to subtract arrays and get index of resulting subarray-CodePudding

Lets say I have the following arrays:

arr1 = [
  ['a', 'b'],
  ['c', 'd'],
  ['e', 'f']
]

arr2 = [
  ['g', 'h'],
  ['i', 'k'],
  ['a', 'b']
]

I want to find the elements in arr1 that do not exist in arr2 and the index of the elements in arr1

I can do this with the following but this isn't very efficient and is not a pretty solution. There can also be many elements in the arrays so this does not scale. Is there a better way to do this?

diff = arr1 - arr2

diff_with_index = diff.map { |x| { index: arr1.index(x), values: x } }

print diff_with_index
# [{:index=>1, :values=>["c", "d"]}, {:index=>2, :values=>["e", "f"]}]

CodePudding user response：

When you have to do multiple include? checks, the most efficient way is to turn one of the lists into a set or hash beforehand, so you can have O(1) lookup time, so something like this:

require 'set'
arr2_set = Set.new(arr2)
arr1.each_index.select { |idx| !arr2_set.include?(arr1[idx]) }

CodePudding user response：

Here is one way.

i1 = (0..arr1.size-1).to_a
  #=> [0, 1, 2]

h1 = arr1.zip(i1).to_h
  #=> {["a", "b"]=>0, ["c", "d"]=>1, ["e", "f"]=>2}

i1 - arr2.map { |a| h1[a] }
  #=> [1, 2]

Note that

arr2.map { |a| h1[a] }
  #=> [nil, nil, 0]