c# - 非比較ベースのソート問題のソートアルゴリズム?

Question

私は現在、難しいソートの問題に直面しています。相互にソートする必要があるイベントのコレクション (比較ソート) と、リスト内の相対位置に対してソートする必要があります。

簡単に言えば、優先度 (整数)、期間 (秒)、およびイベントがリストに表示される最も早い発生時刻を持つイベントのリストがあります。優先度に基づいてイベントを並べ替える必要がありますが、最も早い発生時間より前にリストに表示されるイベントはありません。（うまくいけば）より明確にするための例を次に示します。

// Psuedo C# code
class Event { int priority; double duration; double earliestTime ; }

void Example()
{
    Event a = new Event { priority = 1, duration = 4.0, earliestTime = 0.0 };
    Event b = new Event { priority = 2, duration = 5.0, earliestTime = 6.0 };
    Event c = new Event { priority = 3, duration = 3.0, earliestTime = 0.0 };
    Event d = new Event { priority = 4, duration = 2.0, earliestTime = 0.0 };

    // assume list starts at 0.0 seconds
    List<Event> results = Sort( new List<Event> { a, b, c, d } );

    assert( results[ 0 ] == a ); // 4.0 seconds elapsed
    assert( results[ 1 ] == c ); // 7.0 seconds elapsed
    assert( results[ 2 ] == b ); // 12.0 seconds elapsed
    assert( results[ 3 ] == d ); // 14.0 seconds elapsed
}

アイテム "b" は、リストの 6.0 秒まで開始できないため、最後に来る必要があります。したがって、アイテムは延期され、"c" は優先度が低くても "b" の前に移動します。（うまくいけば、上記で私の問題が説明されます。そうでない場合は、お知らせください。編集します。）

私の現在の考えは、挿入ソートを使用してソートプロセスを管理することです。他の一般的な並べ替えアルゴリズムの多くとは異なり、挿入並べ替えはリストの順序を一度に 1 つずつ順番に決定します。したがって、インデックスごとに、最も早い発生時間が満たされる次に優先度の低いイベントを見つけることができるはずです。

この「並べ替え」の問題に対する優れたソリューションを設計するのに役立つ、並べ替えアルゴリズムとデータ構造に関するリソースを見つけたいと思っています。私の本当の問題は実際にはこれよりも複雑です: 階層的な並べ替え、イベント間の可変バッファ、複数の一定でない時間の制約など、情報やアイデアが多ければ多いほど良いのです。速度とスペースは実際には問題ではありません。ソートの精度とコードの保守性が懸念されます。

編集：説明（コメントに基づく）

• イベントはその期間全体を消費します (つまり、イベントのオーバーラップは許可されません)。
• イベントは、earlylyTime 以降に発生する必要があり、earlylyTime より前に発生することはできません。
• 優先度の低いイベントが存在する場合、イベントは EarlyTime よりも遅く発生する可能性があります
• イベントは中断できません
• リストに収まるすべてのイベントの合計に最大期間があります。これは上には示されていません。(実際には、すべてのイベントの期間は、タイム リストの最大期間よりもはるかに長くなります。)
• ギャップがあってはなりません。(試して埋め戻す穴はありません。)

編集：答え

David Nehme が私が選択した回答を提供しましたが、彼の回答は本質的に挿入ソートであり、他の何人かが挿入ソート タイプの回答を提供したことを指摘したいと思います。これは、特殊な挿入ソートがおそらく進むべき道であることを私に確認させます。皆様、ご回答ありがとうございます。

Answer 1

これは、実際にはソートの問題以上のものです。これは、リリース日に関する単一マシンのスケジューリングの問題です。やろうとしていることに応じて、問題は NP-Hard である可能性があります。たとえば、完了時間の加重合計を最小化しようとしている場合 (加重は優先度に反比例します)、問題は次のように分類されます。

1|ri;pmtn|Σ wiCi 

そしてNP困難です。このトピックに関する論文は数多くありますが、必要以上のものかもしれません。

あなたの場合、ギャップのあるソリューションは決して必要ないため、単純な離散イベント シミュレーション ( O(n log(n)) ) 時間だけが必要になる場合があります。release_jobs をプライオリティ キューとして保存する必要があります。

unreleased_jobs = jobs  // sorted list of jobs, by release date
released_jobs = {}      // priority queue of jobs, by priority
scheduled_jobs = {}     // simple list
while (!unreleased_jobs.empty() || !released_jobs.empty()) {

    while (unreleased_jobs.top().earliestTime  <= t) {
        released_jobs.push(unreleased_jobs.pop())
    }
    if (!released_jobs.empty()) {
       next_job = released_jobs.pop();
       scheduled_jobs.push_back(next_job)
       t = t + next_job.duration
    } else {
       // we have a gap
       t = unreleased_jobs.top().earliestTime
    }
}

