هياكل بيانات .NET:ArrayList، List، HashTable، Dictionary، SortedList، SortedDictionary - السرعة والذاكرة ومتى يتم استخدام كل منها؟

Question

يحتوي .NET على الكثير من بنيات البيانات المعقدة.لسوء الحظ، بعضها متشابه تمامًا، ولست متأكدًا دائمًا متى أستخدم واحدًا ومتى أستخدم الآخر.معظم كتبي في C# وVisual Basic تتحدث عنها إلى حد ما، لكنها لا تخوض في أي تفاصيل حقيقية.

ما الفرق بين Array وArrayList وList وHashtable وDictionary وSortedList وSortedDictionary؟

ما هي تلك التي يمكن تعدادها (IList - يمكنها عمل حلقات "foreach")؟أي منها يستخدم أزواج المفتاح/القيمة (IDict)؟

ماذا عن بصمة الذاكرة؟سرعة الإدراج؟سرعة الاسترجاع؟

هل هناك أي هياكل بيانات أخرى تستحق الذكر؟

ما زلت أبحث عن مزيد من التفاصيل حول استخدام الذاكرة وسرعتها (تدوين Big-O).

Answer 1

من أعلى رأسي:

• Array* - يمثل مصفوفة ذاكرة المدرسة القديمة - يشبه نوعًا ما الاسم المستعار العادي type[] مجموعة مصفوفة.يمكن أن تعداد.لا يمكن أن تنمو تلقائيا.أفترض سرعة إدخال واسترجاع سريعة جدًا.

• ArrayList - مجموعة متزايدة تلقائيا.يضيف المزيد من النفقات العامة.يمكن التعداد، ربما أبطأ من المصفوفة العادية ولكنها لا تزال سريعة جدًا.يتم استخدامها كثيرًا في .NET

• List - أحد المفضلات لدي - يمكن استخدامه مع الأدوية العامة، بحيث يمكنك الحصول على مصفوفة مكتوبة بقوة، على سبيل المثال. List<string>.بخلاف ذلك، يتصرف مثل إلى حد كبير ArrayList

• Hashtable - هاشتابل قديم عادي.O(1) إلى O(n) أسوأ الحالات.يمكن تعداد خصائص القيمة والمفاتيح، وإجراء أزواج المفاتيح/القيم

• Dictionary - نفس ما ورد أعلاه فقط مكتوبًا بقوة عبر الأدوية العامة، مثل Dictionary<string, string>

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

أنا أميل إلى استخدام List و Dictionary طوال الوقت - بمجرد أن تبدأ في استخدامها بقوة مع الأدوية العامة، فمن الصعب حقًا العودة إلى الأدوية القياسية غير العامة.

هناك الكثير من هياكل البيانات الأخرى أيضًا - هناك KeyValuePair والتي يمكنك استخدامها للقيام ببعض الأشياء المثيرة للاهتمام، هناك SortedDictionary والتي يمكن أن تكون مفيدة أيضًا.

Answer 2

إذا كان ذلك ممكنا، استخدم الأدوية الجنيسة. هذا يتضمن:

• القائمة بدلاً من ArrayList
• القاموس بدلاً من HashTable

Answer 3

أولاً، تقوم كافة المجموعات في .NET بتطبيق IEnumerable.

ثانيًا، الكثير من المجموعات مكررة لأنه تمت إضافة الأدوية العامة في الإصدار 2.0 من إطار العمل.

لذا، على الرغم من أن المجموعات العامة من المحتمل أن تضيف ميزات، إلا أن الجزء الأكبر منها:

• القائمة هي تطبيق عام لـ ArrayList.
• القاموس هو تطبيق عام لـ Hashtable

المصفوفات عبارة عن مجموعة ذات حجم ثابت يمكنك تغيير القيمة المخزنة في فهرس معين.

SortedDictionary هو قاموس معرفي يتم فرزه بناءً على المفاتيح.SortedList عبارة عن قاموس معرفي يتم فرزه بناءً على IComparer المطلوب.

لذا، فإن تطبيقات IDictionary (تلك التي تدعم KeyValuePairs) هي:* hashtable * قاموس * sortedlist * sortedDictionaryary

مجموعة أخرى تمت إضافتها في .NET 3.5 هي Hashset.إنها مجموعة تدعم العمليات المحددة.

كما أن LinkedList عبارة عن تطبيق قياسي للقائمة المرتبطة (القائمة عبارة عن قائمة مصفوفة لاسترجاع أسرع).

Answer 4

ورقة غش جيدة مع ذكر التعقيدات المتعلقة بهياكل البيانات والخوارزميات وما إلى ذلك.

Answer 5

إليك بعض النصائح العامة لك:

