2

我正在编写一个日历应用程序，它需要检查重复条目之间的冲突。每个Entry 对象都有一个recurrences() 方法，该方法返回一个范围数组——每个范围包含每个未来事件的开始和结束时间。

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

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

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

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

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

谢谢

戴夫

4

4 回答 4

2

首先，您可以通过引起早期函数返回来改善这一点：

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)。
  • 如果找不到匹配的方法，则必须使用上面给出的方法作为后备。

正如您所看到的，后者的工作量更大——并且最坏情况下的执行时间可能相同（因为它使用原始算法作为后备）。例如，最坏的情况可能是由“不规则”重复（“每天一小时后”）引起的。

于 2009-04-12T12:34:22.003 回答
1 
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
于 2012-06-19T19:45:05.007 回答
0

假设重复是可排序的，您可以在 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
于 2009-04-12T13:28:50.217 回答
0

一些想法：

  1. 使用从日历日期指向该日期所有条目的列表的数据结构。然后查看该日期的条目列表中是否存在冲突。
  2. 查看星期几 - 星期一的重复条目永远不会与星期三的条目发生冲突（包含在第一个想法中）。
  3. 使用过期日期 - 检查冲突时，仅检查适合较早过期条目的日期。您可能会从埃拉托色尼筛法中获得一些灵感。
于 2009-04-12T12:36:52.730 回答