شجرة المصفوفة المجزأة
في علم الحاسوب ، تُعدّ شجرة المصفوفة المُجزأة ( HAT ) بنية بيانات ديناميكية للمصفوفات ، نشرها إدوارد سيتارسكي عام 1996، [ 1 ] حيث تحتفظ بمصفوفة من أجزاء الذاكرة المنفصلة (أو "الأوراق") لتخزين عناصر البيانات، على عكس المصفوفات الديناميكية البسيطة التي تحتفظ ببياناتها في منطقة ذاكرة متصلة واحدة. هدفها الأساسي هو تقليل نسخ العناصر نتيجةً لعمليات تغيير حجم المصفوفة التلقائية، وتحسين أنماط استخدام الذاكرة.
بينما تهدر المصفوفات الديناميكية البسيطة القائمة على التوسع الهندسي مساحة خطية (Ω( n ))، حيث n هو عدد عناصر المصفوفة ، فإن أشجار المصفوفات المجزأة تهدر مساحة تخزين من رتبة O ( √n ) فقط. يسمح تحسين الخوارزمية بالتخلص التام من نسخ البيانات، على حساب زيادة المساحة المهدرة.
يُمكنه الوصول إلى البيانات في زمن ثابت ( O (1))، وإن كان أبطأ قليلاً من المصفوفات الديناميكية البسيطة. يُحقق هذا الخوارزمية أداءً مُعدلاً O(1) عند إضافة سلسلة من العناصر إلى نهاية شجرة مصفوفة مُجزأة. وعلى عكس ما يوحي به اسمه، فهو لا يستخدم دوال التجزئة .
التعريفات
كما عرّفها سيتارسكي، تحتوي شجرة المصفوفة المُجزأة على دليل رئيسي يتضمن عددًا من المصفوفات الطرفية يساوي قوة العدد اثنين . جميع المصفوفات الطرفية لها نفس حجم الدليل الرئيسي. يشبه هذا الهيكل ظاهريًا جدول التجزئة مع سلاسل تصادم قائمة على المصفوفات، وهو أساس تسمية شجرة المصفوفة المُجزأة . يمكن لشجرة مصفوفة مُجزأة كاملة أن تحتوي على m² عنصرًا، حيث m هو حجم الدليل الرئيسي. [ 1 ] يُمكّن استخدام قوى العدد اثنين من معالجة البيانات الفيزيائية بشكل أسرع من خلال عمليات البت بدلًا من العمليات الحسابية للقسمة والباقي [ 1 ] ، ويضمن أداءً ثابتًا ( O(1)) لعملية الإلحاق في حالة وجود نسخ عرضية للمصفوفة العامة أثناء التوسيع.
التوسعات وتقليص الحجم
في مخطط التوسيع الهندسي الديناميكي المعتاد للمصفوفات ، يُعاد تخصيص المصفوفة كوحدة متسلسلة كاملة من الذاكرة بحجم مضاعف لحجمها الحالي (ثم تُنقل البيانات بالكامل إلى الموقع الجديد). يضمن هذا الأسلوب عمليات مُستهلكة بتكلفة مساحة مهدرة قدرها O(n)، حيث تُملأ المصفوفة المُوسّعة إلى نصف سعتها الجديدة.
عندما تمتلئ شجرة المصفوفة المُجزأة، يجب إعادة هيكلة دليلها وأوراقها إلى ضعف حجمها السابق لاستيعاب عمليات الإلحاق الإضافية. ثم تُنقل البيانات المخزنة في الهيكل القديم إلى المواقع الجديدة. بعد ذلك، تُخصص ورقة واحدة جديدة فقط وتُضاف إلى المصفوفة العلوية، التي تمتلئ بالتالي إلى ربع سعتها الجديدة فقط. لم تُخصص جميع الأوراق الإضافية بعد، ولن تُخصص إلا عند الحاجة، مما يُهدر مساحة تخزين مقدارها O ( √n ) فقط. [ 2 ]
توجد عدة بدائل لتقليل الحجم: فعندما يمتلئ مصفوفة التجزئة بمقدار ثُمنها، يمكن إعادة هيكلتها إلى مصفوفة تجزئة أصغر حجمًا، نصف ممتلئة؛ وخيار آخر هو تحرير مصفوفات الأوراق غير المستخدمة فقط، دون تغيير حجم الأوراق. تشمل التحسينات الإضافية إضافة أوراق جديدة دون تغيير الحجم مع توسيع مصفوفة الدليل حسب الحاجة، ربما من خلال التوسيع الهندسي. سيؤدي هذا إلى إلغاء الحاجة إلى نسخ البيانات تمامًا، على حساب جعل المساحة المهدرة من رتبة O ( n )، مع ثابت صغير، وإجراء إعادة الهيكلة فقط عند الوصول إلى حد معين من الحمل الزائد. [ 1 ]
هياكل البيانات ذات الصلة
| نظرة خاطفة (فهرس) | قم بالتعديل (الإدراج أو الحذف) في … | مساحة زائدة، متوسط | |||
|---|---|---|---|---|---|
| بداية | نهاية | وسط | |||
| قائمة مرتبطة | Θ( n ) | Θ(1) | Θ(1)، العنصر النهائي المعروف؛ Θ( n )، عنصر نهائي غير معروف | Θ( n ) | Θ( n ) |
| المصفوفة | Θ(1) | غير متوفر | غير متوفر | غير متوفر | 0 |
| مصفوفة ديناميكية | Θ(1) | Θ( n ) | Θ(1) المستهلكة | Θ( n ) | Θ( n ) [ 3 ] |
| شجرة متوازنة | Θ(log n) | Θ(log n) | Θ(log n ) | Θ(log n ) | Θ( n ) |
| قائمة الوصول العشوائي | Θ(log n) [ 4 ] | Θ(1) | غير متوفر [ 4 ] | غير متوفر [ 4 ] | Θ( n ) |
| شجرة المصفوفة المجزأة | Θ(1) | Θ( n ) | Θ(1) المستهلكة | Θ( n ) | Θ(√ n ) |
قدّم برودنيك وآخرون [ 5 ] خوارزمية مصفوفة ديناميكية ذات نمط هدر مساحة مشابه لأشجار المصفوفات المُجزأة. يحتفظ تطبيق برودنيك بمصفوفات الأوراق المُخصصة مسبقًا، مع دالة حساب عناوين أكثر تعقيدًا مقارنةً بأشجار المصفوفات المُجزأة.
انظر أيضاً
مراجع
- 1 2 3 4 سيتارسكي، إدوارد (سبتمبر 1996). "زقاق الخوارزميات - HATs: أشجار المصفوفات المجزأة" . مجلة دكتور دوب . المجلد 21، العدد 11.
- ↑ كاتاجاينن، يركي (5-8 يونيو 2016). "المصفوفات الديناميكية الفعالة في أسوأ الحالات عمليًا" . في: كوليكوف، ألكسندر س.؛ غولدبيرغ، أندرو ف. (محرران). الخوارزميات التجريبية . الندوة الدولية الخامسة عشرة حول الخوارزميات التجريبية، SEA 2016. سلسلة محاضرات في علوم الحاسوب. المجلد 9685. سانت بطرسبرغ، روسيا : سبرينغر ساينس + بيزنس ميديا . ص 173. doi : 10.1007/978-3-319-38851-9_12 . ISBN 978-3-319-38851-9.
- ↑ برودنيك، أندريه؛ كارلسون، سفانتي؛ سيدجويك، روبرت ؛ مونرو، جي آي؛ ديمين، إي دي (1999)، المصفوفات القابلة لتغيير الحجم في الوقت والمساحة الأمثلين (تقرير فني CS-99-09) (PDF) ، قسم علوم الحاسوب، جامعة واترلو
- 1 2 3 كريس أوكازاكي (1995). "قوائم الوصول العشوائي الوظيفية البحتة". وقائع المؤتمر الدولي السابع حول لغات البرمجة الوظيفية وهندسة الحاسوب : 86-95 . doi : 10.1145/224164.224187 .
- ↑ برودنيك، أندريه؛ كارلسون، سفانتي؛ سيدجويك، روبرت ؛ مونرو، جي آي؛ ديمين، إي دي (1999)، "المصفوفات القابلة لتغيير الحجم في الوقت والمساحة الأمثلين" (ملف PDF) ، التقرير الفني CS-99-09 ، قسم علوم الحاسوب، جامعة واترلو
- المصفوفات