مصفوفة جودي

الموسوعة الحرة

في علوم الحاسوب ، تُعدّ مصفوفة جودي تطبيقًا مُحسَّنًا يدويًا من شركة هيوليت-باكارد في أوائل العقد الأول من القرن الحادي والعشرين لشجرة جذرية ذات 256 عنصرًا ، تستخدم أنواعًا متعددة من العقد لتقليل زمن الاستجابة الناتج عن امتلاء خطوط ذاكرة التخزين المؤقت لوحدة المعالجة المركزية . [ 1 ] [ 2 ] وباعتبارها شجرة جذرية مضغوطة، تستطيع مصفوفة جودي تخزين بيانات مُفهرسة بأعداد صحيحة أو سلاسل نصية، والتي قد تكون متفرقة، مع استخدام منخفض نسبيًا للذاكرة وزمن استجابة قراءة منخفض، دون الاعتماد على التجزئة أو موازنة الشجرة، ودون التضحية بترتيب التصفح. [ 3 ] يتناسب زمن الاستجابة لكل عملية طرديًا معيا(سجل⁡ن){\displaystyle O(\log n)}كما هو متوقع من شجرة، فإن العامل الثابت الرئيسي صغير بما يكفي لجعل مصفوفات جودي مناسبة حتى لنطاق البيتا عنصر. [ 4 ] وعند الاقتضاء، يمكن أن تكون أسرع من تطبيقات أشجار AVL ، وأشجار B ، وجداول التجزئة ، أو قوائم التخطي من نفس الفترة الزمنية. [ 3 ]

تاريخ

تم اختراع مصفوفة جودي بواسطة دوغلاس باسكنز على مر السنين التي سبقت عام 2002، وقد سميت على اسم أخته. [ 5 ]

أنواع العقد

بشكل عام، تندرج عقد الشجرة في مصفوفات Judy ضمن إحدى الفئات الثلاث، على الرغم من أن التنفيذ يستخدم اختلافات ظرفية داخل كل فئة: [ 2 ]

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

تُستخدم العقد الخطية للتفرع المنخفض، وعقد الخرائط النقطية للتفرع المتوسط، والعقد غير المضغوطة للتفرع العالي. [ 2 ]

المزايا والعيوب

بفضل تحسينات التخزين المؤقت ، تتميز مصفوفات جودي بالسرعة، خاصةً مع مجموعات البيانات الضخمة جدًا. في بعض المهام التي تتضمن بيانات متسلسلة أو شبه متسلسلة، قد تتفوق مصفوفات جودي على جداول التجزئة، لأن بنية الشجرة الداخلية لمصفوفات جودي، على عكس جداول التجزئة، تحافظ على ترتيب المفاتيح. [ 6 ]

من ناحية أخرى، لا تُناسب مصفوفات جودي جميع أنواع المفاتيح، وتعتمد بشكل كبير على تقسيم الحالات أثناء الترجمة (مما يزيد من حجم الكود المُترجم والجهد المبذول في إعادة ضبطه ليتناسب مع بنية جديدة [ 6 ] )، وتُقدم بعض التنازلات للبنى القديمة التي قد لا تكون ذات صلة بالأجهزة الحديثة، ولا تستغل تقنية SIMD . [ 2 ] وهي مُحسّنة لأداء القراءة على حساب أداء الكتابة. [ 2 ]

انظر أيضاً

مراجع