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”之前出现，即使它的优先级较低。（希望上面能解释我的问题，如果没有让我知道，我会编辑它。）

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

我希望找到有关排序算法和数据结构的资源，以帮助我为这种“排序”问题设计一个好的解决方案。我真正的问题实际上比这更复杂：分层排序、事件之间的可变缓冲区、多个非常量时间限制，所以信息或想法越多越好。速度和空间并不是真正的问题。排序的准确性和代码的可维护性是一个问题。

编辑：澄清（基于评论）

事件消耗它们的整个持续时间（即不允许事件重叠）
事件必须在其最早时间或之后发生，它们不能在其最早时间之前发生。
如果存在较低优先级的事件，事件可能会晚于它们的 earlyTime
事件不能被打断
最长持续时间是可以放入列表中的所有事件的总和。这在上面没有显示。（实际上所有事件的持续时间将远远大于时间列表的最大持续时间。）
不能有任何空隙。（没有孔可以尝试回填。）

编辑：回答

虽然 David Nehme 给出了我选择的答案，但我想指出他的答案本质上是插入排序，其他几个人提供了插入排序类型的答案。这向我证实了专门的插入排序可能是要走的路。感谢大家的回答。

score 11 · Accepted Answer

这实际上不仅仅是一个排序问题。这是一个发布日期的单机调度问题。根据您要执行的操作，问题可能是 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
    }
}

一个问题是，您可能有一个低优先级的作业，其发布时间刚好在一个短的、高优先级的作业之前，但它会生成一个具有没有间隙的属性的日程表（如果没有间隔的日程表是可能的） .

score 3 · Accepted Answer

我认为：

按优先级排序任务
将任务放入时间线中，在其最早时间之后占用第一个可用时间段，该时间段有一个足够大的孔来完成任务。

将时间线转换为任务列表，然后等待（对于间隙）。

问题：

允许间隙吗？
任务可以拆分吗？
鉴于问题中的任务：延迟 b 完成 c 更好，还是执行 d 以便 b 可以按时开始？

编辑：

我的问题的答案是：

不（ish - 如果没有什么可运行的，我想我们可能会有差距）
不
仍然不清楚，但我猜这个例子建议运行 c 和延迟 b。

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

按优先级排序
为当前的“时间”保留一个计数器，从 t=0 开始
在排序列表中搜索可以在 t 开始的最高优先级项目。
将项目添加到运行订单，并将其持续时间添加到 t。
重复 3&4 直到列表用完。如果在 t 时刻没有可运行的任务，并且还有待处理的任务，则在运行顺序中粘贴一个 1 秒的睡眠任务。

这个算法也是O(n^2)。

score 2 · Accepted Answer

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

顺便说一句，jakber 的解决方案不起作用。即使没有持续时间，以下示例显然也会失败：

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

排序后的序列是a，b而想要的结果肯定是b，a。

score 0 · Accepted Answer

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

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

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

score 0 · Accepted Answer

听起来您确实确实想要基于比较的排序。您的排序键是 {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;
}

针对任何假设进行测试，但我认为这是我们正在寻找的。

score 0 · Accepted Answer

如果您有一组有限的优先级，您可以保留一组按时间排序的列表，每个级别 1 个。每当您需要下一个事件时，请按优先级顺序检查每个列表的头部，直到找到一个开始时间已过的事件。（在您检查时跟踪最短开始时间 - 如果还没有活动准备好，您知道要等待哪个活动）

score 0 · Accepted Answer

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

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

score 0 · Accepted Answer

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

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时间 = 0 开始，还是等待一个滴答声然后开始a，因为它的优先级更高？假设有更多的事件具有更多的优先级和更长的时间权衡。我认为你需要一个规则，“如果下一个事件的优先级更高，并且间隔（现在和最早的时间之间）小于 Y 秒，等待然后启动更高优先级的事件。否则启动低优先级事件（从而推回高优先级的事件）”。

score 0 · Accepted Answer

这是 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

c# - 非基于比较的排序问题的排序算法？

9 回答 9

Related

Reference