Array difference by explicitly specified method or block

user_1934428 0
Viewed 81

If I have Arrays a and b, the expression a-b returns an Array with all those elements in a which are not in b. "Not in" means unequality (!=) here.

In my case, both arrays only contain elements of the same type (or, from the ducktyping perspective, only elements which understand a "equality" method f). Is there an easy way to specify this f as a criterium of equality, in a similar way I can provide my own comparator when doing sort? Currently, I implemented this explicitly :

# Get the difference a-b, based on 'f':
a.select { |ael| b.all? {|bel| ael.f != bel.f} }

This works, but I wonder if there is an easier way.

UPDATE: From the comments to this question, I get the impression, that a concrete example would be appreciated. So, here we go:

class Dummy; end

# Create an Array of Dummy objects.
a = Array.new(99) { Dummy.new }

# Pick some of them at random
b = Array.new(10) { a.sample }

# Now I want to get those elements from a, which are not in b.
diff = a.select { |ael| b.all? {|bel| ael.object_id != bel.object_id} }

Of course in this case, I could also have said ! ael eql? bel, but in my general solution, this is not the case.

ruby
1 Answers

The "normal" object equality for e.g. Hashes and set operations on Arrays (such as the - operation) uses the output of the Object#hash method of the contained objects along with the semantics of the a.eql?(b) comparison.

This can be used to to improve performance. Ruby assumes here that two objects are eql? if the return value of their respective hash methods is the same (and consequently, assumes that two objects returning different hash values to not be eql?).

For a normal a - b operation, this can thus be used to first calculate the hash value of each object once and then only compare those values. This is quite fast.

Now, if you have a custom equality, your best bet would be to overwrite the object's hash methods so that they return suitable values for those semantics.

A common approach is to build an array containing all data taking part of the object's identity and getting its hash, e.g.

class MyObject
  #...
  attr_accessor :foo, :bar 

  def hash
    [self.class, foo, bar].hash
  end
end

In your object's hash method, you would than include all data that is currently considered by your f comparison method. Instead of actually using f then, you are using the default semantics of all Ruby objects and again can achieve quick set operations with your objects.

If however this is not feasible (e.g. because you need different equality semantics based on use-case), you could emulate what ruby does on your own.

With your f method, you could then perform your set operation as follows:

def f_difference(a, b)
  a_map = a.each_with_object({}) do |a_el, hash|
    hash[a_el.f] = a_el
  end

  b.each do |b_el|
    a_map.delete b_el.f
  end

  a_map.values
end

With this approach, you only need to calculate the f value of each of your objects once. We first build a hash map with all f values and elements from a and remove the matching elements from b according to their f values. The remaining values are the result.

This approach saves you from having to loop over b for each object in a which can be slow of you have a lot of objects. If however you only have a few objects on each of your arrays, your original approach should already be fine.

Let's have a look at a benchmark whee I use the standard hash method in place of your custom f to have a comparable result.

require 'benchmark/ips'

def question_diff(a, b)
  a.select { |ael| b.all? {|bel| ael.hash != bel.hash} }
end

def answer_diff(a, b)
  a_map = a.each_with_object({}) do |a_el, hash|
    hash[a_el.hash] = a_el
  end

  b.each do |b_el|
    a_map.delete b_el.hash
  end

  a_map.values
end

A = Array.new(100) { rand(10_000) }
B = Array.new(10) { A.sample }

Benchmark.ips do |x|
  x.report("question") { question_diff(A, B) }
  x.report("answer") { answer_diff(A, B) }

  x.compare!
end

With Ruby 2.7.1, I get the following result on my machine, showing that the original approach from the question is about 5.9 times slower than the optimized version from my answer:

Warming up --------------------------------------
            question     1.304k i/100ms
              answer     7.504k i/100ms
Calculating -------------------------------------
            question     12.779k (± 2.0%) i/s -     63.896k in   5.002006s
              answer     74.898k (± 3.3%) i/s -    375.200k in   5.015239s

Comparison:
              answer:    74898.0 i/s
            question:    12779.3 i/s - 5.86x  (± 0.00) slower
user_4217050
Related