اختلافات الأداء بين أريليست و لينكدليست

Question

نعم ، هذا موضوع قديم ، لكن لا يزال لدي بعض الالتباسات.

في جاوة ، يقول الناس:

1. أريليست أسرع من لينكدليست إذا كنت عشوائيا الوصول إلى عناصره.أعتقد أن الوصول العشوائي يعني"أعطني العنصر التاسع".لماذا أريليست أسرع?

2. لينكدليست أسرع من أريليست للحذف.أنا أفهم هذا واحد.أرايليست أبطأ منذ صفيف النسخ الاحتياطي الداخلي يحتاج إلى إعادة تخصيص.شرح التعليمات البرمجية:

   List<String> list = new ArrayList<String>();
   list.add("a");
   list.add("b");
   list.add("c");
   list.remove("b");
   System.out.println(list.get(1)); //output "c"
   

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

Answer 1

أريليست أسرع من لينكدليست إذا كنت عشوائيا الوصول إلى عناصره.أعتقد أن الوصول العشوائي يعني"أعطني العنصر التاسع".لماذا أريليست أسرع?

ArrayList لديه إشارات مباشرة إلى كل عنصر في القائمة ، لذلك يمكن الحصول على عنصر ن عشر في وقت ثابت. LinkedList يجب أن تجتاز القائمة من البداية للوصول إلى العنصر ن عشر.

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

ArrayList أبطأ لأنه يحتاج إلى نسخ جزء من المصفوفة لإزالة الفتحة التي أصبحت مجانية.إذا تم الحذف باستخدام ListIterator.remove() أبي, LinkedList فقط يجب أن تتلاعب ببعض المراجع;إذا تم الحذف حسب القيمة أو الفهرس, LinkedList يجب أن تفحص القائمة بأكملها أولا للعثور على العنصر(العناصر) المراد حذفه.

إذا كان ذلك يعني نقل بعض العناصر مرة أخرى ومن ثم وضع العنصر في بقعة فارغة الأوسط ، يجب أن يكون أريليست أبطأ.

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

Answer 2

تجاهل هذه الإجابة الآن. الإجابات الأخرى، خاصة أن AIX ، معظمها صحيحة. على المدى الطويل، إنها طريقة الرهان. وإذا كان لديك ما يكفي من البيانات (على مرجع واحد على جهاز واحد، يبدو أن هناك حوالي مليون إدخال) يتمتع ArrayList و LinkedList حاليا كما هو قيد الإعلان. ومع ذلك، هناك بعض النقاط الدقيقة التي تنطبق في أوائل القرن 21.

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

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

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

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

linkedlist أجزاء صغيرة وذيذة من الذاكرة وحب GC. لا يزال يعمل بشكل جيد عند استخدام 99٪ من ذاكرتك المتوفرة.

لذلك بشكل عام، استخدم قائمة الصفائح الخاصة بمجموعات أصغر من البيانات غير المرجح أن يكون لها معظم محتوياتها المحذوفة، أو عندما تكون لديك سيطرة ضيقة على الإبداع والنمو. (على سبيل المثال، إنشاء قائمة صفيف واحدة تستخدم 90٪ من الذاكرة واستخدامه دون ملء مدة البرنامج على ما يرام. إنشاء وتحرير مثيلات الصفيف باستمرار التي تستخدم 10٪ من الذاكرة ستقتلك.) خلاف ذلك، اذهب مع linkedlist (أو خريطة من نوع ما إذا كنت بحاجة إلى وصول عشوائي). إذا كان لديك مجموعات كبيرة جدا (على سبيل المثال أكثر من 100000 عنصر)، لا توجد مخاوف بشأن GC، وتخطيط الكثير من الإدراج والحذف وليس الوصول العشوائي، وتشغيل بعض المعايير لمعرفة ما هو أسرع.

Answer 3

ال ArrayList الطبقة هي فئة المجمع لمجموعة.يحتوي على صفيف داخلي.

public ArrayList<T> {
    private Object[] array;
    private int size;
}

A LinkedList هي فئة المجمع لقائمة مرتبطة ، مع عقدة داخلية لإدارة البيانات.

public LinkedList<T> {
    class Node<T> {
        T data;
        Node next;
        Node prev;
    }
    private Node<T> first;
    private Node<T> last;
    private int size;
}

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

أريليست أسرع من لينكدليست إذا كنت عشوائيا الوصول إلى عناصره.أعتقد أن الوصول العشوائي يعني"أعطني العنصر التاسع".لماذا أريليست أسرع?

وقت الوصول ل أريليست:س (1).وقت الوصول إلى لينكدليست:س (ن).

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

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

وقت الحذف ل أريليست:وقت الوصول + س (ن).وقت الحذف ل لينكدليست:وقت الوصول + س (1).

يجب على أريليست نقل جميع العناصر من array[index] إلى array[index-1] بدءا من العنصر لحذف الفهرس.يجب أن تنتقل لينكدليست حتى هذا البند ومن ثم محو تلك العقدة عن طريق فصله من القائمة.

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

الإدراج الوقت ل أريليست:س (ن).وقت الإدراج ل لينكدليست:س (1).

لماذا أريليست يمكن أن تأخذ س (ن)?لأنه عندما تقوم بإدراج عنصر جديد وتكون المصفوفة ممتلئة ، فأنت بحاجة إلى إنشاء مصفوفة جديدة بحجم أكبر (يمكنك حساب الحجم الجديد بصيغة مثل 2 * الحجم أو 3 * الحجم / 2).لينكدليست فقط إضافة عقدة جديدة بجانب الماضي.

