مصفوفة يمكن تغيير حجمها بسرعة

Question

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

• نظام.مجموعة مصفوفة - Redim Preserve نسخ ذاكرة الوصول العشوائي (RAM) بأكملها من القديم إلى الجديد، ببطء مثل كمية العناصر الموجودة
• System.Collections.ArrayList - جيد بما فيه الكفاية؟
• System.Collections.الأول قائمة - جيد بما فيه الكفاية؟

Answer 1

فقط لتلخيص بعض هياكل البيانات:

System.Collections.ArrayList:هياكل البيانات غير المكتوبة عفا عليها الزمن.استخدم List(of t) بدلاً من ذلك.

System.Collections.Generic.List(من t):وهذا يمثل مصفوفة يمكن تغيير حجمها.تستخدم بنية البيانات هذه مصفوفة داخلية خلف الكواليس.إضافة عناصر إلى القائمة هي O(1) طالما لم يتم ملء المصفوفة الأساسية، وإلا فإن O(n+1) لتغيير حجم المصفوفة الداخلية ونسخ العناصر فوقها.

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

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

System.Collections.Generic.LinkedList(من t):إذا لم تكن بحاجة إلى الوصول العشوائي أو المفهرس إلى العناصر الموجودة في قائمتك، على سبيل المثال، كنت تخطط فقط لإضافة عناصر والتكرار من الأول إلى الأخير، فإن القائمة المرتبطة هي صديقك.عمليات الإدخال والإزالة هي O(1)، والبحث هو O(n).

Answer 2

يجب عليك استخدام القائمة العامة<> (System.Collections.Generic.List) لهذا.تعمل في الوقت المطفأ المستمر.

كما أنه يشارك الميزات التالية مع Arrays.

• وصول عشوائي سريع (يمكنك الوصول إلى أي عنصر في القائمة في O(1))
• إنه سريع التكرار
• بطيء في إدراج وإزالة الكائنات في البداية أو المنتصف (نظرًا لأنه يتعين عليه عمل نسخة من القائمة بأكملها)

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

Answer 3

هل تناسبك بنية LinkedList<T>؟إنها ليست (في بعض الحالات) بديهية مثل المصفوفة المستقيمة، ولكنها سريعة جدًا.

• AddLast للإلحاق بالنهاية
• AddBefore/AddAfter لإدراجها في القائمة
• AddFirst للإلحاق بالبداية

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

يوجد أيضًا هذا المرجع الذي سيساعدك على تحديد الطريقة الصحيحة التي يجب اتباعها:

متى تستخدم قائمة مرتبطة على قائمة صفيف/صفيف؟

Answer 4

ما هو "جيد بما فيه الكفاية" بالنسبة لك؟ما الذي تريد فعله بالضبط ببنية البيانات هذه؟

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

ربما تكون جداول التجزئة (الوصول إلى O(1) المطفأة وإدراجها في أي مكان، ولكن O(n) أسوأ حالة للإدراج) أو الأشجار (O(log(n)) للوصول والإدراج في أي مكان، مضمونة) أكثر ملاءمة.

Answer 5

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

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