問題の 1 つは、優先度の低い短いジョブのリリース時間が、優先度の高い短いジョブの直前にある可能性があることですが、ギャップがないという特性を持つスケジュールが生成されます (ギャップのないスケジュールが可能である場合)。 .

Answer 2

おもう：

1. タスクを優先順位で並べ替える
2. タスクに十分な大きさの穴がある、earlyTime の後に最初に使用可能なスロットを取得して、タスクをタイムラインに合わせます。

タイムラインをタスクのリストに変換し、(ギャップを) 待ちます。

質問:

1. ギャップは許されますか？
2. タスクは分割できますか?
3. 質問のようなタスクを考えると、b を遅らせて c を完了するのと、b が時間通りに開始できるように d を実行するのとのどちらがよいでしょうか?

編集：

私の質問に対する答えは次のとおりです。

1. いいえ（そうです-実行するものが何もない場合、ギャップが生じる可能性があると思います）
2. いいえ
3. まだ明確ではありませんが、この例では、c を実行して b を遅らせることが示唆されていると思います。

この場合、アルゴリズムは次のようになります。

1. 優先順位で並べ替え
2. t=0 から始まる現在の「時間」のカウンターを保持する
3. ソートされたリストを検索して、t で開始できる最も優先度の高い項目を探します。
4. アイテムを実行中の順序に追加し、その期間を t に追加します。
5. リストが尽きるまで3と4を繰り返します。t で実行可能なタスクがなく、保留中のタスクが残っている場合は、実行順序に 1 秒のスリープ タスクを固定します。

このアルゴリズムも O(n^2) です。

Answer 3

つまり、2 つの制約 (強い: 実行の最も早い時点、弱い: 優先度) を策定しながら、全体の実行時間を最適化したいですか? これは、制約充足問題と呼ばれます。この種の問題には特別なソルバーがあります。

ちなみに、jakber のソリューションは機能しません。期間がなくても、次の例は明らかに失敗します。

event a (priority = 1, start = 5)
event b (priority = 2, start = 0)

ソートされたシーケンスは になりますがa、必要なb結果は確かbにaです。

Answer 4

あなたの問題の複雑さを完全に理解しているとは言えませんが、直感的に、優先度と開始時間の関係を定義する必要があることがわかります。例は次のとおりです。

Event a = new Event { priority = 1, duration = 4.0, earliestTime = 1.0 };
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 0.0 };

では、先に進んbで time = 0 から開始するか、それともティックを待ってから開始するaか (優先度が高いため) を選択します。より多くの優先度とより長い時間のトレードオフを持つイベントがさらにあったとします。「次のイベントの優先度が X 高く、(現在と最も早い時間の間の) ギャップが Y 秒未満の場合、待機してから優先度の高いイベントを開始する。それ以外の場合は、優先度の低いイベントを開始する」という行に沿ったルールが必要だと思います。イベント（したがって、優先度の高いイベントを押し戻す）」.

Answer 5

実際に比較ベースの並べ替えが必要なようです。ソートキーは {earliestTime, priority} の順です。あなたの例は疑似 C# であるため、疑似 C# ソリューションを提供します。

class Event : IComparable<Event>, IComparable{
    int    priority;
    double duration;
    double earliestTime;

    public int CompareTo(Event other){
        if(other == null)
            return 1; /* define: non-null > null */

        int cmp = earliestTime.CompareTo(other.earliestTime);
        if(cmp != 0)
            return cmp;

        /* earliestTimes were equal, so move on to next comparison */
        return priority.CompareTo(other.priority);
    }

   int IComparable.CompareTo(object other){ /* for compatibility with non-generic collections */
       if(other == null)
            return 1; /* define: non-null > null */

       Event e_other = other as Event;
       if(e_other == null) /* must have been some other type */
           throw new ArgumentException("Must be an Event", "other");

       return CompareTo(e_other); /* forward to strongly-typed implementation */
   }
}

これで、アサートが期待するとおりにリストがソートされます。

編集：

私の最初の推測では、イベントはリストから選択され、別のスレッドに渡され、キュー マネージャーは時間どおりに次のイベントを起動できるようになるというものでしたが、受け取ったコメントから、おそらくシングル スレッドでありながら、優先度の高いイベントをできるだけ開始時刻近くで開始できるようにすることがより望ましいものでした。その場合、CompareTo関数は次のように変更する必要があります。

