تنفيذ القائمة التي تحافظ على الطلب

Question

هل يوجد List التنفيذ في Java الذي يحافظ على النظام بناءً على ما تم توفيره Comparator?

شيء يمكن استخدامه بالطريقة التالية:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

لهذا السبب. someT يتم إدراجه بحيث يتم الحفاظ على الترتيب في القائمة وفقًا لذلك cmp

(بناءً على اقتراح @andersoj، أكمل سؤالي بطلب آخر)

أريد أيضًا أن أكون قادرًا على اجتياز القائمة بترتيب مفروز دون إزالة العناصر، على سبيل المثال:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

يجب أن تمر.

نرحب بجميع الاقتراحات (باستثناء إخباري باستخدام Collections.sort في القائمة الكاملة غير المرتبة)، على الرغم من ذلك، أفضل شيئًا ما java.* أو في نهاية المطاف org.apache.* لأنه سيكون من الصعب تقديم مكتبات جديدة في هذه اللحظة.

ملحوظة:(تحديث 4) أدركت أن تطبيقات هذا النوع من القائمة لن يكون لها أداء كافٍ.هناك نهجان عامان:

1. استخدم البنية المرتبطة (نوعًا ما) B-tree أو ما شابه ذلك
2. استخدام المصفوفة والإدراج (مع البحث الثنائي)

رقم 1.لديه مشكلة مع ذاكرة التخزين المؤقت CPU يفتقد رقم 2.لديه مشكلة مع تحويل العناصر في المصفوفة.

التحديث 2: TreeSet لا يعمل لأنه يستخدم المقارنة المتوفرة (MyComparator) للتحقق من التساوي وبناء عليه يفترض تساوي العناصر واستبعادها.أحتاج إلى أداة المقارنة هذه فقط من أجل الترتيب، وليس تصفية "التفرد" (نظرًا لأن العناصر حسب ترتيبها الطبيعي ليست متساوية)

التحديث 3: PriorityQueue لا يعمل كما List (كما أحتاج) لأنه لا توجد طريقة لاجتيازها بالترتيب الذي تم "فرزها به"، للحصول على العناصر بالترتيب المفرز، عليك إزالتها من المجموعة.

تحديث:

سؤال مماثل:
قائمة مرتبة جيدة لجافا
قائمة الصفيف مرتبة في جافا

Answer 1

الاستجابة للمتطلبات الجديدة.أرى احتمالين:

• افعل ما يفعله JavaDoc PriorityQueue يقول:

  تقوم هذه الفئة ومكررها بتنفيذ جميع الطرق الاختيارية لواجهات Collection وIterator.تم توفير التكرار في الطريقة iterator() لا يمكن ضمان اجتياز عناصر قائمة الانتظار ذات الأولوية بأي ترتيب معين.إذا كنت بحاجة إلى اجتياز مرتب، ففكر في استخدامه Arrays.sort(pq.toArray()).

  أظن أن هذا سيؤدي إلى أفضل أداء نظرًا لمتطلباتك.إذا لم يكن هذا مقبولاً، فسوف تحتاج إلى شرح أفضل لما تحاول تحقيقه.

• القيام بالبناء قائمة الذي يفرز نفسه ببساطة عند إضافة عناصر جديدة.هذا هو الألم الحقيقي...إذا استخدمت بنية مرتبطة، فيمكنك إجراء فرز إدراج فعال، ولكن المنطقة المحلية سيئة.إذا كنت تستخدم بنية مدعومة بمصفوفة، فإن فرز الإدراج يعد أمرًا مؤلمًا ولكن الاجتياز أفضل.إذا كان التكرار/الاجتياز نادرًا، فيمكنك الاحتفاظ بمحتويات القائمة دون فرز وفرزها فقط عند الطلب.

• فكر في استخدام أ طابور الأولوية كما اقترحت، وإذا كنت بحاجة إلى التكرار بالترتيب، فاكتب مكررًا مجمّعًا:

  class PqIter implements Iterator<T>
  {
     final PriorityQueue<T> pq;
     public PqIter(PriorityQueue <T> source)
     {
       pq = new PriorityQueue(source); 
     }
  
     @Override
     public boolean hasNext()
     {
       return pq.peek() != null
     }
  
     @Override
     public T next()
     { return pq.poll(); }
  
     @Override
     public void remove()
     { throw new UnsupportedOperationException(""); }
  }
  

