مقارب تعقيد .صافي جمع الصفوف

Question

هل هناك أي الموارد عن تعقيد مقارب (big-O والباقي) من طرق .صافي جمع الصفوف (Dictionary<K,V>, List<T> الخ...) ؟

وأنا أعلم أن C5 مكتبة الوثائق يتضمن بعض المعلومات حول هذا الموضوع (على سبيل المثال), ولكن أنا مهتم في المعيار .صافي مجموعات أيضا...(و PowerCollections المعلومات أيضا أن يكون لطيفا).

Answer 1

MSDN قوائم هذه:

• Dictionary<,>
• List<>
• SortedList<,> (تحرير:الخطأ في الرابط ؛ هنا عام الإصدار)
• SortedDictionary<,>

الخ.على سبيل المثال:

على SortedList(TKey, TValue) generic الفصل هي شجرة البحث الثنائية مع O(log n) استرجاع, حيث n هو عدد العناصر في القاموس.في هذا, وهو مشابه SortedDictionary(TKey, TValue) generic فئة.فئتين مماثلة طرازات كائن, وكلاهما O(log n) واسترجاعها.حيث فئتين تختلف في استخدام الذاكرة و سرعة الإدراج وإزالة:

SortedList(TKey, TValue) يستخدم أقل الذاكرة من SortedDictionary(TKey, TValue).

SortedDictionary(TKey, TValue) وقد أسرع الإدراج وإزالة العمليات على البيانات التي لم يتم فرزها ، O(log n) بدلا من O(n) SortedList(TKey, TValue).

إذا كان يتم تعبئة قائمة في كل مرة من فرز البيانات ، SortedList(TKey, TValue) هو أسرع من SortedDictionary(TKey, TValue).

Answer 2

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

ولقد اتخذت الجداول من تلك الصفحة وتغيير / موسع لهم للإطار. NET. انظر أيضا صفحات MSDN ل SortedDictionary و <لأ href = "HTTP: //msdn.microsoft.com/en-us/library/ms132319.aspx "يختلط =" noreferrer "> SortedList ، التي التفاصيل تعقيدات الوقت اللازم لعمليات مختلفة.

---

البحث

Type of Search/Collection Types           Complexity  Comments
Linear search Array/ArrayList/LinkedList  O(N)        Unsorted data.
Binary search sorted Array/ArrayList/     O(log N)    Requires sorted data.
Search Hashtable/Dictionary<T>            O(1)        Uses hash function.
Binary search SortedDictionary/SortedKey  O(log N)    Sorting is automated.

استرجاع والإدراج

Operation         Array/ArrayList  LinkedList  SortedDictionary  SortedList
Access back       O(1)             O(1)        O(log N)          O(log N)
Access front      O(1)             O(1)        N.A.              N.A.
Access middle     O(1)             O(N)        N.A.              N.A.
Insert at back    O(1)             O(1)        O(log N)          O(N)
Insert at front   O(N)             O(1)        N.A.              N.A.
Insert in middle  O(N)             O(1)        N.A.              N.A.

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

وSortedList لديه بعض الخصائص البارزة لإدخال واسترجاع.

الإدراج (إضافة أسلوب):

<اقتباس فقرة>   

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

استرجاع (الخاصية عنصر):

<اقتباس فقرة>   

واسترداد قيمة هذه الخاصية   هي عملية O (سجل ن)، حيث n   العد. تعيين الخاصية هي   O (تسجيل ن) العملية إذا كان المفتاح   بالفعل في SortedList <(و<(TKey،   TValue>)>). إذا لم يكن المفتاح في   القائمة، إعداد الخاصية هو O (ن)   عملية للبيانات لم يتم فرزها، أو O (سجل   ن) إذا تم إضافة العنصر الجديد في   نهاية القائمة. إذا تسبب الإدراج ل   تغيير الحجم، وهذه العملية O (ن).

لاحظ أن ArrayList ما يعادل List<T> من حيث تعقيد جميع العمليات.

---

Answer 3

وأنا لا أعرف بشكل عام (الجواب أخرى نشرت فقط ربما يعطي لك بالضبط ما كنت بعد) - ولكن هل يمكن أن تعكس هذه وغيرها من أساليب بالطبع باستخدام ILSpy (قليلا محرجا مع رمز FSharp، صحيح) و هذا ينتج في نهاية المطاف هذه الوظيفة كما C #:

internal static a maximumElementAux<a>(SetTree<a> s, a n)
{
  while (true)
  {
    SetTree<a> setTree = s;
    if (setTree is SetTree<a>.SetOne)
    {
      break;
    }
    if (setTree == null)
    {
      return n;
    }
    SetTree<a>.SetNode setNode = (SetTree<a>.SetNode)s;
    SetTree<a> arg_23_0 = setNode.item3;
    n = setNode.item1;
    s = arg_23_0;
  }
  return ((SetTree<a>.SetOne)s).item;
  return n;
}

وحسنا حتى هذه ليست بالضبط كود 'الصحيح' في C # شروط - ولكن وجود حلقة while(true) يعني أنه لا يمكن أن يكون O (1) على الأقل؛ أما ما هو عليه في الواقع ... حسنا، رأسي يؤلمني كثيرا لمعرفة:)

Answer 4

وتقدم هذه الصفحة ملاحظات قصيرة عن بعض الايجابيات الرئيسية وسلبيات بالنسبة لمعظم مجموعات .NET:

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Answer 5

وليس هناك شيء مثل "تعقيد جمع الصفوف". بدلا من ذلك، عمليات مختلفة على هذه المجموعات لها تعقيدات مختلفة. على سبيل المثال، إضافة عنصر إلى Dictionary<K, V> href="http://msdn.microsoft.com/en-us/library/k7z0zy8k.aspx" rel="nofollow noreferrer"> ...

<اقتباس فقرة>   

... تقترب من O (1) العملية. إذا لا بد من زيادة القدرة على استيعاب العنصر الجديد، يصبح هذا الأسلوب ل<م> O (ن) العملية، حيث n هو Count.

وحين استرجاع عنصر من Dictionary<K, V> ...

<اقتباس فقرة>   

... تقترب من O (1) العملية.

Answer 6

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