Рассчитать пересечение двух массивов диапазонов (дат) в рубине

Question

Учитывая два больших массива диапазонов...

A = [0..23, 30..53, 60..83, 90..113]
B = [-Float::INFINITY..13, 25..33, 45..53, 65..73, 85..93]

Когда я делаю логическое соединение...

C = A.mask(B)

Тогда я ожидаю

describe "Array#mask" do
  it{expect(C = A.mask(B)).to eq([0..13, 30..33, 45..53, 65..73, 90..93])}
end

Такое ощущение, что так и должно быть...

C = A & B
=> []

но это пусто, потому что ни один из диапазонов не идентичен.

Вот наглядный пример.

,

Я включил Infinity в диапазон, потому что решения этой проблемы обычно включают преобразование Range в массив или набор.

Мое текущее решение Это мое текущее решение с прохождением тестов на скорость и точность. Я искал комментарии и / или предлагаемые улучшения. Во втором тесте используется превосходный гем IceCube для генерации массива диапазонов дат. В моем методе маски есть неявное предположение, что вхождения каждого диапазона дат в каждом расписании не перекрываются.

require 'pry'
require 'rspec'
require 'benchmark'
require 'chronic'
require 'ice_cube'
require 'active_support'
require 'active_support/core_ext/numeric'
require 'active_support/core_ext/date/calculations'

A = [0..23, 30..53, 60..83, 90..113]
B = [-Float::INFINITY..13, 25..33, 45..53, 65..73, 85..93]

class Array
  def mask(other)
    a_down = self.map{|r| [:a, r.max]}
    a_up = self.map{|r| [:a, r.min]}

    b_down = other.map{|r| [:b, r.max]}
    b_up = other.map{|r| [:b, r.min]}

    up = a_up + b_up
    down = a_down + b_down

    a, b, start, result = false, false, nil, []
    ticks = (up + down).sort_by{|i| i[1]}
    ticks.each do |tick|
      tick[0] == :a ? a = !a : b = !b
      result << (start..tick[1]) if !start.nil?
      start = a & b ? tick[1] : nil
    end
    return result
  end
end

describe "Array#mask" do
  context "simple integer array" do
    it{expect(C = A.mask(B)).to eq([0..13, 30..33, 45..53, 65..73, 90..93])}
  end

  context "larger date ranges from IceCube schedule" do
    it "should take less than 0.1 seconds" do
      year = Time.now..(Time.now + 52.weeks)
      non_premium_schedule = IceCube::Schedule.new(Time.at(0)) do |s|
        s.duration = 12.hours
        s.add_recurrence_rule IceCube::Rule.weekly.day(:monday, :tuesday, :wednesday, :thursday, :friday).hour_of_day(7).minute_of_hour(0)
      end
      rota_schedule = IceCube::Schedule.new(Time.at(0)) do |s|
        s.duration = 7.hours
        s.add_recurrence_rule IceCube::Rule.weekly(2).day(:tuesday).hour_of_day(15).minute_of_hour(30)
      end
      np = non_premium_schedule.occurrences_between(year.min, year.max).map{|d| d..d+non_premium_schedule.duration}
      rt = rota_schedule.occurrences_between(year.min, year.max).map{|d| d..d+rota_schedule.duration}
      expect(Benchmark.realtime{np.mask(rt)}).to be < 0.1
    end
  end
end

Кажется странным, что вы не можете сделать это с помощью существующих основных методов Ruby? Я что-то пропустил? Я нахожу себя вычислять пересечения диапазонов на довольно регулярной основе.

Мне также пришло в голову, что вы можете использовать тот же метод, чтобы найти пересечение между двумя отдельными диапазонами, передавая массивы из одного элемента. например

[(54..99)].mask[(65..120)]

Я понимаю, что вроде как ответил на свой вопрос, но решил оставить его здесь как ссылку для других.

Answer 1

Я не уверен, что действительно понимаю ваш вопрос; Я немного смущен вашим expect заявление, и я не знаю, почему ваши массивы не одинакового размера. Тем не менее, если вы хотите вычислить пересечение двух диапазонов, мне нравится эта обезьяна-патч (из Ruby: пересечение между двумя диапазонами):

class Range
  def intersection(other)
    return nil if (self.max < other.begin or other.max < self.begin) 
    [self.begin, other.begin].max..[self.max, other.max].min
  end
  alias_method :&, :intersection
end

и тогда вы можете сделать:

A = [0..23, 30..53, 60..83, 0..0, 90..113]
B = [-Float::INFINITY..13, 25..33, 45..53, 65..73, 85..93]

A.zip(B).map { |x, y| x & y }
# => [0..13, 30..33, nil, nil, 90..93]

что кажется разумным результатом...

РЕДАКТИРОВАТЬ

Если вы обезьяна Range как написано выше, а затем сделать:

# your initial data
A = [0..23, 30..53, 60..83, 90..113]
B = [-Float::INFINITY..13, 25..33, 45..53, 65..73, 85..93]

A.product(B).map {|x, y| x & y }.compact
# => [0..13, 30..33, 45..53, 65..73, 90..93]

Вы получаете результаты, которые вы указываете. Понятия не имею, как он сравнивает по производительности, и я не уверен насчет порядка сортировки...