一种非比较排序问题的排序算法？

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”之前执行，尽管其优先级较低。（希望上面的内容解释了我的问题，如果没有，请让我知道，我会进行编辑。）

我目前的想法是使用插入排序算法来管理排序过程。与许多其他常见的排序算法不同，插入排序算法逐个按顺序决定列表的顺序。因此，对于每个索引，我应该能够找到下一个最低优先级事件，其最早发生时间将得到满足。

我希望能够找到有关排序算法和数据结构的资源，以帮助我设计这种“排序”问题的好解决方案。我的实际问题比这个更复杂：分层排序、事件之间的可变缓冲区、多个非常数时间限制，因此获取更多信息或思路将更好。速度和空间并不重要，而对排序的准确性和代码的可维护性则很重要。

编辑：澄清（基于评论）

• 事件占用整个持续时间（即不允许事件重叠）
• 事件必须在其最早时间或之后发生，不能在其最早时间之前发生。
• 如果存在优先级较低的事件，则事件可以在其最早时间之后发生
• 事件不能被中断
• 列表中所有事件的持续时间总和有一个最大值。这在上面没有显示。（实际上，所有事件的持续时间将远大于时间列表的最大持续时间。）
• 不能有任何空隙。（没有任何漏洞可以尝试回填。）

编辑：答案

虽然David Nehme给出了我选择的答案，但我想指出，他的答案本质上是插入排序算法，而其他几个人提供了类似插入排序的答案。这对我来说证实了专门的插入排序可能是正确的方法。感谢所有人的答案。

- ARKBAN

---

问题：是否允许存在间隔？您是否想要填补它们？例如，您是否希望a、d、b、c作为解决方案，以确保b发生在t=6而不是t=7？ - Douglas Leeder

列表中所有事件的总持续时间有一个最大值。>> 这是什么意思。一些事件将无法安排吗？

- David Nehme

不能有任何间隙。（没有空洞可以尝试填补。）

你能保证这是可能的吗？例如，只有这两个事件。Event a = new Event { duration = 4.0, earliestTime = 0.0 };Event b = new Event {duration = 5.0, earliestTime = 6.0 }; - David Nehme

Answer 1

实际上，这不仅仅是一个排序问题。它是一个带有发布日期的单机调度问题。根据您尝试做什么，该问题可能是NP-Hard。例如，如果您试图最小化完成时间的加权和（权重与优先级成反比），则该问题被归类为NP-Hard问题。

1|ri;pmtn|Σ wiCi 

这个问题是NP难问题。有许多关于这个主题的论文，但可能不是你需要的。

在你的情况下，你永远不希望有间隙的解决方案，因此你可能只需要进行简单的离散事件模拟（O（n log（n））时间）。你需要将released_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
    }
}

一个问题是，你可能有一个优先级较低的任务，其发布时间恰好在一个短期、高优先级的任务之前，但它会生成一个没有间隔的日程安排（如果有可能生成没有间隔的日程安排）。

- David Nehme

---

“单机”是什么意思？与分布式计算类型问题相对应吗？ - ARKBAN

我的意思是这类似于在单个处理器上安排作业。我不是指您将编写用于解决此问题的代码。 - David Nehme

我怀疑你是对的。但这可能取决于权重是始终尽快开始高优先级（我的答案），还是始终避免间隙，这可能会导致不同的线性解决方案。 - Douglas Leeder

或许不是线性的，但至少是P。 - Douglas Leeder

你能推荐一些处理这种问题的资源吗？（其他人在帖子中发布了维基百科上的约束满足问题页面链接。） - ARKBAN

Answer 2

我认为：

1. 按优先级排序任务
2. 将任务适配到时间线上，从最早时间开始找到第一个可用的空隙大到足以容纳该任务的时间段。

将时间线转换成任务列表，并等待（等待空隙）。

问题：

1. 可以有空隙吗？
2. 任务可以分割吗？
3. 假设问题中给出的任务：是延迟 b 来完成 c 更好，还是做 d 以便 b 可以准时开始？

编辑：

我的问题的答案是：

1. 不行（如果没有要运行的内容，我猜我们可以有空隙）
2. 不行
3. 仍然不清楚，但我想例子表明运行 c 并延迟 b 更好。

在这种情况下，算法可能是：

