Ruby：最快的方法来测试列表中的任何数字是否在范围列表中？

Question

一种可能的方法来检查，如果从列表中至少一个数字是其他列表中的一个范围是这样的：

# Input example: 
# numbers = [123, 345, 567] 
# ranges =[(1..10), (60..80), (200..400)] 
def is_in(numbers, ranges) 
    numbers.each do |n| 
    ranges.each do |r| 
     return true if r.include?(n) 
    end 
    end 
    false 
end 

什么是这种情况下每一个最快的方法：

1. 只有号码列表大
2. 只有范围列表大
3. 两者都是大

Answer 1

如果您的数组数组很大且有序，则可以使用Ruby 2.0的新二进制搜索方法Array#bsearch来加速范围覆盖检查从O（N）复杂度到O（logN）。

class Range 
    def fast_cover_any?(ordered_arr) 
    lo = first 
    probe = ordered_arr.bsearch {|x| x >= lo} 
    probe && exclude_end? ? probe < last : probe <= last 
    end 
end 

ranges.any? { |r| r.fast_cover_any?(numbers) } 

Answer 2

ranges =[(1..10), (60..80), (200..400)] 

numbers = [123, 700, 567] 
numbers.any?{|x| ranges.any? {|y| y.include? x}} #=> false 

numbers = [123, 400, 567] 
numbers.any?{|x| ranges.any? {|y| y.include? x}} #=> true 

使用ordered list：

ranges =[(1..10), (60..80), (200..400)] 

numbers = [123, 300, 567] 
p numbers.sort.any?{|y| ranges.sort_by(&:first).bsearch{|x| x.include? y}} #=> true 

numbers = [123, 700, 567] 
p numbers.sort.any?{|y| ranges.sort_by(&:first).bsearch{|x| x.include? y}} #=> false 

Answer 3

简单的答案是存放在组织结构中的数据结构中的一个，并搜索另一个列表中的元素。

假设您有两个列表x和y分别为长度为m和n。

若m < < N：排序x和找到在排序列表Y的元素

如果M >> N：排序y和，并在排序列表

如果找到的元素从X他们是相同的大小选择任何他们进行排序。

如何组织范围： 使用每个范围的开始对列表进行排序。如果两个范围重叠合并它们。最后，您将获得根据范围的开始排序的非重叠范围列表。