خوارزمية الفرز غير المقارنة على أساس نوع المشكلة ؟

Question

أنا حاليا تواجه صعوبة الفرز المشكلة.لدي مجموعة من الأحداث التي تحتاج إلى فرز ضد بعضها البعض (a مقارنة نوعا ما) و ضد مركزها النسبي في القائمة.

في أبسط شروط لدي قائمة من الأحداث أن يكون لكل أولوية (عدد صحيح) ، مدتها (ثانية) ، أقرب وقت حدوثها أن هذا الحدث يمكن أن تظهر في القائمة.أنا بحاجة إلى فرز الأحداث على أساس الأولوية ، ولكن أي حال من الأحوال لا يمكن أن تظهر في القائمة قبل أقرب وقت حدوثها.هنا مثال على (أمل) توضيح:

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

البند "ب" يجب أن يأتي آخر لأنه لا يجوز أن تبدأ حتى 6.0 ثانية في قائمة, لذلك هو المؤجلة و "ج" يحصل قبل "ب" على الرغم من أولوية أقل.(أمل أعلاه يوضح مشكلتي إن لم يكن اسمحوا لي أن أعرف وأنا سوف تحريره.)

بلدي الحالي هو فكرة استخدام نوع الإدراج لإدارة عملية الفرز.على عكس العديد من الآخرين المشتركة خوارزميات الفرز ، نوع الإدراج يقرر ترتيب قائمة في وقت واحد و في النظام.لذلك لكل مؤشر يجب أن تكون قادرة على العثور على التالي أقل أولوية الحدث الذي أقرب وقت حدوثها سوف يكون راضيا.

أنا على أمل أن تجد الموارد عن الفرز الخوارزميات وهياكل البيانات مساعدتي في تصميم حل جيد هذا "النوع" من المشكلة.مشكلتي الحقيقية هي في الواقع أكثر تعقيدا من ذلك:الهرمية الفرز متغير مخازن بين الأحداث متعددة غير ثابتة لضيق الوقت ، وبالتالي فإن المزيد من معلومات أو أفكار أفضل.السرعة و المساحة ليست حقا قلق.الدقة في الفرز و الصيانة من قانون هي مصدر قلق.

تحرير: إيضاحات (استنادا إلى التعليقات)

• الأحداث تستهلك كامل المدة (التي لا يوجد تداخل الأحداث سمحت)
• الأحداث يجب أن تحدث في أو بعد earliestTime, أنها لا يمكن أن تحدث قبل earliestTime.
• الأحداث يمكن أن تحدث في وقت لاحق من earliestTime إذا أولوية أقل الأحداث موجودة
• الأحداث لا تنقطع
• هناك حد أقصى مدة مجموع كل الأحداث التي يمكن أن تندرج في قائمة.هذا ليس هو مبين أعلاه.(في الواقع مدة كل الأحداث ستكون أكبر بكثير من الوقت قائمة أقصى مدة.)
• لا يمكن أن يكون هناك أي ثغرات.(لا توجد ثقوب في محاولة العودة التعبئة.)

تحرير: الجواب

بينما ديفيد نعمة أعطى الجواب المحدد ، أردت أن أشير إلى أن جوابه هو أحد أنواع الإدراج في القلب ، و عدة أشخاص آخرين المقدمة الإدراج نوع الإجابات.هذا يؤكد لي أنه متخصص في نوع الإدراج ربما هو الطريق للذهاب.شكرا لكم جميعا على إجاباتك.

Answer 1

هذا هو في الواقع أكثر من الفرز المشكلة.هذا هو واحد آلة جدولة مشكلة مع تواريخ الإصدار.اعتمادا على ما كنت تحاول القيام به ، قد تكون المشكلة NP-Hard.على سبيل المثال ، إذا كنت تحاول mimimize المرجح-مجموع الانتهاء مرات (الوزن عكسيا مع الأولويات) ، المشكلة تصنيف كما

1|ri;pmtn|Σ wiCi 

و هو NP-hard.هناك العديد من ورقات على هذا الموضوع, ولكن قد يكون أكثر من ما كنت بحاجة.

في حالتك أنت لا تريد حل مع الثغرات, لذلك ما قد تحتاج فقط إلى القيام به هو بسيط منفصلة الحدث المحاكاة ( 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
    }
}

مشكلة واحدة هي أن كنت قد يكون على ذات الأولوية المنخفضة العمل مع الافراج عن الوقت فقط قبل فترة قصيرة ، ذات الأولوية العالية الوظيفة ولكن سوف تنتج جدول زمني مع الممتلكات التي لا توجد ثغرات (إذا كان الجدول الزمني مع أي ثغرات ممكنة).

Answer 2

