عثر أندرو كرابيفين؛ الطالب الجامعي في جامعة “روتجرز”، في خريف عام 2021، على ورقة بحثية عن ذاكرة الكمبيوتر غيرت حياته. حينها، لم يعرها كرابيفين اهتمامًا كبيرًا. ولكن بعد عامين، عندما خصص وقتًا أخيرًا لمراجعة الورقة البحثية كنوع من التسلية أدت جهوده إلى إعادة النظر في أداة شائعة الاستخدام في علوم الكمبيوتر.
جداول التجزئة وذاكرة الكمبيوتر
وكان عنوان البحث “مؤشرات صغيرة” يشير إلى كيانات تشبه الأسهم، يمكنها توجيهك إلى معلومة أو عنصر في ذاكرة الكمبيوتر. سرعان ما ابتكر “كرابيفين” طريقةً محتملةً لتصغير حجم هذه المؤشرات بشكل أكبر. ما يقلل استهلاكها للذاكرة. ولكن لتحقيق ذلك، احتاج إلى طريقة أفضل لتنظيم البيانات التي تشير إليها هذه المؤشرات.
ولجأ إلى نهج شائع لتخزين البيانات يُعرف بجدول التجزئة. لكن في خضم تجاربه، أدرك “كرابيفين” أنه ابتكر نوعًا جديدًا من جداول التجزئة. أسرع من المتوقع، إذ يستغرق وقتًا وخطوات أقل للعثور على عناصر محددة.
وكان مارتن فاراش-كولتون؛ المؤلف المشارك في ورقة “المؤشرات الصغيرة”، وأستاذ “كرابيفين” السابق في جامعة “روتجرز”، متشككًا في البداية بشأن تصميم “كرابيفين” الجديد.
ووفق تقرير موقع “theverge“، الذي اطلعت عليه “عالم التكنولوجيا”؛ فإن جداول التجزئة من أكثر هياكل البيانات دراسةً في علوم الكمبيوتر. وقد بدا هذا التقدم أشبه بالخيال.
ولكن للتأكد، طلب من ويليام كوزماول؛ أحد زملائه الدائمين وأحد المؤلفين المشاركين في الدراسة من جامعة كارنيجي ميلون، الاطلاع على اختراع طالبه. وكان رد فعله مختلفًا.
ويتذكر أنه قال لـ”كرابيفين”: “لم تبتكر جدول تجزئة رائعًا فحسب؛ بل لقد قضت تمامًا على تخمين عمره 40 عامًا”.
وفي ورقة بحثية منشورة في يناير الماضي؛ أثبت كرابيفين، في جامعة كامبريدج، وفاراش كولتون، جامعة نيويورك. أن جدول التجزئة الجديد هذا قادر بالفعل على العثور على العناصر بشكل أسرع ما كان يُعتقد أنه ممكن.
ما جداول التجزئة؟
وقال أليكس كونواي؛ من معهد “كورنيل” للتكنولوجيا في مدينة نيويورك: ” إنها ورقة بحثية مهمة. تُعدّ جداول التجزئة من أقدم هياكل البيانات لدينا. ولا تزال من أكثر الطرق فعالية لتخزين البيانات”. وأضاف: “مع ذلك، لا تزال هناك أسئلة مفتوحة حول كيفية عملها. تجيب هذه الورقة البحثية على بعض هذه الأسئلة بطرق مُدهشة”.
أصبحت جداول التجزئة شائعة الاستخدام في الحوسبة، ويعود ذلك جزئيًا إلى بساطتها وسهولة استخدامها. هذه الجداول مصممة لتمكين المستخدمين من القيام بثلاثة أمور فقط:
- الاستعلام عن عنصر.
- حذفه.
- إدراجه في خانة فارغة.
ويعود تاريخ أول جداول التجزئة إلى أوائل خمسينيات القرن الماضي. وقد درسها علماء الكمبيوتر واستخدموها منذ ذلك الحين.
ومن بين أمور أخرى، أراد الباحثون تحديد حدود السرعة لبعض هذه العمليات. على سبيل المثال، ما مدى السرعة الممكنة لإجراء بحث أو إدراج جديد؟
كيفية عمل جداول التجزئة
ساعد مارتن فاراش كولتون كرابيفين في إثبات أن جدول التجزئة الجديد الخاص به يتناقض مع تخمين قائم منذ فترة طويلة. تعتمد الإجابة عمومًا على مقدار الوقت المستغرق للعثور على مساحة فارغة في جدول التجزئة.
وهذا بدوره يعتمد عادةً على مدى امتلاء جدول التجزئة. يمكن وصف الامتلاء من حيث النسبة المئوية الإجمالية. هذا الجدول ممتلئ بنسبة 50 بالمائة، وهذا الجدول ممتلئ بنسبة 90 بالمائة.
لكن غالبًا ما يتعامل الباحثون مع جداول أكثر امتلاءً بكثير. لذلك، قد يستخدمون بدلاً من ذلك عددًا صحيحًا، يُشار إليه بـ x ، لتحديد مدى قرب جدول التجزئة من الامتلاء بنسبة 100 بالمائة.
وإذا كانت x تساوي 100، فإن الجدول ممتلئ بنسبة 99 بالمائة. إذا كانت x تساوي 1000، فإن الجدول ممتلئ بنسبة 99.9 بالمائة. يوفر مقياس الامتلاء هذا طريقة ملائمة لتقييم المدة التي يجب أن يستغرقها تنفيذ إجراءات مثل الاستعلامات أو عمليات الإدراج.
لطالما عرف الباحثون أنه في بعض جداول التجزئة الشائعة، يتناسب الوقت المتوقع اللازم لإجراء أسوأ عملية إدخال ممكنة. مثل وضع عنصر في آخر خانة فارغة متبقية – طرديًا مع x .
ويقول “كوزماول”: “إذا كان جدول التجزئة لديك ممتلئًا بنسبة 99%، فمن المنطقي أن تضطر إلى البحث في نحو 100 موضع مختلف للعثور على خانة فارغة”.
الفحص الموحد
وفي ورقة بحثية منشورة في عام 1985، أكد أندرو ياو؛ عالم الكمبيوتر، الذي فاز لاحقًا بجائزة “إيه إم تورينج”، أن أفضل طريقة للعثور على عنصر فردي أو مساحة فارغة بين جداول التجزئة ذات مجموعة خصائص محددة هي البحث في المساحات المحتملة عشوائيًا.
وهي طريقة معروفة باسم “الفحص الموحد”. كما ذكر أنه في أسوأ الأحوال، عند البحث عن آخر مساحة فارغة متبقية، لا يمكن أبدًا الحصول على قيمة أفضل من x . على مدار أربعين عامًا، افترض معظم علماء الكمبيوتر صحة تخمين “ياو”.
ولم يتردد كرابيفين في اتباع الحكمة التقليدية لسبب بسيط هو جهله بها. قال: “لقد فعلت هذا دون أن أعرف بتخمين ياو”. أدت استكشافاته باستخدام المؤشرات الصغيرة إلى نوع جديد من جداول التجزئة، نوع لا يعتمد على الفحص المنتظم.
وبالنسبة لجدول التجزئة الجديد هذا، فإن الوقت اللازم للاستعلامات والإدخالات في أسوأ الحالات يتناسب طرديًا مع (log x ) 2 – أسرع بكثير من x . تناقض هذه النتيجة بشكل مباشر مع تخمين ياو. ساعد فاراش-كولتون وكوزماول كرابيفين في إثبات أن (log x ) 2 هو الحد الأمثل الذي لا يُقهر لفئة جداول التجزئة الشائعة التي كتب عنها ياو.
وقال جاي بليلوش من جامعة كارنيجي ميلون: “هذه النتيجة جميلة لأنها تعالج وتحل مثل هذه المشكلة الكلاسيكية”.
قد لا تفضي نتائج الفريق إلى تطبيقات فورية في ذاكرة الكمبيوتر. لكن هذا ليس كل ما يهم، كما قال كونواي. “من المهم فهم هذه الأنواع من هياكل البيانات بشكل أفضل. لا أحد يعلم متى ستفسح نتيجة كهذه المجال أمام شيء يمكّنك من تحسين أدائك العملي.”