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他們是相同的大小選擇任何他們進行排序。

如何組織範圍： 使用每個範圍的開始對列表進行排序。如果兩個範圍重疊合並它們。最後，您將獲得根據範圍的開始排序的非重疊範圍列表。