我有两个排序的浮点数数组(通常是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