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

recurrences() のデフォルトでは、開始時刻から開始時刻 + 1 年までのすべての発生を返します

問題は、この方法があまり効率的でないことです。それぞれが 1 年以上毎日繰り返される 2 つのエントリだけを比較すると、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

ただし、これによりアルゴリズムの平均パフォーマンスが向上するわけではなく、競合が発生した場合に比較が 1 回だけ行われます。あなたが得た唯一のオプションは、「単純な」衝突を早期に検出することです。以下のようなので

  • 繰り返しの種類 (毎週、毎日、毎月) を繰り返しオブジェクトに格納します。
  • 両方が毎日の繰り返しである場合は、競合の可能性がある最初の日を見つけます。例:毎日、a: 1 月から 7 月、b: 5 月から 10 月は、時間の競合について 5 月 1 日のみをチェックする必要があります。競合が発生しない場合は、他の競合をチェックする必要はありません。
  • 異なる星座 (週 - 週、日 - 週、日 - 年) に対して同じことを行います。
  • day-weekとweek-day-week_day(x,y)は と同じですday_week(y,x)。
  • 一致する方法が見つからない場合は、上記の方法をフォールバックとして使用する必要があります。

ご覧のとおり、後者の方がはるかに多くの作業が必要です。また、最悪の場合の実行時間は同じになる可能性があります (元のアルゴリズムをフォールバックとして使用するため)。最悪の場合は、たとえば、「不規則な」繰り返し (「毎日 1 時間後」) が原因である可能性があります。

于 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 に答える