لقد اعتدنا على حقيقة أن المجموعات القياسية في JDK مصنوعة بشكل جيد وتتصرف بشكل حدسي. ولكن هل هو حقا كذلك؟ أمس الرومان إليزاروفإليزاروفنشر على تويتر الأخبار حول دعامة جديدة مثيرة للاهتمام.تمسك بشدة: Set.removeAll(list)في بعض الحالات يمكن أن يعمل مع O (N²). كيف ذلك؟
اكتشف رومان مشكلة عندما قام بتصحيح جزء من الكود الذي يعمل ، لسبب مذهل ، ببطء شديد. أطلقه في ملف التعريف المدمج في IntelliJ IDEA ورأى على الفور على الرسم البياني اللهب أنه كان يضيع كل الوقت داخل طريقة AbstractSet.removeAllالاتصال list.contains(رابط إلى المكان المحدد في الرمز ).لفهم ما يحدث ، فكر في مثال مختلف قليلاً. في وقت سابق ، كتب جون سكيت مقالة "هناك فجوة في تجريدي ، عزيزي ليزا ، عزيزة ليزا" ، حيث ينظر في الحالة التالية المثيرة للاهتمام.لنفترض أن لدينا HashSet سنقوم بحذف شيء منه. لنفترض أننا قمنا بإزالة عناصر من مجموعة أخرى B من مجموعة A. غالبًا ما يحدث أن العديد من العناصر من B غير موجودة ببساطة في A. سنقوم بتحليل حالة خاصة عندما لا تتقاطع A و B على الإطلاق - أي أنه لا يوجد شيء يجب القيام به.سنكتب برنامجًا بسيطًا يتم فيه تحديد أحجام مجموعاتنا من سطر الأوامر. بحيث لا تتقاطع هذه المجموعات تمامًا ، سيتم ملء واحدة منها بأرقام موجبة فقط ، والأخرى بأرقام سلبية فقط. ثم نزيل من المجموعة الأولى جميع عناصر الثانية ونقيس الوقت المنقضي باستخدامهاSystem.currentTimeMillis(). هذه ليست أفضل طريقة في العالم لحساب الفترة الزمنية ، ولكنها تجعل من الممكن نسخ ولصق الشفرة مباشرة من هبر إلى إيديا وتتيح لنا من الاضطرار إلى إعداد مشروع مافن جديد لـ JMH.import java.util.*;
public class Test {
public static void main(String[] args) {
int sourceSize = Integer.parseInt(args[0]);
int removalsSize = Integer.parseInt(args[1]);
Set<Integer> source = new HashSet<Integer>();
Collection<Integer> removals = new ArrayList<Integer>();
for (int i = 0; i < sourceSize; i++) {
source.add(i);
}
for (int i = 1; i <= removalsSize; i++) {
removals.add(-i);
}
long start = System.currentTimeMillis();
source.removeAll(removals);
long end = System.currentTimeMillis();
System.out.println("Time taken: " + (end - start) + "ms");
}
}
كود بسيط للغاية يمكن كتابته دون استعادة الوعي. الآن لنقم بتشغيله بمعلمات مختلفة. أولاً ، جرب مجموعة من 100 عنصر تحتاج إلى رمي 100 منها:$ java Test 100 100
Time taken: 1ms
كل شيء سريع حتى الآن ، ولكن ماذا يحدث إذا قمت بزيادة الأعداد؟java Test 1000000 300000
Time taken: 38ms
$java Test 300000 300000
Time taken: 178131ms
كيف تحب هذا: الآن ننتظر ثلاث دقائق. يبدو بديهيًا أن وقت معالجة مجموعة أصغر (300000 عنصر في الحالة الثانية) يجب أن يكون أقل مما كان عليه عند معالجة مجموعة أكبر (مليون عنصر في الحالة الأولى). العكس هو الصحيح على الفور. لم تكن الحياة تستعد لهذا ، أليس كذلك؟الآن سر التركيز.في الواقع ، يتم وصفه بنص واضح في JavaDoc المقابل :مجموعات التعليمات البرمجية أقل: مجموعة أو مجموعة. يتم ذلك باستخدام الطريقة sizeعلى كل منها. إذا كان هناك عدد أقل من العناصر في المجموعة ، فسيتم إجراء التكرار على المجموعة ، وفي كل تكرار يتم التحقق مما إذا كان العنصر الحالي في المجموعة. إذا كانت الإجابة بنعم ، فسيتم إزالة العنصر من المجموعة باستخدام طريقة removeالتكرار. إذا اتضح أن المجموعة أصغر في عدد العناصر ، فسيكون من الضروري تجاوز المجموعة بالفعل ، وإزالة كل هذه العناصر من المجموعة باستخدام الطريقة removeمن المجموعة.
من الناحية العملية ، هذا يعني أنه عند استدعائه source.removeAll(removals):- إذا كانت المجموعة
removalsأصغر من source، فسيتم استدعاء الطريقة removeج HashSet، وهي سريعة جدًا ؛ - إذا كانت المجموعة
removalsأكبر أو متساوية في الحجم منها source، فسيتم استدعاء طريقة removals.containsتعمل ببطء شديد ArrayList.
في JDK 8 ، هناك شيء من هذا القبيل مسؤول عن هذا الجزء من التعليمات البرمجية:public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
يبدو أن JDK قد اختارت طريقة سيئة إلى حد ما للتعامل مع المهمة ، ولكن نظرًا لأنه تم وصفه بالفعل في JavaDoc ، فلا يوجد عودة.أم هناك؟هرع الناس لسقسقة الرومانية Elizarov، وو Zheka كوزلوف وجدت علة المقابلة نشرت على JDK 15 مع أداء، ستيوارت ماركس.وبعد ذلك ، اقتحم ستيوارت ماركس نفسه الخيط وأكد أنه كان يتعامل حقًا مع هذه المشكلة:لذا هناك ضوء في نهاية النفق. إذا قمت بالترقية إلى أحدث إصدارات Java ، بالطبع.الموجودات
الاستنتاجات من هذه القصة هي كما يلي: هناك مشكلة تستحق أن تعرف عنها. يتم بالفعل إصلاح المشكلة ، ولكن تم إصلاحها فقط لمستخدمي Java الجدد السعداء ، ويجب ألا تأمل في ذلك حقًا.بشكل عام ، عندما تحاول تخزين الكثير من البيانات في مجموعات في Java ، فقد تواجه العديد من المشاكل غير البديهية التي تحتاج إلى الاستعداد لها.
لذا ، يا أطفال ، تعلمنا اليوم شيئًا جديدًا!واستمرارًا للحفل ، أوصيك بالنظر إلى بعض التقارير لرومان إليزاروف ، الذي ساعد في تسليط الضوء على هذا الخطأ. بالطبع ، هذه التقارير لا علاقة لها بالخلل نفسه ، ولكن هناك مجموعة من صفائح الصفيح المختلفة:JPoint, , 2020 . , , , .