C# الأشجار الثنائية و القواميس

Question

أنا تكافح مع مفهوم عند استخدام أشجار البحث الثنائية و عند استخدام القواميس.

في تطبيق فعلت القليل من التجربة التي استخدمت C5 المكتبة TreeDictionary (التي أعتقد هو الأحمر-الأسود شجرة البحث الثنائية) ، و ج# القاموس.القاموس كان دائما أسرع في إضافة/العثور على العمليات وأيضا يستخدم دائما أقل مساحة الذاكرة.على سبيل المثال ، في 16809 <int, float> إدخالات القاموس المستخدمة 342 وكالة: حكومة البحرين توافق في حين الشجرة تستخدم 723 وكالة: حكومة البحرين توافق.

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

كما الجانب السؤال ، لا أحد يعرف إذا كان هناك أسرع + أكثر كفاءة الذاكرة بنية البيانات لتخزين <int, float> أزواج القاموس نوع من إما من ذكر الهياكل ؟

Answer 1

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

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

بشكل عام ، تعد القواميس مجرد غلاف فاخر حول مجموعة من القوائم المرتبطة. يمكنك إدخال في القاموس شيء مثل:

LinkedList<Tuple<TKey, TValue>> list =
    internalArray[internalArray % key.GetHashCode()];
if (list.Exists(x => x.Key == key))
    throw new Exception("Key already exists");
list.AddLast(Tuple.Create(key, value));

إذن كذلك تقريبا س (1) العملية. يستخدم القاموس ذاكرة O (internalarray.length + n) ، حيث N هو عدد العناصر في المجموعة.

بشكل عام ، يمكن تنفيذ BSTS على النحو التالي:

• قوائم مرتبطة ، والتي تستخدم مساحة O (n) ، حيث N هي عناصر الأرقام في المجموعة.
• المصفوفات, التي تستخدم o (2^ح - n) المساحة حيث h هي ارتفاع الشجرة و n هو عدد العناصر في المجموعة.
  • نظرًا لأن الأشجار ذات اللون الأسود الأحمر لها ارتفاع محدود من O (1.44 * N) ، يجب أن يكون لتطبيق الصفيف استخدام ذاكرة محددًا حوالي O (2^1.44n - ن)

الاحتمالات هي ، يتم تنفيذ c5 treedictionary باستخدام المصفوفات ، والتي ربما تكون مسؤولة عن المساحة الضائعة.

ما يعطي؟ هل هناك نقطة في المكان الذي تكون فيه BST أفضل من القواميس؟

القواميس لها بعض الخصائص غير المرغوب فيها:

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

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

  • int32 GetHashCode الطريقة حرفيًا فقط return this, ، لذلك سيكون من الصعب عليك العثور على حالة يكون فيها علامة التجزئة مع مفاتيح INT أبطأ من قاموس الأشجار.

أشجار RB لها بعض الخصائص المرغوبة:

• يمكنك العثور على/إزالة عناصر Min و Max في وقت O (log n) ، مقارنة بوقت O (n) باستخدام قاموس.

• إذا تم تنفيذ شجرة كقائمة مرتبطة بدلاً من صفيف ، فإن الشجرة مستخدم أكثر كفاءة من القاموس.

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

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

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

Answer 2

من المنطقي أن تتطلب عقدة الأشجار تخزينًا أكبر من إدخال القاموس. تحتاج عقدة الأشجار الثنائية إلى تخزين القيمة وقطاع الفرعية اليسرى واليسرى. عام Dictionary<TKey, TValue> يتم تنفيذها كجدول التجزئة الذي - أفترض - إما يستخدم قائمة مرتبطة لكل دلو (قيمة بالإضافة إلى مؤشر/مرجع واحد) أو نوع من إعادة التقييم (فقط القيمة). يجب أن يكون لدي نظرة خاطفة في العاكس للتأكد ، لكن لغرض هذا السؤال لا أعتقد أنه من المهم.

كلما كان جدول التجزئة ، أقل كفاءة من حيث التخزين/الذاكرة. إذا قمت بإنشاء جدول التجزئة (القاموس) وتهيئة قدرته إلى مليون ، وملءها فقط بـ 10،000 عنصر ، فأنا متأكد من أنها ستأكل ذاكرة أكبر بكثير من BST مع 10000 عقد.

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

---

إذا كان السؤال هو "لماذا تريد استخدام شجرة ثنائية بدلاً من جدول التجزئة؟" ثم أفضل إجابة IMO هي أن الأشجار الثنائية يتم طلبها في حين أن جداول التجزئة ليست كذلك. يمكنك فقط البحث في جدول التجزئة عن المفاتيح التي تساوي تمامًا شيء ما ؛ باستخدام شجرة ، يمكنك البحث عن مجموعة من القيم ، أو أقرب قيمة ، وما إلى ذلك. هذا تمييز مهم للغاية إذا كنت تقوم بإنشاء فهرس أو شيء مشابه.

Answer 3

يبدو لي أنك تقوم بتحسين سابق لأوانه.

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

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

Answer 4

يجب أن تكون الواجهة الخاصة بشجرة وجدول التجزئة (الذي أظن أنه ما يقام به القاموس) متشابهًا جدًا. دائما تدور حول عمليات البحث الرئيسية.

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

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

Answer 5

أنت لا تقارن "التفاح بالتفاح" ، وسيعطيك BST أمر التمثيل بينما يتيح لك القاموس إجراء بحث على زوج القيمة الرئيسي (في حالتك).

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

Answer 6

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

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

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

باختصار, مع BST مدعومة تخصيص كومة الذاكرة المؤقتة تحصل على أسوأ الأحوال O(log(N)) الوقت مع hashtable تحصل O(N) أسوأ الأحوال الوقت.

BST يأتي بسعر O(log(N)) متوسط الوقت هو أسوأ ذاكرة التخزين المؤقت محلة وأكثر عمليات تخصيص كومة الذاكرة المؤقتة ، ولكن قد الكمون ضمانات حماية من هجمات القاموس و تجزئة الذاكرة.

الجدير بالذكر أن BST هو أيضا موضوع تجزئة الذاكرة على منصات أخرى ، وليس باستخدام ضغط جامع البيانات المهملة.

أما بالنسبة لحجم الذاكرة،.صافي القاموس`2 الفئة هي أكثر كفاءة الذاكرة, لأنه يخزن البيانات خارج كومة قائمة مرتبطة ، فقط بتخزين قيمة تعويض المعلومات.BST إلى كائن مخزن رأس (كل عقدة مثيل فئة على كومة), اثنين من المؤشرات و بعض المعزز البيانات شجرة متوازنة الأشجار.على سبيل المثال, أحمر-أسود شجرة حاجة منطقية تفسر اللون (الأحمر أو الأسود).هذا هو على الأقل 6 كلمات الجهاز, إذا لم أكن مخطئا.لذا كل عقدة في شجرة سوداء على نظام 64 بت هو الحد الأدنى من:

3 عبارة عن رأس = 24 بايت 2 الكلمات للطفل المؤشرات = 16 بايت 1 كلمة color = 8 بايت على الأقل 1 كلمة قيمة 8+ بايت = 24+16+8+8 = 56 بايت (+8 بايت إذا كانت الشجرة يستخدم عقدة الأم المؤشر).

في نفس الوقت, الحجم الأدنى إدخال القاموس سيكون فقط 16 بايت.