وبعبارة أخرى ، هل ترغب في تحسين الشاملة إدارة الوقت أثناء وضع اثنين من القيود (قوية:أقرب نقطة التنفيذ ، وضعف:الأولوية)?وهذا ما يسمى القيد رضا مشكلة.هناك خاصة يحلون لهذا النوع من المشكلة.

بالمناسبة, jakber الحل لا يعمل.حتى من دون مدة المثال التالي من الواضح فشل:

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

مرتبة تسلسل سيكون a, b حين أراد النتيجة بالتأكيد b, a.

Answer 3

أعتقد:

1. فرز المهام حسب الأولوية
2. تناسب المهام في خط الزمن ، مع اول فتحة بعد earliestTime أن لديها ثقب كبير بما فيه الكفاية للقيام بهذه المهمة.

تحويل خط الزمن إلى قائمة المهام, وينتظر (على الفجوات).

الأسئلة:

1. ثغرات سمحت ؟
2. يمكن أن المهام الانقسام ؟
3. بالنظر إلى المهام كما في السؤال:هل من الأفضل تأخير ب لاستكمال ج ، أو د إذا أن ب يمكن أن تبدأ في الوقت المناسب ؟

تحرير:

نظام التشغيل الإجابات على أسئلتي هي:

1. لا (العش - إذا كان هناك أي شيء لتشغيل أعتقد أننا يمكن أن يكون فجوة)
2. لا
3. لا تزال غير واضحة لكن أعتقد على سبيل المثال يشير إلى المدى c و تأخير ب.

في هذه الحالة الخوارزمية قد يكون:

1. الترتيب حسب الأولوية
2. الحفاظ على العداد الحالي 'الوقت' بدءا من t=0
3. البحث على الرغم من فرز القائمة على أولوية قصوى البند التي يمكن أن تبدأ في تي.
4. إضافة بند إلى تشغيل النظام ، إضافة مدته إلى t.
5. كرر 3 و 4 حتى يتم استنفاد القائمة.إذا كان هناك أي مهام runnable في ر ، وهناك المهام المتبقية في انتظار عصا 1-النوم الثانية المهمة في تشغيل النظام.

هذه الخوارزمية هو أيضا O(n^2).

Answer 4

أعتقد أن عليك أن فرز القائمة مرتين:أولا حسب الأولوية ومن ثم من قبل أقرب وقت ممكن ، وذلك باستخدام أي مستقرة خوارزمية الفرز ، على سبيل المثال نوع الإدراج.بهذه الطريقة سوف يكون الوقت زيادة و في كل مرة أن الأمور ستكون مرتبة حسب الأولوية.

إلا إذا كنت ترى شيئا لا يمكنك تجاهل تماما مدة كل حال لغرض النوع.

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

Answer 5

إذا كان لديك مجموعة محدودة من مستويات الأولوية ، يمكن أن نضع مجموعة من وقت فرز القوائم ، 1 لكل مستوى.كلما كنت في حاجة الحدث القادم ، تحقق رأس كل قائمة في ترتيب الأولويات حتى يمكنك العثور على واحد التي تبدأ من الوقت قد انقضى.(تتبع بداية الحد الأدنى من الوقت أثناء تسجيل الوصول في حالة أي حال من هو مستعد حتى الآن ، يمكنك أن تعرف أي واحد أن ننتظر)

Answer 6

تبدو مشكلة كنت أعاني من اليوم الذي تم الرد هنا.
على افتراض كنت تستخدم C#...

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

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

إذا هل يمكننا المضي قدما والبدء في b في الوقت = 0 ، أو هل علينا أن ننتظر لحظة ثم تبدأ a لأنها أعلى أولوية ؟ لنفترض أن هناك المزيد من الأحداث مع المزيد من أولويات زمنية أطول المفاضلات.أعتقد أنك بحاجة القاعدة على غرار "إذا كان الحدث القادم هو العاشر أولوية أعلى الهوة (بين الآن أقرب وقت) أقل من ذ ثانية انتظر ثم ابدأ أولوية أعلى الحدث.وإلا بدء أولوية منخفضة الحدث (وبالتالي دحر أولوية عالية واحدة)".

Answer 9

هنا بعض كود بايثون على غرار دوغلاس الجواب.أولا نحن الترتيب حسب الأولوية ، ثم نحن تناسب الجدول الزمني في اختيار نوع الأزياء:

#!/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 10

يبدو أنك فعلا لا تريد المقارنة على أساس النوع.النوع الرئيسي هو {earliestTime الأولوية} ، في هذا النظام.منذ المثال الخاص بك هو الزائفة 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;
}

هذا الاختبار ضد أي افتراضات لكن أعتقد أنه ما نبحث عنه.