• استخدم الجوافة TreeMultiSet.لقد اختبرت الكود التالي مع Integer ويبدو أن تفعل الشيء الصحيح.

  import com.google.common.collect.TreeMultiset;
  
  public class TreeMultiSetTest { 
    public static void main(String[] args) {
      TreeMultiset<Integer> ts = TreeMultiset.create();
      ts.add(1);  ts.add(0); ts.add(2);
      ts.add(-1); ts.add(5); ts.add(2);
  
      for (Integer i : ts) {
        System.out.println(i);
      } 
    } 
  }
  

يعالج ما يلي مشكلة التفرد/التصفية التي كنت تواجهها عند استخدام ملف SortedSet.أرى أنك تريد أيضًا مكررًا، لذلك لن ينجح هذا.

إذا كان ما تريده حقًا هو أمر مثل القائمة الشيء، يمكنك الاستفادة من PriorityQueue.

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

لاحظ ما تقوله وثائق واجهة برمجة التطبيقات (API) حول خصائص الوقت للعمليات المختلفة:

ملاحظة التنفيذ:يوفر هذا التنفيذ يا (سجل (ن)) الوقت لطرق enqueing و dequeing (offer, poll, remove() و add); خطي الوقت ل remove(Object) و contains(Object) طُرق؛و ثابت الوقت المناسب لطرق الاسترجاع (peek, element, ، و size).

يجب عليك أيضًا أن تدرك أن التكرارات التي يتم إنتاجها بواسطة PriorityQueue لا تتصرف كما قد يتوقع المرء:

ال Iterator المنصوص عليها في الطريقة iterator() لا يمكن ضمان اجتياز عناصر قائمة الانتظار ذات الأولوية بأي ترتيب معين.إذا كنت بحاجة إلى اجتياز مرتب، ففكر في استخدامه Arrays.sort(pq.toArray()).

لقد لاحظت للتو أن الجوافة توفر ملف MinMaxPriorityQueue.هذا التنفيذ مدعوم بالمصفوفة، بدلاً من النموذج المرتبط الموجود في JDK PriorityQueue, ، وبالتالي من المحتمل أن يكون له سلوك توقيت مختلف.إذا كنت تفعل شيئًا حساسًا للأداء، فقد ترغب في إلقاء نظرة عليه.في حين أن الملاحظات تعطي أوقاتًا كبيرة مختلفة قليلاً (خطية ولوغاريتمية)، إلا أن كل تلك الأوقات يجب أيضًا أن تكون محددة، وهو ما قد يكون مفيدًا.

لا يوجد List التنفيذ في حد ذاته يحافظ على الترتيب، ولكن ما تبحث عنه على الأرجح هو تطبيقات SortedSet.أ TreeSet هو الأكثر شيوعا.التنفيذ الآخر، أ ConcurrentSkipListSet مخصص لاستخدامات أكثر تحديدًا.لاحظ أن أ SortedSet يوفر الطلب، لكنه لا يسمح بإدخالات مكررة، كما يفعل a List.

المراجع:

• مشاركة مدونة PriorityQueue لم يتم طلب التكرار
• سؤال على ذلك أمر PQ المكرر

Answer 2

ربما عليك أن تكون باستخدام TreeSet:

العناصر التي أمرت باستخدام الطبيعي يأمر, أو عن طريق المقارنة المقدمة في تعيين وقت إنشاء ، اعتمادا على البناء المستخدمة.

على سبيل المثال:

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

لاحظ أن هذا هو مجموعة, لذا لا إدخالات مكررة مسموح بها.هذا قد أو قد لا تعمل المحددة الخاصة بك استخدام القضية.

Answer 3

لدي مشكلة مماثلة وأنا أفكر في استخدام الأشجار.لتجنب استبعاد العناصر "المتساوية"، سأقوم بتعديل المقارنة، لذا بدلا من العودة 0، سيعود رقما عشوائيا بين (-1،1) أو سيعود دائما 1.

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