ruby - 检测重复事件中的冲突

Question

我正在编写一个需要检查冲突的日历应用程序 在经常性分录之间。每个 Entry 对象都有一个 recurrences() 方法 它返回一个范围数组——每个范围包含开始和结束 每个 future 事件的时间。

我需要检查新条目和现有条目之间的冲突。我是 通过检查新的 future 没有出现来做到这一点 条目与现有条目的 future 出现冲突:

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

recurrences() 默认返回开始时间之间的所有事件 和开始时间 + 1 年

问题是这种方法效率不高。仅比较两个条目，每个条目在 1 年内每天重复一次，导致 365 * 365 比较(在我的机器上需要 4 秒以上)。可能有任意数量的现有条目可以与新条目进行比较 我现在的方法没用。

我没有计算机科学或数学背景，但我一直 阅读有关算法的各种教科书，但我一直找不到 优化方法的方法。还有其他人有什么想法吗？

谢谢

戴夫

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:1 月至 7 月，b:5 月至 10 月 应该只检查 May,1st 是否存在时间冲突。如果没有发生任何冲突，则无需检查任何其他冲突。
• 对不同的星座(周-周、日-周、日-年)执行相同的操作。
• 避免编写 day-week 和 week-day - week_day(x,y) 与 day_week( y,x).
• 如果您没有找到匹配的方法，您将不得不使用上面给出的方法作为后备。

如您所见，后者的工作量要大得多——而且最坏情况下的执行时间可能相同(因为它使用原始算法作为回退)。例如，最坏的情况可能是由“不规则”复发(“每天一小时后”)引起的。