هذا التحليل ليس فقط في جافا ولكن في لغات برمجة أخرى مثل ج ، ج#و ج#.

مزيد من المعلومات هنا:

• http://en.wikipedia.org/wiki/Array_data_structure
• http://en.wikipedia.org/wiki/Linked_list

Answer 4

كلا من إزالة () وإدراج () لديك كفاءة وقت تشغيل O (N) لكل من المرضيات والربطيات. ومع ذلك، فإن السبب وراء وقت المعالجة الخطي يأتي من سببين مختلفين للغاية:

في قائمة Arraylist تحصل على العنصر في O (1)، ولكن في الواقع إزالة أو إدراج شيء ما يجعله س (ن) لأن جميع العناصر التالية تحتاج إلى تغيير.

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

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

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

Answer 5

arraylist

• arraylist هو أفضل خيار إذا كانت عمليةنا المتكررة عملية استرجاع.
• ArrayList هو أسوأ خيار إذا كانت عمليةنا الإدراج والحذف في المنتصف لأن عمليات التحول متعددة داخليا يتم تنفيذها. سيتم تخزين
• في عناصر الصفيف في مواقع الذاكرة المتتالية، وبالتالي أصبحت عملية الاسترجاع سهلة.

  linkedlist: -

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

    الآن يأتي إلى أسئلتك: -

    1) يوفر Arraylist البيانات وفقا للفهارس وينفذ واجهة RandomAccess التي تعد واجهة العلامة التي توفر إمكانية استرجاع عشوائي إلى قائمة الصفوف ولكن LinkedList لا تنفذ واجهة RandomAccess هذه هي السبب أسرع في قائمة الصور.

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

Answer 6

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

Answer 7

في قائمة مرتبطة بالعناصر لها إشارة إلى العنصر قبل وبعدها.في قائمة صفيف، يكون بنية البيانات مجرد صفيف.

تحتاج LI>

في قائمة الارتباط إلى تكرار عناصر N للحصول على عنصر NTH.تحتاج قائمة صفيف فقط إلى إرجاع عنصر N من صفيف الدعم.

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

2. نفس السبب كحذف هنا.

Answer 8

arraylist : يتمتع مجموعة الصفيف بنية مثل مجموعة، ولها مرجع مباشر إلى كل عنصر.حتى الوصول RENDOM سريع في الصورة.

linkedlist : في قائمة الارتباط للحصول على nth elemnt، يجب عليك اجتياز قائمة كاملة، يستغرق وقتا مقارنة بقائمة الصفيف.كل عنصر لديه رابط لعنصره السابق والعد، لذلك الحذف سريع.

Answer 9

قائمة الصفيف: تعمل فئة ArrayList على توسيع AbstractList وتنفيذ واجهة القائمة وRandomAccess (واجهة العلامة).يدعم ArrayList المصفوفات الديناميكية التي يمكن أن تنمو حسب الحاجة. إنه يعطينا التكرار الأول على العناصر.

قائمة مرتبطة: يتم ترتيب LinkedList حسب موضع الفهرس، مثل ArrayList، باستثناء أن العناصر مرتبطة بشكل مزدوج ببعضها البعض.يمنحك هذا الارتباط طرقًا جديدة (تتجاوز ما تحصل عليه من واجهة القائمة) للإضافة والإزالة من البداية أو النهاية، مما يجعله خيارًا سهلاً لتنفيذ مكدس أو قائمة انتظار.ضع في اعتبارك أن القائمة المرتبطة قد تتكرر بشكل أبطأ من قائمة ArrayList، لكنه يعد اختيارًا جيدًا عندما تحتاج إلى الإدراج والحذف السريع. اعتبارًا من Java 5، تم تحسين فئة LinkedList لتنفيذ واجهة java.util.Queue.وعلى هذا النحو، فهو يدعم الآن أساليب قائمة الانتظار الشائعة:نظرة خاطفة ()، استطلاع ()، وعرض ().

Answer 10

أريد أن أضيف قطعة إضافية من المعلومات لها حول الفرق في الأداء.

نحن نعلم ذلك بالفعل بسبب حقيقة أن ArrayList التنفيذ مدعوم من قبل Object[] إنه يدعم الوصول العشوائي وتغيير الحجم الديناميكي و LinkedList يستخدم التنفيذ مراجع للرأس والذيل للتنقل فيه.ليس لديه قدرات وصول عشوائي ، لكنه يدعم تغيير الحجم الديناميكي أيضا.

أول شيء هو أنه مع أريليست ، يمكنك الوصول على الفور الفهرس ، في حين مع لينكدليست ، لديك تكرار أسفل سلسلة الكائن.

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

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

تحقق من المزيد الاختلافات أريليست و لينكدليست.

Answer 11

حتى يبدو أنها متطابقة (نفس قائمة Inteface المنفذة - غير آمنة غير آمنة)، فهي تعطي نتائج مختلفة من حيث الأداء في إضافة / حذف والبحث عن الوقت والذاكرة المستهلكة (LinkedList تستهلك أكثر).

يمكن استخدام linkedl إذا كنت تستخدم الإدراج / الحذف للغاية مع الأداء O (1). يمكن استخدام أجهزة التشغيل إذا كنت تستخدم عمليات الوصول المباشر مع الأداء O (1)

قد يوضح هذا الرمز من هذه التعليقات ويمكنك محاولة فهم نتائج الأداء.(آسف لرمز لوحة الغلاية) giveacodicetagpre.