• يمكنك استخدام foreach على الأنواع التي تنفذ IEnumerable. IList هو في الأساس IEnumberable مع Count و Item (الوصول إلى العناصر باستخدام فهرس صفري). IDictionary من ناحية أخرى يعني أنه يمكنك الوصول إلى العناصر عن طريق أي فهرس قابل للتجزئة.

• Array, ArrayList و List تنفيذ جميع IList. Dictionary, SortedDictionary, ، و Hashtable ينفذ IDictionary.

• إذا كنت تستخدم .NET 2.0 أو أعلى، فمن المستحسن استخدام نظيرات عامة من الأنواع المذكورة.

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

• هياكل بيانات .NET موجودة System.Collections مساحة الاسم.هناك مكتبات نوع مثل مجموعات الطاقة والتي تقدم هياكل بيانات إضافية.

• للحصول على فهم شامل لهياكل البيانات، راجع موارد مثل CLRS.

Answer 6

هياكل بيانات .NET:

المزيد للمحادثة حول سبب اختلاف ArrayList و List بالفعل

المصفوفات

كما ذكر أحد المستخدمين، فإن المصفوفات هي مجموعة "المدرسة القديمة" (نعم، تعتبر المصفوفات مجموعة ولكنها ليست جزءًا منها System.Collections).ولكن، ما هي "المدرسة القديمة" فيما يتعلق بالمصفوفات مقارنة بالمجموعات الأخرى، أي تلك التي أدرجتها في عنوانك (هنا، ArrayList وList(Of T))؟لنبدأ بالأساسيات من خلال النظر إلى المصفوفات.

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

أبعد من ذلك، وعلى عكس 101 مفهوم شائع للبرمجة، يمكن أن تكون المصفوفات معقدة للغاية:

يمكن أن تكون المصفوفات أحادية البعد، أو متعددة الأبعاد، أو متراكمة (المصفوفات المتعرجة تستحق القراءة عنها).المصفوفات نفسها ليست ديناميكية:بمجرد التهيئة، مجموعة من ن الحجم يحتفظ بمساحة كافية للاحتفاظ به ن عدد الكائنات.لا يمكن أن يزيد عدد العناصر في المصفوفة أو يتقلص. Dim _array As Int32() = New Int32(100) يحجز مساحة كافية على كتلة الذاكرة ليحتوي المصفوفة على 100 كائن من النوع البدائي Int32 (في هذه الحالة، تتم تهيئة المصفوفة لتحتوي على 0s).يتم إرجاع عنوان هذه الكتلة إلى _array.

وفقا للمادة، مواصفات اللغة المشتركة (CLS) يتطلب أن تكون جميع المصفوفات ذات أساس صفري.المصفوفات في .NET تدعم المصفوفات غير الصفرية؛ومع ذلك، هذا أقل شيوعاً.نتيجة "شيوعية" المصفوفات ذات الأساس الصفري، أنفقت Microsoft الكثير من الوقت لتحسين أدائها;لذلك، تعد المصفوفات ذات البعد الواحد والمصفوفة الصفرية (SZs) "خاصة" - وهي حقًا أفضل تطبيق لمصفوفة (على عكس المصفوفات متعددة الأبعاد، وما إلى ذلك) - لأن المصفوفات ذات البعد الواحد لديها تعليمات لغة وسيطة محددة لمعالجتها.

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

مرة أخرى، أكبر عائق أمام المصفوفات هو عدم إمكانية تغيير حجمها.لديهم قدرة "ثابتة".تقديم ArrayList وList(Of T) إلى تاريخنا:

ArrayList - قائمة غير عامة

ال ArrayList (جنبا إلى جنب مع List(Of T) - على الرغم من وجود بعض الاختلافات الهامة هنا، والتي سيتم شرحها لاحقًا) - ربما يكون من الأفضل اعتبارها الإضافة التالية للمجموعات (بالمعنى الواسع).ArrayList ترث من الأول قائمة (سليل واجهة 'ICollection').ArrayLists، في حد ذاتها، هي أضخم - تتطلب المزيد تكاليف غير مباشرة - من القوائم.

IList يمكّن التنفيذ من التعامل مع ArrayLists كقوائم ذات حجم ثابت (مثل Arrays)؛ومع ذلك، بخلاف الوظائف الإضافية التي أضافتها ArrayLists، لا توجد مزايا حقيقية لاستخدام ArrayLists ذات الحجم الثابت لأن ArrayLists (فوق المصفوفات) في هذه الحالة تكون أبطأ بشكل ملحوظ.

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

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

قائمة (من T):ما أصبح ArrayList (وآمل أن يكون)

