Fast Ruby method / algorithm to pair elements of two arrays

Question

I have two sorted arrays of float numbers (usually 800-1500 elements), size of the two arrays can be different by +-20-30 %. I am looking for a fast method which pick a correspondent pair of all elements of the smaller array from the elements of the biggest array on the basis of minimal difference.

Currently I am using this

def get_pairs(ary1,ary2)
  if ary1.size<ary2.size then
    smaller=ary1;bigger=ary2
  else
    smaller=ary2;bigger=ary1;
  end
  p=Array.new(smaller.size)
  smaller.each_with_index do |z,i|
     pair=bigger.min_by{|elem| (elem-z).abs}
     p[i]=[z, pair]
  end
  return p
end

This is the key element of my program, it is called very often and unfortunately it is too slow for me.

See related question http://stackoverflow.com/questions/3815116/given-two-arrays-a-and-b-find-all-pairs-of-elements-a1-b1-such-that-a1-belong — Mihai8, Jul 23 '14 at 17:50

fbonetti · Accepted Answer · 2014-07-23T19:38:07.310

1

The problem with using min_by is that you have to iterate over every single element of bigger for each element of smaller. Try breaking early once you've found the pair with lowest difference.

def get_pairs(a, b)
  smaller, bigger = [a, b].map(&:sort).sort_by(&:length)

  smaller.map do |x|
    lowest_diff = nil
    lowest_element = nil

    bigger.each_with_index do |y, i|
      diff = (x - y).abs

      if lowest_diff.nil? || diff < lowest_diff
        lowest_diff = diff
        lowest_element = y
      elsif diff > lowest_diff || y == bigger.last
        break [x, lowest_element]
      end
    end
  end
end

edited Jul 23 '14 at 19:38

answered Jul 23 '14 at 19:01

fbonetti

6,652
3
34
32

Thx, I don't understand exactly but it works and reasonably faster! – Konstantin Jul 23 '14 at 20:31
@Konstantin Think of it this way - with your original algorithm, if the small array had 1,000 elements and the big array had 1,000 elements, you would need to execute 1,000,000 comparisons! The algorithm that I posted exits the loop once it finds the 'optimal' pair, so requires far fewer comparisons. – fbonetti Jul 23 '14 at 21:33
Sometimes it fails, I am using this version now: ` def get_p2_fast(a,b) if a.size<=b.size then smaller=a;bigger=b else smaller=b;nagyobb=a; end p=Array.new(smaller.size) pointer=0 smaller.each_with_index do |z,i| while z-bigger[pointer]>=0 && pointer<=bigger.size-2 do pointer=pointer+1 end if (bigger[pointer]-z).abs<=(bigger[pointer-1]-z).abs then pair=bigger[pointer] else pair=bigger[pointer-1] pointer=pointer-1 end p[i]=[z, pair] end return p end ` – Konstantin Jul 25 '14 at 21:38

score 0 · Answer 2 · answered Jul 25 '14 at 21:41

Sometimes it fails, I am using this version now:

def get_p2_fast(a,b)
  if a.size<=b.size then
    smaller=a;bigger=b
  else
    smaller=b;nagyobb=a;
  end
  p=Array.new(smaller.size)
  pointer=0
  smaller.each_with_index do |z,i|
     while z-bigger[pointer]>=0 && pointer<=bigger.size-2 do
       pointer=pointer+1
     end
     if (bigger[pointer]-z).abs<=(bigger[pointer-1]-z).abs then
       pair=bigger[pointer]
     else
       pair=bigger[pointer-1]
       pointer=pointer-1
     end
     p[i]=[z, pair]
  end
  return p
end

Fast Ruby method / algorithm to pair elements of two arrays

2 Answers2