public int CompareTo(Event other){
    if(other == null)
        return 1; /* define: non-null > null */

    int cmp = priority.CompareTo(other.priority);

    if(cmp == 0)
        /*
         * calculate and compare the time each event will be late
         * if the other one were to start first.  This time may be
         * negative if starting one will not make the other one late
         */
        return (earliestTime + duration - other.earliestTime).CompareTo(
            other.earliestTime + other.duration - earliestTime);

    /*
     * they're different priorities. if the lower-priority event
     * (presume that greater priority index means lower priority,
     * e.g. priority 4 is "lower" priority than priority 1), would
     * would make the higher-priority event late, then order the
     * higher-priority one first.  Otherwise, just order them by
     * earliestTime.
     */
    if(cmp < 0){/* this one is higher priority */
        if(earliestTime <= other.earliestTime)
            /* this one must start first */
            return -1;

        if(other.earliestTime + other.duration <= earliestTime)
            /* the lower-priority event would not make this one late */
            return 1;

        return -1;
    }

    /* this one is lower priority */
    if(other.earliestTime <= earliestTime)
        /* the other one must start first */
        return 1;

    if(earliestTime + duration <= other.earliestTime)
        /* this event will not make the higher-priority one late */
        return -1;

    return 1;
}

仮定に対してこれをテストしますが、それが私たちが探しているものだと思います.

Answer 6

優先度レベルのセットが限られている場合は、レベルごとに 1 つずつ、時間順にソートされた一連のリストを保持できます。次のイベントが必要なときはいつでも、開始時刻が過ぎているイベントが見つかるまで、各リストの先頭を優先順に調べます。(確認中は最低開始時間を記録しておいてください - イベントの準備がまだできていない場合は、どれを待つべきかがわかります)

Answer 7

ダグラスの回答に沿ったPythonコードを次に示します。最初に優先順位で並べ替え、次に選択並べ替え方式でタイムラインを適合させます。

#!/usr/bin/env python
MIN_PRIORITY = 100

class Event(object):
    def __init__(self, name, priority, duration, earliestTime):
        self.name = name
        self.priority = priority
        self.duration = duration
        self.earliestTime = earliestTime
    def __str__(self):
        return "%-10s:  P %3d  D %3.1f  T %3.1f" % (self.name, self.priority, self.duration, self.earliestTime)

def sortEvents(_events):
    def comparePriority(event1, event2):
        if event1.priority < event2.priority: return -1
        if event1.priority > event2.priority: return 1
        return 0

    # Get a copy of the events and sort by priority
    events = [e for e in _events]
    events.sort(cmp=comparePriority)

    # Select one event at a time, checking for compatibility with elapsed time
    elapsedTime = 0.0
    sortedEvents = []
    while events:
        minGap = events[0].earliestTime - elapsedTime
        for e in events:
            currentGap = e.earliestTime - elapsedTime
            if currentGap < minGap:
                minGap = currentGap
            if currentGap <= 0.0:
                sortedEvents.append(e)
                elapsedTime += e.duration
                events.remove(e)
                break

        # If none of the events fits, add a suitable gap
        if minGap > 0:
            sortedEvents.append( Event("gap", MIN_PRIORITY, minGap, elapsedTime) )
            elapsedTime += minGap
    return sortedEvents

if __name__ == "__main__":
    #e1 = Event("event1", 1, 1.0, 4.0)
    #e2 = Event("event2", 2, 1.0, 6.0)
    #e3 = Event("event3", 3, 1.0, 8.0)
    #e4 = Event("event4", 4, 1.0, 10.0)

    e1 = Event("event1", 1, 4.0, 0.0)
    e2 = Event("event2", 2, 5.0, 6.0)
    e3 = Event("event3", 3, 3.0, 0.0)
    e4 = Event("event4", 4, 2.0, 0.0)

    events = [e1, e2, e3, e4]

    print "Before:"
    for event in events: print event
    sortedEvents = sortEvents(events)
    print "\nAfter:"
    for event in sortedEvents: print event

Answer 8

リストを 2 回ソートする必要があると思います。最初は優先順位で、次に挿入ソートなどの安定したソート アルゴリズムを使用して最も早い時間でソートします。そうすれば時間が増え、そのたびに物事は優先度順にソートされます。

表示されないものがない限り、ソートの目的で各イベントの期間を完全に無視できます。

http://en.wikipedia.org/wiki/Category:Stable_sorts

Answer 9

ちなみに、最も一般的なケースでは、解決策がない場合があります (ダグラスが指摘したように、ギャップが許容されない限り)。例えば：

Event a = new Event { priority = 1, duration = 1.0, earliestTime = 4.0 };
Event b = new Event { priority = 2, duration = 1.0, earliestTime = 4.0 };
Event c = new Event { priority = 3, duration = 1.0, earliestTime = 4.0 };
Event d = new Event { priority = 4, duration = 1.0, earliestTime = 4.0 };