обнаружение конфликтов в повторяющихся событиях

Question

Я пишу приложение календаря, которое должно проверять наличие конфликтов между повторяющимися записями. Каждый объект Entry имеет метод recurferences () который возвращает массив диапазонов - каждый диапазон содержит начало и конец времена каждого будущего происшествия.

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

def conflicts?(other)
  conflicts = 0
  recurrences.each do |my_rec|
    other.recurrences.each do |other_rec|
      start, finish = other_rec.first, other_rec.last
      conflicts += 1 if my_rec.include?(start) || my_rec.include?(finish)
    end
  end
  conflicts > 0
end

recurferences () по умолчанию возвращает все вхождения между временем начала и время начала + 1 год

проблема в том, что этот метод не очень эффективен. Сравнение только двух записей, каждая с ежедневным повторением в течение 1 года, приводит к 365 * 365 сравнениям (на моей машине это занимает более 4 секунд). Может быть любое количество существующих записей, чтобы сравнить новую запись с таким метод, который у меня есть сейчас, бесполезен.

У меня нет компьютерных или математических знаний, но я был читая различные учебники по алгоритмам, и я не смог найти способ оптимизации метода. У кого-нибудь еще есть идеи?

спасибо

Dave

Answer 1

Прежде всего, вы можете улучшить это, просто вызвав ранний возврат функции:

def conflicts?(other)
  conflicts = 0
  recurrences.each do |my_rec|
    other.recurrences.each do |other_rec|
      start, finish = other_rec.first, other_rec.last
      return true if my_rec.include?(start) || my_rec.include?(finish)
    end
  end
  false
end

Это, однако, не улучшит среднюю производительность вашего алгоритма, но вызовет только одно сравнение в случае конфликта. Единственный вариант, который вы получили, - это раннее обнаружение «простых» столкновений. Так как

• Сохранить тип повторения (еженедельно, ежедневно, ежемесячно) в объекте повторения.
• Если оба являются ежедневными повторениями, найдите первый день, когда может возникнуть потенциальный конфликт. Пример: ежедневно, a: январь-июль, b: май-октябрь должен проверять только 1 мая на наличие временного конфликта. Если этого не произойдет, вам не нужно проверять наличие других конфликтов.
• Сделайте то же самое для разных созвездий (неделя-неделя, день-неделя, день-год).
• Не пишите day-week, а week-day - week_day(x,y) совпадает с day_week(y,x).
• Если вы не найдете подходящий метод, вам придется использовать метод, указанный выше, как запасной вариант.

Как вы можете видеть, последний намного больше работает - И время выполнения в худшем случае может быть таким же (поскольку он использует исходный алгоритм в качестве запасного варианта). Наихудший случай может быть вызван, например, «нерегулярным» повторением («каждый день через час»).

Answer 2

require 'set' #ruby standard lib
first_dates  = Set.new [1,2]  #where 1 and 2 are your sample dates, in an array
second_dates = Set.new [2,3]  #where 2 and 3 are your sample dates,
first_dates.intersection( second_dates ).empty?  #if empty, then no conflict

Answer 3

Предполагая, что повторения можно сортировать, вы можете отсортировать их по O (n * log (n)) и сравнить только с соседними событиями. Вот начало:

def conflicts?(other)
 conflicts = 0
 # Generate all recurrences and sort
 all_recurrences = recurrences + other.recurrences
 all_recurrences.sort!

 # Keep track of what immediate neighbors could be conflicting
 conflicting = []
 all_recurrences.each do |my_rec| 
     conflicting.each do |other_rec| do
       start, finish = other_rec.first, other_rec.last
       if my_rec.include?(start) || my_rec.include?(finish) then
          # TODO update conflicting array: add my_rec + other_rec if conflicting
          conflicts += 1
       else 
          # TODO remove other_rec if not conflicting
       end
     end
 end
 conflicts > 0
end

Answer 4

Несколько идей:

1. Используйте структуру данных, указывающую с календарной даты на список всех записей на эту дату. Затем загляните внутрь списка записей на эту дату для конфликтов.
2. Посмотрите на неделю дня - повторяющаяся запись в понедельник никогда не столкнется с записью в среду (в соответствии с первой идеей).
3. Использовать даты истечения срока - при проверке коллизий проверяйте только те даты, которые соответствуют записи, срок действия которой истекает раньше. Вы можете получить вдохновение от Сита Эратосфена .