4

00:00 ～ 00:59 の期間に一連のイベントをスケジュールしたいとします。私は完全な分 (00:01、決して 00:01:30) でそれらをスケジュールします。

その期間内にできるだけ間隔を空けて配置したいのですが、その時間内に合計でいくつのイベントが発生するかは前もってわかりません。今日は 1 つのイベントをスケジュールし、明日はさらに 2 つのイベントをスケジュールします。

私の頭の中には明白なアルゴリズムがあり、それを実装する力ずくの方法を考えることができますが、誰かがもっと良い方法を知っていると確信しています。Ruby か、Ruby に翻訳できるものが望ましいのですが、入手できるものを使用します。

したがって、頭の中で考えることができるアルゴリズムは次のとおりです。

イベント 1 はちょうど 00:00 に終了します。

イベント 2 は 00:30 に終了します。これは、その時間が既存のイベントから最も離れているためです。

イベント 3 は、00:15 または 00:45 に終了する可能性があります。最初の 00:15 を選択します。

その後、イベント 4 は 00:45 に終了します。

イベント 5 は 00:08 頃に終了します (00:07:30 から切り上げ)。

等々。

したがって、取得した分の各ペア (たとえば、00:00–00:15、00:15–00:30、00:30–00:00) を見て、最大の範囲 (00:30–00:00) を選択できます。 )、それを 2 で割って丸めます。

しかし、私はそれがもっとうまくできると確信しています。共有してください！

4

4 に答える 4

2

スケジュールできるイベントは最大で60しかないため、静的テーブルを使用する価値があると思います（アルゴリズムを考えてテストする場合と比較して）。つまり、時間内にイベントをレイアウトするのは非常に簡単な作業です。しかし、それをうまく行う方法をコンピューターに教えるのはそれほど簡単ではありません。

したがって、私が提案するのは、次のイベントを配置する時間の静的な値を使用してテーブルを定義することです。次のようになります。

00:00, 01:00, 00:30, 00:15, 00:45...
于 2012-08-01T13:59:36.563 に答える
2

イベントのスケジュールにビット反転を使用できます。イベントの連続番号のバイナリ表現を取得し、そのビットを逆にして、結果を特定の範囲 (0..59 分) にスケーリングするだけです。

別の方法は、ビット反転ワードを順番に生成することです (0000、1000、0100、1100、...)。

これにより、最大 32 個のイベントを簡単に配信できます。さらにイベントが必要な場合は、結果をスケーリングした後、結果の分が既に占有されているかどうかを確認し、そうであれば、次の単語を生成してスケーリングします。

Ruby での例を次に示します。

class Scheduler
  def initialize
    @word = 0
  end

  def next_slot
    bit = 32
    while  (((@word ^= bit) & bit) == 0) do
      bit >>= 1;
    end
  end

  def schedule
    (@word * 60) / 64
  end
end


scheduler = Scheduler.new

20.times do
  p scheduler.schedule
  scheduler.next_slot
end

ビット反転ワードを順番に生成する方法は、" Matters Computational " の 1.14.3 章から借用しています。

アップデート：

0..63 から 0..59 へのスケーリングにより、このアルゴリズムは 0、15、30、および 45 の直後に最小のスロットを作成する傾向があります。問題は、常にこれらの (最小の) スロットから間隔を埋め始めることです。最大のスロットから充填を開始する方が自然です。このため、アルゴリズムは完全ではありません。追加の問題は、「すでに占有されている分」を確認する必要があることです。

幸いなことに、小さな修正でこれらの問題はすべて解消されます。変えるだけ

while  (((@word ^= bit) & bit) == 0) do

に

while  (((@word ^= bit) & bit) != 0) do

63で初期化@wordします (または 0 で初期化を続けますが、最初のイベントを取得するために 1 回繰り返します)。この修正により、反転ワードが 63 から 0 に減少し、常にイベントが可能な限り最大のスロットに分散され、最初の 60 回の反復で「競合する」イベントが許可されなくなります。

その他のアルゴリズム

前のアプローチは単純ですが、(いつでも) 最大の空のスロットが最小のスロットの 2 倍以下であることを保証するだけです。イベントをできるだけ離して配置したいので、フィボナッチ数または黄金比に基づくアルゴリズムが優先される場合があります。

  1. 初期間隔 (0..59) を優先度キュー (最大ヒープ、優先度 = 間隔サイズ) に配置します。
  2. イベントをスケジュールするには、優先キューをポップし、結果の間隔を黄金比 (1.618) で分割し、このイベントの時間として分割ポイントを使用し、2 つの結果の間隔を優先キューに戻します。

これにより、最大の空のスロットが最小のスロットの (約) 1.618 倍を超えないことが保証されます。小さいスロットの場合、近似は悪化し、サイズは 2:1 として関連付けられます。

スケジュールの変更間で優先キューを保持するのが不便な場合は、事前に 60 の可能なイベントの配列を準備し、新しいイベントが必要になるたびにこの配列から次の値を抽出できます。

于 2012-08-01T14:13:53.073 に答える
1

イベントのスケジュールを変更することはできず、到着するイベントの数が事前にわからないため、あなた自身の提案（01:00を使用するというRomanのメモ付き）が最適だと思います。

ただし、最大で到着するイベントの数について何らかの見積もりがある場合は、おそらくそれを最適化できます。たとえば、最大7つのイベントを見積もっているとすると、60 / (n - 1)= 10分のスロットを準備し、次のようにイベントをスケジュールできます。

  • 00:00
  • 01:00
  • 00:30
  • 00:10
  • 00:40
  • 00:20
  • 00:50//10分間隔

最後のいくつかのイベントが到着しない可能性があるため、00：50が使用される可能性は低いことに注意してください。

これは、特に最悪のシナリオでは、すべてのスロットが使用された場合に、非推定ベースのアルゴリズムよりも公平になります。

  • 00:00
  • 01:00
  • 00:30
  • 00:15
  • 00:45
  • 00:07
  • 00:37//7分間隔
于 2012-08-01T13:56:48.893 に答える
0

ソリューションの Ruby 実装を作成しました。60 を超えるイベントはすべて分 0 に積み重なるというエッジ ケースがあります。これは、時間のすべての空きスペースが同じサイズになり、最初の空きスペースが優先されるためです。

60 を超えるイベントの処理方法を指定していませんでしたし、特に気にする必要もありませんが、気になる場合は、ランダム化またはラウンド ロビンによってそのエッジ ケースを解決できると思います。

each_cons(2) バイグラムを取得します。残りはおそらく簡単です。

class Scheduler
  def initialize
    @scheduled_minutes = []
  end

  def next_slot
    if @scheduled_minutes.empty?
      slot = 0
    else
      circle = @scheduled_minutes + [@scheduled_minutes.first + 60]
      slot = 0
      largest_known_distance = 0

      circle.each_cons(2) do |(from, unto)|
        distance = (from - unto).abs
        if distance > largest_known_distance
          largest_known_distance = distance
          slot = (from + distance/2) % 60
        end
      end
    end

    @scheduled_minutes << slot
    @scheduled_minutes.sort!
    slot
  end

  def schedule
    @scheduled_minutes
  end
end


scheduler = Scheduler.new

20.times do
  scheduler.next_slot
  p scheduler.schedule
end
于 2012-08-01T14:08:45.637 に答える