Алгоритм сортировки для задачи сортировки, не основанной на сравнении?

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", хотя его приоритет ниже. (Надеюсь, вышеизложенное объясняет мою проблему, если нет, дайте мне знать, и я отредактирую ее.)

Моя текущая идея заключается в использовании сортировки вставок для управления процессом сортировки. В отличие от многих других распространенных алгоритмов сортировки, сортировка вставкой определяет порядок списка по одному и по порядку. Таким образом, для каждого индекса я должен быть в состоянии найти следующее событие с самым низким приоритетом, чье самое раннее время возникновения будет удовлетворено.

Я надеюсь найти ресурсы по алгоритмам сортировки и структурам данных, которые помогут мне найти хорошее решение для такого рода проблем. Моя настоящая проблема на самом деле более сложная, чем эта: иерархическая сортировка, переменные буферы между событиями, множество неконстантных временных ограничений, поэтому чем больше информации или идей, тем лучше. Скорость и пространство на самом деле не проблема. Точность сортировки и удобство сопровождения кода являются проблемой.

Редактировать: Разъяснения (по комментариям)

• События потребляют всю свою продолжительность (т. Е. Перекрытие событий не допускается)
• События должны происходить в или после их самого раннего времени, они не могут происходить раньше их самого раннего времени.
• События могут произойти позже их самого раннего времени, если существуют события с более низким приоритетом
• События не могут быть прерваны
• Максимальная продолжительность - сумма всех событий, которые могут поместиться в списке. Это не показано выше. (На самом деле продолжительность всех событий будет намного больше, чем максимальная продолжительность временного списка.)
• Пробелов не должно быть. (Нет отверстий, чтобы попытаться заполнить их обратно.)

Редактировать: Ответ

В то время как Дэвид Нехм дал ответ, который я выбрал, я хотел отметить, что его ответ - это вставка в глубине души, и несколько других людей предоставили вставки для сортировки ответов. Это подтверждает для меня, что специализированная сортировка вставок - это, вероятно, путь. Спасибо всем вам за ваши ответы.

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

Одна из проблем заключается в том, что у вас может быть задание с низким приоритетом и временем выпуска незадолго до короткого задания с высоким приоритетом, но оно создаст расписание со свойством отсутствия пробелов (если расписание без пробелов возможно).

Answer 2

Я думаю:

1. Сортировка задач по приоритету
2. Поместите задачи в график времени, заняв первое доступное место после их самого раннего времени, в котором достаточно большое отверстие для задачи.

Преобразование временной шкалы в список задач и ожидание (для пробелов).

Вопросы:

1. Разрешены ли пропуски?
2. Можно ли разделить задачи?
3. Учитывая задачи, как в вопросе: лучше ли отложить b, чтобы завершить c, или сделать d, чтобы b мог начать вовремя?

Edit:

Ответы на мои вопросы:

1. Нет (иш - если нечего бежать, я думаю, у нас может быть разрыв)
2. Нет
3. Все еще не ясно, но я предполагаю, что пример предлагает выполнить c и задержку b.

В этом случае алгоритм может быть:

1. Сортировка по приоритету
2. Сохранить счетчик текущего времени, начиная с t = 0
3. Поиск в отсортированном списке для элемента с наивысшим приоритетом, который может быть начат в момент времени t.
4. Добавьте элемент в порядок выполнения и добавьте его длительность к т.
5. Повторяйте 3 и 4, пока список не будет исчерпан. Если нет задач, выполняемых в момент времени t, и есть задачи, ожидающие выполнения, установите 1-секундную задачу ожидания в порядке выполнения.

Этот алгоритм также O (n ^ 2).

Answer 3

Другими словами, вы хотите оптимизировать общее время выполнения, формулируя два ограничения (сильное: самая ранняя точка выполнения, слабое: приоритет)? Это называется проблемой удовлетворения ограничений . Для решения этой проблемы существуют специальные решения.

Кстати, решение Якбера не работает. Даже без продолжительности следующий пример явно не работает:

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

Отсортированная последовательность будет a, b, в то время как желаемый результат, безусловно, b, a.

Answer 4

Вот некоторый код 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 5

Я не совсем уверен, что понимаю все сложности вашей проблемы, но мой инстинкт подсказывает мне, что вам нужно определить связь между приоритетом и временем начала. Пример будет:

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, потому что это более высокий приоритет? Предположим, было больше событий с большим количеством приоритетов и более длительными компромиссами. Я думаю, что вам нужно правило в духе "если следующее событие имеет более высокий приоритет X, а разрыв (между настоящим моментом и самым ранним временем) меньше Y секунд, подождите и затем запустите событие с более высоким приоритетом. В противном случае запустите низкий приоритет событие (таким образом отталкивая назад приоритетное) ".

Answer 6

Между прочим, в самом общем случае может не быть решения (если пробелы не разрешены, как указал Дуглас). Например:

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

Answer 7

Звучит как проблема, с которой я столкнулся на днях, на что ответил здесь .
Предполагая, что вы используете C # ...

Answer 8

Если у вас ограниченный набор уровней приоритета, вы можете сохранить набор отсортированных по времени списков, по 1 для каждого уровня. Всякий раз, когда вам нужно следующее событие, проверяйте заголовок каждого списка в порядке приоритета, пока не найдете тот, чье время начала прошло. (Следите за минимальным временем запуска, пока вы проверяете - если событие еще не готово, вы знаете, какое из них ждать)

Answer 9

Похоже, вы действительно хотите сортировку на основе сравнения. Ваш ключ сортировки - {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 */
   }
}

Теперь ваш список будет отсортирован так, как ожидают ваши утверждения.

EDIT

Первоначально я предполагал, что события будут выбраны из списка и переданы отдельному потоку, чтобы администратор очередей мог запустить следующее событие вовремя, но из полученных мной комментариев я понял, что, возможно, подход, который был однопоточным, но все же позволял запускать события с более высоким приоритетом как можно ближе к их времени начала, было более желательным. В этом случае функция 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 10

Я думаю, вам следует отсортировать список дважды: сначала по приоритету, а затем по самому раннему времени, используя любой алгоритм сортировки stable , например сортировку вставкой. Таким образом, время будет увеличиваться, и каждый раз все будет отсортировано по приоритету.

Если вы не видите что-то, что я не могу, вы можете полностью игнорировать продолжительность каждого события с целью сортировки.

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