جافا:عكس الفرز دون حفظ النظام

Question

التحديث:في الواقع الحل الوحيد المقبول لهذه المشكلة سيكون الفرز مجموعة تصاعدي ثم عكس ذلك.

السماح S يكون التسلسل التالي من الأحداث:

Event | Time
  A   | 0:00
  B   | 0:01
  C   | 0:01
  D   | 0:02

لدي بسيط للمقارنة لفرز S, والتي أنواع العناصر حسب الوقت القيمة.

public int compare(Event e1, Event e2) {

    // Reverse sorting. 
    // _sortOrder is set outside this method.
    if(SORT_DESCENDING.equals(_sortOrder))
        return e2.getTime() - e1.getTime(); /* time is long */

    return e1.getTime() - e2.getTime();
}

المشكلة هي:عندما ترتيب فرز تصاعدي ، S يتم فرز بشكل صحيح:A, B, C, D.

ولكن عندما استخدم عكس الفرز ، S يصبح D ، B ، C ، A:

Event | Time
  D   | 0:02
  B   | 0:01 /* B and C should be reversed */
  C   | 0:01
  A   | 0:00

يحدث هذا لأن الافتراضي خوارزمية الفرز تحافظ على الترتيب الأصلي لعناصر مع نفس الوقت القيمة.

لذا كيف يمكنني ترتيب عكسي دون حفظ الأصلي النظام ؟

ملاحظة: وأنا أعلم أنني يمكن فرز S تصاعدي كذلك ببساطة الرجوع ، ولكن للأسف هذا ليس خيارا في حالتي.

Answer 1

خوارزمية الفرز هو الصحيح:0.01 0.01.إلا إذا كان هناك شيء كنت لا تقول لنا.ولكن إذا كنت تريد بالضبط عكس ترتيب تصاعدي نوعا ما ثم فرزها في ترتيب تصاعدي استخدام مجموعات.عكس().هذا يعني:

List<SomeObject> list = ...;
Collections.sort(list, myComparator);
Collections.reverse(list);

والتي سوف تعطيك ما تريده بالضبط.

ولكن إذا كان عكس لا خيار لديك سوى اثنين من الخيارات على اليسار:

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

الآن قبل أن تقول لا يمكنك عكس (لماذا؟) ، دعني أسألك كيف كنت الفرز?إذا كنت تستخدم Collections.sort() النظر في التعليمات البرمجية المصدر (جافا 6u10):

public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
    i.next();
    i.set((T)a[j]);
}
}

لذلك نسخ مجموعة إلى مجموعة ، انواع أن مجموعة ومن ثم يستخدم لإعادة ترتيب المجموعة.

هل أنت متأكد من أنك لا تستطيع العكس ؟

Answer 2

ما الذي تستخدمه نوع ؟ تخميني هو انه شيء الذي يضمن انها مستقرة نوعا ما و كنت قد حصلت على اثنين من قيم متساوية بقدر المقارنة المعنية.

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

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

Answer 3

أنا في عداد المفقودين شيء, أو لا يمكنك فقط استخدام اسم الحدث (أو أيا كان أ ، ب ، ج ، د) النوع الثانوي المفتاح ؟ فقط تمديد المقارنة إلى شيء من هذا القبيل:

public int compare(Event e1, Event e2) {
    int cmp = e1.getTime() - e2.getTime(); // compare times
    if (cmp == 0)  // if times are equal, compare names instead
        cmp = e1.getName().compareTo(e2.getName());
    return SORT_DESCENDING.equals(_sortOrder)? -cmp : cmp;
}

Answer 4

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

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

Answer 5

طريقة أخرى ولكن لا حل مشكلتك :

List<SomeObject> list = ...;
Collections.sort(list, Collections.<SomeObject>reverseOrder());

Answer 6

لماذا 0:01 أصغر/أكبر من 0:01, أو لماذا يجب أن تكون مرتبة بطريقة خاصة جدا إذا كان كلاهما نفس الشيء ؟

أنت لا تبحث عن عكس النوع ، كنت تبحث عن عكس النوع, آسف.:)

Answer 7

ترتيب لا تبدو صحيحة ، فقط مقارنة الأسماء إذا e1.getTime() == e2.getTime().

Answer 8

اعتمادا على كيفية بسرعة المقارنة بين اثنين من العناصر مقارنة التحول لهم, هل يمكن أن مجرد القيام تنازلي مستقرة نوعا ما ، ثم عكس جميع المناطق من "المساواة" العناصر.