我有两个排序的浮点数数组(通常是800-1500个元素),两个数组的大小可以相差+20-30%。
我正在寻找一种快速的方法,从最大数组的元素中,根据最小的差异,选出一对小数组的所有元素。
目前我正在使用这个

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

这是我程序的关键元素,它经常被调用,不幸的是它对我来说太慢了。

最佳答案

使用min_by的问题是,对于bigger的每个元素,必须遍历smaller的每个元素。一旦找到差价最低的那对,就试着早点破发。

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

10-07 14:18