يعد الاختلاف في استخدام الذاكرة كبيرًا بدرجة كافية حيث تستهلك القائمة (Of Int32) ذاكرة أقل بنسبة 56% من قائمة ArrayList التي تحتوي على نفس النوع البدائي (8 ميجابايت مقابل 8 ميجابايت).19 ميغابايت في العرض التوضيحي المرتبط أعلاه:مرة أخرى، مرتبطة هنا) - على الرغم من أن هذه نتيجة تفاقمت بواسطة جهاز 64 بت.إن هذا الاختلاف يدل حقاً على أمرين:أولاً (1)، "كائن" من نوع Int32 (ArrayList) أكبر بكثير من نوع Int32 البدائي (قائمة)؛ثانيًا (2)، يكون الفرق هائلاً نتيجة للعمل الداخلي لجهاز 64 بت.

إذن ما هو الفرق وما هو قائمة (من تي)? MSDN يحدد أ List(Of T) مثل، "...قائمة مكتوبة بقوة بالكائنات التي يمكن الوصول إليها عن طريق الفهرس." تكمن الأهمية هنا في البت "المكتوب بقوة":قائمة (من T) "تتعرف" على الأنواع وتخزن الكائنات كنوعها.لذلك، ان Int32 يتم تخزينه ك Int32 وليس Object يكتب.وهذا يزيل المشاكل الناجمة عن الملاكمة والفتح.

تحدد MSDN أن هذا الاختلاف يتم تفعيله فقط عند تخزين الأنواع البدائية وليس الأنواع المرجعية. أيضًا، يحدث الاختلاف بالفعل على نطاق واسع:أكثر من 500 عنصر.الأمر الأكثر إثارة للاهتمام هو أن وثائق MSDN تنص على أنه "من مصلحتك استخدام التطبيق الخاص بالنوع لفئة List(Of T) بدلاً من استخدام فئة ArrayList...."

في الأساس، List(Of T) هي ArrayList، ولكنها أفضل.إنه "المعادل العام" لـ ArrayList.مثل ArrayList، ليس من المضمون أن يتم فرزها حتى يتم فرزها (انظر الشكل).تحتوي القائمة (Of T) أيضًا على بعض الوظائف المضافة.

Answer 7

أنا أتعاطف مع السؤال - لقد وجدت أيضًا (تجد؟) الاختيار محيرًا، لذلك شرعت بشكل علمي في معرفة أي بنية بيانات هي الأسرع (لقد أجريت الاختبار باستخدام VB، لكنني أتخيل أن C# ستكون نفسها، لأن كلا اللغتين افعل نفس الشيء على مستوى CLR).يمكنك ان ترى بعض نتائج القياس التي أجراها لي هنا (هناك أيضًا بعض المناقشات حول نوع البيانات الأفضل للاستخدام وفي أي ظروف).

Answer 8

لقد تم توضيحها بشكل جيد في الذكاء.فقط اكتب System.Collections. أو System.Collections.Generics (مفضل) وستحصل على قائمة ووصف مختصر لما هو متاح.

Answer 9

جداول التصنيف/القواميس هي أداء O(1)، مما يعني أن الأداء ليس دالة للحجم.من المهم أن نعرف.

يحرر:من الناحية العملية، متوسط ​​التعقيد الزمني لعمليات البحث في Hashtable/Dictionary<> هو O(1).

Answer 10

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

Answer 11

ملاحظة مهمة حول Hashtable vs Dictionary لهندسة التداول المنهجي عالي التردد:مشكلة سلامة الموضوع

يعد Hashtable آمنًا للاستخدام بواسطة سلاسل رسائل متعددة.الأعضاء الثابتون العامون في القاموس آمنون، لكن لا يمكن ضمان أن يكونوا كذلك في أي مثيل.

لذا يظل Hashtable هو الخيار "المعياري" في هذا الصدد.

Answer 12

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

Answer 13

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

Answer 14

هياكل ومجموعات بيانات C# الأكثر شيوعًا

• مجموعة مصفوفة
• ArrayList
• قائمة
• قائمة مرتبطة
• قاموس
• HashSet
• كومة
• طابور
• SortedList

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

في هذه المقالة سوف أتناول بنيات البيانات المضمنة في C#، بما في ذلك تلك الجديدة المقدمة في C#.NET 3.5.لاحظ أن العديد من هياكل البيانات هذه تنطبق على لغات البرمجة الأخرى.

مجموعة مصفوفة

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

[object type][] myArray = new [object type][number of elements]

بعض الأمثلة:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

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

ArrayList

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

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

الجانب السلبي لبنية بيانات ArrayList هو أنه يجب على المرء إعادة القيم المستردة إلى نوعها الأصلي:

int arrayListValue = (int)myArrayList[0]

المصادر ومزيد من المعلومات يمكنك العثور عليها هنا :

• هياكل البيانات C#
• المجموعات وهياكل البيانات
• List vs IEnumerable vs IQueryable vs ICollection vs IDictionary
• System.Collections.مساحة الاسم العامة
• مساحة اسم System.Collections