CODEWITHSUNDEEP
rubyalgorithm
fotanus
fotanus

Reputation: 20116

Ruby: Fastest way to test if any number from a list is in a list of ranges?

One possible way to check if at least one number from a list is in one range of other list is like the following:

# 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

What is the fastest way for each one of this cases:

  1. Only numbers list is big
  2. Only ranges list is big
  3. Both are big

Upvotes: 3

Views: 344

Answers (3)

Arup Rakshit
Arup Rakshit

Reputation: 118271

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

Using 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

Upvotes: 1

dbenhur
dbenhur

Reputation: 20408

If your number array is large AND ordered, you could speed up the range coverage check from O(N) complexity to O(logN) using Ruby 2.0's new binary search Array#bsearch method.

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) }

Upvotes: 3

ElKamina
ElKamina

Reputation: 7807

The simple answer is store one of the data structures in a organized structure and search the other list's elements.

Assume you have two lists x and y with lengths m and n respectively.

If m << n: sort x and and find elements from y in the sorted list

If m >> n: sort y and and find elements from x in the sorted list

If they are of same size choose any of them to sort.

How to organize ranges: Sort the list using start of each range. If two ranges overlap merge them. At the end you will have a list of non-overlapping ranges sorted according to start of the range.

Upvotes: 1

Related Questions