استخراج عدد معين من أعلى القيم في القائمة

Question

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

الحل الأول الذي يتبادر إلى الذهن هو القيام Collections.sort() وللحصول على العناصر واحدة تلو الأخرى عن طريق المرور عبر List. هل هناك حل أكثر أناقة على الرغم من أنه يمكن استخدامه لإعداد العناصر الثمانية الأولى ، على سبيل المثال؟

Answer 1

فقط اذهب ل Collections.sort(..). إنه فعال بما فيه الكفاية.

تقدم هذه الخوارزمية أداءً مضمونًا لـ N log (n).

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

Answer 2

خياراتك:

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

   تحديث: أقف تصحيحًا على البحث الخطي بالضرورة أفضل من الفرز. انظر مقال ويكيبيديا "Selection_algorithm - اختيار k أصغر أو أكبر عناصر"للحصول على خوارزميات اختيار أفضل.

2. الحفاظ يدويا List (واحد أو واحد متوازي) مرتبة في ترتيب الوزن. يمكنك استخدام طرق مثل Collections.binarySearch () لتحديد مكان إدراج كل عنصر جديد.

3. الحفاظ على أ List (الأصلي أو واحد متوازي) مرتبة في ترتيب الوزن عن طريق الاتصال collections.sort () بعد كل تعديل ، تعديلات الدُفعات ، أو قبل العرض مباشرة (ربما الحفاظ على علامة تعديل لتجنب فرز قائمة مرتبة بالفعل).

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

5. الحفاظ يدويًا على بنية بيانات ثانية (ربما مرتبة بالوزن) للعناصر العليا N. يتم تحديث بنية البيانات هذه في أي وقت يتم فيه تعديل بنية البيانات الأصلية. يمكنك إنشاء بنية البيانات الخاصة بك لالتفاف القائمة الأصلية وهذا "Top N Cache" معًا.

Answer 3

يمكنك استخدام أ ماكس هيب.

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

Answer 4

أو أ طابور الأولوية.

Answer 5

استخدام دولار:

List<Integer> topTen = $(list).sort().slice(10).toList();

دون استخدام الدولار يجب عليك sort() باستخدام Collections.sort(), ، ثم احصل على العناصر الأولى باستخدام list.sublist(0, n).

Answer 6

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

Queue<Integer> topN = new PriorityQueue<Integer>(n);
for (Integer item : input) {
  if (topN.size() < n) {
    topN.add(item);        
  } else if (item > topN.peek()) {
    topN.add(item);          
    topN.poll();
  }
}

List<Integer> result = new ArrayList<Integer>(n);
result.addAll(topN);
Collections.sort(result, Collections.reverseOrder());

الكومة هنا (ميني راب) يحدها الحجم على الأقل. ليست هناك حاجة حقيقية لجعل كومة من جميع العناصر الخاصة بك.

Answer 7

لا ليس بالفعل كذلك. على الأقل عدم استخدام طرق Java المدمجة.

هناك طرق ذكية للحصول على أعلى (أو أدنى) عدد من العناصر من قائمة أسرع من O(n*log(n)) العملية ، ولكن هذا سيتطلب منك ترميز هذا الحل باليد. إذا بقي عدد العناصر منخفضًا نسبيًا (لا يزيد عن بضع مئات) ، فالفصل باستخدامه باستخدام Collections.sort() ثم الاستيلاء على أرقام أفضل n هو الطريق للذهاب IMO.

Answer 8

يعتمد على عدد. دعنا نحدد N على أنه العدد الإجمالي للمفاتيح ، و M كرقم ترغب في عرضه.
فرز كل شيء: O(nlogn)
مسح المصفوفة في كل مرة للحصول على أعلى رقم التالي: O(n*m)
لذا فإن السؤال هو - ما هي العلاقة بين n إلى m؟
لو m < log n, ، سيكون المسح أكثر كفاءة.
غير ذلك، m >= log n, ، مما يعني أن الفرز سيكون أفضل. (منذ لحالة الحافة m = log n لا يهم في الواقع ، لكن الفرز سيمنحك أيضًا فائدة ، جيدًا ، فرز الصفيف ، وهو أمر لطيف دائمًا.

Answer 9

إذا كان حجم القائمة هو n ، وعدد العناصر المراد استردادها هو k ، فأنت بحاجة إلى استدعاء Heapify في القائمة ، والتي تحول القائمة (التي يجب أن تكون قابلة للفهرسة ، على سبيل المثال صفيف) إلى قائمة انتظار ذات أولوية. (انظر وظيفة Heapify في http://en.wikipedia.org/wiki/Heapsort)

يستغرق استرداد عنصر في الجزء العلوي من الكومة (عنصر الحد الأقصى) وقتًا في (LG n). لذلك سيكون وقتك العام:

o (n + k lg n)

وهو أفضل من O (n lg n) على افتراض أن K أصغر بكثير من N.

Answer 10

إذا كان الاحتفاظ بمجموعة مصنفة أو استخدام بنية بيانات مختلفة ليس خيارًا ، فيمكنك تجربة شيء مثل ما يلي. يشبه الوقت o فرز الصفيف الكبير ولكن في الممارسة العملية يجب أن يكون هذا أكثر كفاءة.

small_array = big_array.slice( number_of_items_to_find );
small_array.sort();
least_found_value = small_array.get(0).value;

for ( item in big_array ) {  // needs to skip first few items
  if ( item.value > least_found_value ) {
    small_array.remove(0);
    small_array.insert_sorted(item);
    least_found_value = small_array.get(0).value;
  }
}

يمكن أن يكون small_array كائنًا [] ويمكن إجراء الحلقة الداخلية مع التبديل بدلاً من الإزالة والإدراج فعليًا في صفيف.