CODEWITHSUNDEEP
arraysrubysorting
Gauthier
Gauthier

Reputation: 195

Ruby: Efficient way to compare two arrays of arrays

I search the most efficient way to get the difference between two arrays of arrays. At this point I don't know if working with hash would be better.

I have two arrays of array containing one id and one datetime converted to int.

a = [[1, 1234],[2, 7345],[3, 12769],[4, 13456], [5, 34765]]
b = [[1, 1234],[3, 12769],[2, 7345],[5, 39875],[4, 13459]]

My goal is to know if the date contained in each arrays of a is superior to the date contained with the same id in b and keep the arrays that match the comparaison otherwise I would have done something like a - b.

What is the fastest and cleanest way even with large amounts of arrays ?

The alternative way would be with hash, I don't really know what to use.

a = [{id: 1, date: 1234},{id: 2, date: 7345},{id: 3, date: 12769},{id: 4, date: 13456},{id: 5, date: 34765}]
b = [{id: 1, date: 1234},{id: 3, date: 12769},{id: 2, date: 7345},{id: 5, date: 39875}, {id: 4, date: 13459}]

What are your thoughts ?

Upvotes: 1

Views: 266

Answers (2)

max pleaner
max pleaner

Reputation: 26788

It is easier and better performing to have b be a hash. Fortunately, an array of 2-element arrays can be directly converted to hash with .to_h (and back to array with .to_a).

# this will make an { <id> => <date> } hash
b_hash = b.to_h

Now the filter step just involves a select over a, checking the associated values in b_hash. I use |(id, date)| to destructure the array into its individual elements:

result = a.select do |(id, date)|
  b_hash[id] > date
end

Note that you do want to keep the .to_h call outside the select loop since it's an O(N) operation.

You could do it without converting b.to_h, you would just need to loop through b for each element of a, taking the time complexity from O(N) to O(N^2)

Upvotes: 3

Cary Swoveland
Cary Swoveland

Reputation: 110735

Suppose a and b are defined as follows.

a = [[1, 1235] ,[2, 7345], [3, 12760],[4, 13466], [5, 34765]]
b = [[5, 39875],[3, 12769],[2, 7345], [1, 1234],  [4, 13459]]

Then

a.select { |id,date| date > b.assoc(id).last }
  #=> [[1, 1235], [4, 13466]]

See Array#assoc. This is not the most efficient solution but it may be fine if a and b are not too large. I posted it mainly because it uses a method that I rarely use.

Upvotes: 3

Related Questions