ما هي القائمة <Object> التي ستكون الأسرع في الكتابة والقراءة والتدمير لمرة واحدة؟

Question

ما هو أسرع تنفيذ للقائمة (في جافا) في سيناريو حيث سيتم إنشاء القائمة عنصرًا واحدًا في كل مرة ثم في وقت لاحق سيتم قراءة عنصر واحد في كل مرة؟سيتم إجراء القراءات باستخدام مكرر ومن ثم سيتم تدمير القائمة.
أعلم أن تدوين Big O لـ get هو O(1) والإضافة هي O(1) لقائمة ArrayList، بينما LinkedList هو O(n) لـ get وO(1) للإضافة.هل يتصرف المكرر بنفس تدوين Big O؟

Answer 1

يعتمد الأمر إلى حد كبير على ما إذا كنت تعرف الحد الأقصى لحجم كل قائمة مقدمًا.

إذا قمت بذلك، استخدم ArrayList;سيكون بالتأكيد أسرع.

بخلاف ذلك، ربما سيتعين عليك إنشاء ملف تعريف.أثناء الوصول إلى ArrayList هو O(1)، فإن إنشائه ليس بهذه البساطة، بسبب تغيير الحجم الديناميكي.

هناك نقطة أخرى يجب أخذها بعين الاعتبار وهي أن مقايضة الزمكان ليست واضحة المعالم.يحتوي كل كائن Java على قدر كبير من الحمل.في حين أن ArrayList قد يهدر بعض المساحة على الفتحات الفائضة، كل فتحة تبلغ 4 بايت فقط (أو 8 على JVM 64 بت).كل عنصر من أ LinkedList من المحتمل أن يكون حوالي 50 بايت (ربما 100 في JVM 64 بت).لذلك يجب أن يكون لديك عدد لا بأس به من الفتحات الضائعة في ArrayList قبل LinkedList في الواقع تفوز بميزتها الفضائية المفترضة.المنطقة المرجعية هي أيضًا عامل ArrayList ويفضل هناك أيضا.

في الممارسة العملية، أستخدمها دائمًا تقريبًا ArrayList.

Answer 2

الأفكار الأولى:

• أعد صياغة التعليمات البرمجية الخاصة بك حتى لا تحتاج إلى القائمة.
• قم بتبسيط البيانات إلى نوع بيانات عددي، ثم استخدم: كثافة العمليات []
• أو حتى مجرد استخدام مجموعة من أي كائن لديك: هدف[] - جون جاردنر
• تهيئة القائمة بالحجم الكامل: new ArrayList(123);

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

Answer 3

التكرار من خلال قائمة مرتبطة هو O(1) لكل عنصر.

وقت تشغيل Big O لكل خيار هو نفسه.من المحتمل أن تكون ArrayList أسرع بسبب موقع الذاكرة الأفضل، ولكن سيتعين عليك قياسها للتأكد من ذلك.اختر ما يجعل الكود أوضح.

Answer 4

لاحظ أن التكرار من خلال مثيل LinkedList يمكن أن يكون O(n^2) إذا تم ذلك بسذاجة.خاصة:

List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

هذا أمر فظيع للغاية من حيث الكفاءة نظرًا لحقيقة أنه يجب اجتياز القائمة حتى تصل إلى ذلك i مرتين لكل التكرار.إذا كنت تستخدم LinkedList, ، تأكد من استخدام إما Iterator أو Java 5 المحسنة for-حلقة:

for (Object o : list) {
    // ...
}

الكود أعلاه هو O(n)، حيث يتم اجتياز القائمة بشكل سليم في مكانها.

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

Answer 5

أقترح قياس ذلك.إن قراءة واجهة برمجة التطبيقات (API) شيء واحد، ولكن حتى تجربها بنفسك، فستكون أكاديمية.

يجب أن يكون من السهل اختباره، فقط تأكد من قيامك بعمليات ذات معنى، وإلا فإن نقطة الاتصال سوف تتفوق عليك في الذكاء وتقوم بتحسينها كلها إلى NO-OP :)

Answer 6

من المؤكد أنك تريد ArrayList.يعد كل من الإضافة والقراءة "وقتًا ثابتًا مستهلكًا" (أي.O(1)) كما هو محدد في الوثائق (لاحظ أن هذا صحيح حتى لو كان على القائمة زيادة حجمها - فهي مصممة على هذا النحو انظر http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html ).إذا كنت تعرف تقريبًا عدد الكائنات التي ستقوم بتخزينها، فسيتم التخلص من الزيادة في حجم ArrayList.

الإضافة إلى نهاية القائمة المرتبطة هي O(1)، لكن المضاعف الثابت أكبر من ArrayList (نظرًا لأنك عادةً ما تقوم بإنشاء كائن عقدة في كل مرة).القراءة مطابقة فعليًا لقائمة ArrayList إذا كنت تستخدم مكررًا.

إنها قاعدة جيدة أن تستخدم دائمًا أبسط بنية ممكنة، ما لم يكن هناك سبب وجيه لعدم القيام بذلك.هنا لا يوجد مثل هذا السبب.

الاقتباس الدقيق من وثائق ArrayList هو:"تعمل عملية الإضافة في وقت ثابت مستهلك، أي أن إضافة عناصر n تتطلب وقت O(n).جميع العمليات الأخرى تعمل في وقت خطي (تقريبًا).العامل الثابت منخفض مقارنةً بتطبيق LinkedList."

Answer 7

هناك تطبيق قائمة جديد يسمى قائمة الغراء وهو أسرع من جميع تطبيقات القائمة الكلاسيكية.

Answer 8

لقد بدأت بالفعل أعتقد أنه يجب تجنب أي استخدام لهياكل البيانات ذات السلوك غير الحتمي، مثل ArrayList أو HashMap، لذلك أود أن أقول استخدم ArrayList فقط إذا كان بإمكانك ربط حجمه؛أي قائمة غير محدودة تستخدم LinkedList.وذلك لأنني أقوم بشكل أساسي بترميز الأنظمة ذات متطلبات الوقت الفعلي تقريبًا.

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

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