1. 按优先级排序
2. 保持当前“时间”的计数器，从 t=0 开始
3. 搜索经过排序的列表，找到可以在 t 开始的最高优先级项目。
4. 将该项目添加到运行顺序中，并将其持续时间添加到 t。
5. 重复步骤 3 和 4，直到列表用尽。如果在 t 时没有可运行的任务，并且有待处理的任务，则将一个 1 秒的休眠任务添加到运行顺序中。

该算法的时间复杂度也是 O(n^2)。

- Douglas Leeder

---

在最坏情况下，时间复杂度将会是O(n^2)，对吧？ - Federico A. Ramponi

是的，我认为是O(n^2)。仍然比NP要好。 - Douglas Leeder

你的算法是我描述的插入排序技术。(很高兴看到有人想到了类似的想法。) - ARKBAN

Answer 3

换句话说，您想在制定两个约束条件（强约束：最早执行点，弱约束：优先级）的同时优化总运行时间？这被称为约束满足问题。有专门解决这种问题的求解器。

顺便提一下，jakber的解决方案不起作用。即使没有持续时间，以下示例显然也无法成功：

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

排序后的序列是 a、b，而期望的结果肯定是 b、a。

- Konrad Rudolph

---

谢谢，但是在我的解决方案中，第二个排序将按照开始时间进行排序，从而产生b，a。然而，如果事件不能同时发生，我的解决方案就会崩溃，所以我想你也有道理。 - jakber

Answer 4

我认为你应该对列表进行两次排序：首先按优先级排序，然后按最早时间排序，使用任何稳定的排序算法，例如插入排序。这样时间会逐渐增加，每个时间段内的事情都会按优先级排序。

除非你看到了我没有看到的东西，否则可以完全忽略每个事件的持续时间以进行排序。

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

- jakber

---

我不能忽略时间长度，因为随着时间的推移，当前时间增加，不同的事件可以添加到列表中。 - ARKBAN

那么事件不能同时发生吗？ - jakber

我猜不是，所以如果你有很多低优先级的任务可以从0开始，但有一个必须在t=4开始的高优先级任务，那么你只能先安排几个低优先级任务。 - Douglas Leeder

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;
}

请对此进行测试以验证任何假设，但我认为这正是我们正在寻找的。

- P Daddy

---

如果您有许多低优先级任务会延迟一个只能在稍后开始的高优先级任务，那么这种方法是行不通的。 - Douglas Leeder

它不能是基于直接比较的排序。如果您不知道Event1和Event2之前发生了什么，您无法决定Event1 < Event2还是Event2 < Event1。 - Federico A. Ramponi

我认为你们两位都在提到优先级较低的早期事件的持续时间延迟了优先级较高的后期事件的开始。我原本以为采用多线程的方法按时触发事件（不管已经运行了什么），但我会修改为假设采用单线程的方法。 - P Daddy

Answer 6

如果您有一组有限的优先级别，可以保留一组按时间排序的列表，每个级别一个。每当您需要下一个事件时，请按优先顺序检查每个列表的头，直到找到其开始时间已过去的事件为止。（在检查时跟踪最小开始时间 - 以防尚未准备好任何事件，您知道要等待哪个事件）

- AShelly

Answer 7

顺便提一下，在最一般的情况下可能没有解决方案（除非允许间隙，正如道格拉斯所指出的那样）。例如：

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 };

- Federico Ramponi

---

你是正确的。（在实际问题中，列表的开始时间将设置为4.0，并安排所有事件。） - ARKBAN

Answer 8

我不完全确定我理解你的问题的复杂性，但我的直觉告诉我你需要定义优先级和开始时间之间的关系。例如：

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

那么，我们是在时间 = 0 开始执行 b，还是等待一个时钟周期再开始执行 a ，因为它的优先级更高？假设有更多具有更高优先级和更长时间权衡的事件。我认为你需要一个类似于“如果下一个事件是 X 更高的优先级，并且（现在与最早时间之间的间隔）小于 Y 秒，则等待然后开始更高的优先级事件。否则开始低优先级事件（从而推迟高优先级事件）” 的规则。

- rmeador

---

你可以继续执行事件“b”，并将事件“a”推迟到“b”完成后再执行。 - ARKBAN

Answer 9

这里是一些类似于Douglas答案的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

- Federico Ramponi