العودة للوحة التحكم

QudahWay IR

Skip Pointers & Skip Lists | تسريع الدمج بالقفزات

Slide 01
Slide 01
Slide 02
Slide 02
⏪ التذكير بالدمج العادي (Basic Merge)
في الطريقة العادية بـ simultaneouslyنمشي على القائمتين مع بعض. هاض باخد وقت خطي Linear Time.

التكلفة (Cost): إذا القائمة الأولى طولها m والثانية n، رح نحتاج عمليات بالأقصى O(m+n).
السؤال: Can we do better?
الجواب: Yes!
Slide 03
Slide 03
⏭️ تعزيز القوائم بإضافة قفزات (Skip Pointers)
كيف رح نسرع البحث؟ التفاصيل كالتالي:

ليش؟ (Why?): عشان نعمل تخطي (Skip) للملفات اللي أصلاً ما رح تكون ضمن نتيجة البحث النهائية.
كيف؟ (How?): هاض الإشي بنجهزه وإحنا بنبني الفهرس أصلاً at indexing time. القفزات بتكون جاهزة قبل البحث ومزروعة في القوائم.
وين بنحطهم؟ (Where?): رح نجاوب عليه في السلايدات القادمة بناءً على مقاييس أداء ومعادلة حسابية.
Slide 04
Slide 04
💻 كيف الخوارزمية بتشتغل برمجياً؟
هاض الـ Pseudo-code بيشرح خوارزمية الـ Intersection للقفزات بشكل متسلسل:

1. التطابق: إذا الرقمين متساويين، بنخزنه بالنتيجة وبنحرك الاثنين.
2. المقارنة: إذا رقم p1 أصغر، بنسأل: هل في قفزة عن طريق hasSkip(p1) توديني لرقم أصغر أو يساوي p2؟
3. القفز (Skip): طالما الجواب "نعم صحيح"، بنضل نقفز باستخدام skip(p1). وإلا بنمشي خطوة واحدة العادية next(p1). والمنطق بينطبق عالجهتين!
Slide 05
Slide 05
🔎 مثال عملي على معالجة الاستعلام
نشوف مع بعض بالمثال كيف الخوارزمية قللت العمليات:

الخطوة السابقة: لنفرض إننا وصلنا عند الرقم 8 ولقيناه متطابق، فبنسجله وبنتقدم للي بعده.
الوضع الحالي: الرقم اللي فوق 41 واللي تحت 11. الـ 11 أصغر بالمقارنة فبدنا نحركه.
القفزة (Skip!): الـ 11 عنده قفزة للـ 31. والـ 31 أقل من الـ 41 اللي بندور عليه فوق. إذن ليش نمشي حبة حبة على الأرقام بالنص intervening postings؟ بنعمل قفزة مباشرة للـ 31 🚀.
Slide 06
Slide 06
تمرين
هاض التمرين بورينا إن القفزات بتنعمل في القائمتين حسب الحاجة لتسريع الوصول:

السيناريو لتكملة الحل: عنا حالياً 31 و 41، الـ 31 لسه أصغر من 41 فبنمشي للـ 41 تحت لأنها النقطة التالية.
أخيراً بنوصل وتطابق الـ 41 فوق وتحت. تخيل المجهود الكبير والوقت الضائع للكمبيوتر لو قارنا الأرقام بيناتهم بدون الـ Skip Pointer!
Slide 07
Slide 07
⚖️ الموازنة: وين نحط القفزات؟
سؤال المليون: شو الطول المناسب للقفزة؟ عنا حالتين:

قفزات كثيرة (بطول قصير): فرصة القفز بتكون كبيرة، لكن رح نضيع وقت وإحنا بنقارن المؤشرات نفسها مع الرقم اللي بندور عليه وبصير الكود مكلف حسابياً بدون فايدة.
قفزات قليلة (بطول كبير): ما في مقارنات كثيرة للمؤشرات، لكن مسافات القفز بتصير طويلة جداً، وفرصة إن القفزة تنجح بالعبور بتصير نادرة.
Slide 08
Slide 08
⚙️ الحل النهائي (Heuristic)
عشان نحل مشكلة الفجوة بالمقارنة، استخدمنا معادلة رياضية استدلالية:

القاعدة الذهبية الاستدلالية: إذا كان طول القائمة L، بنحط قفزة كل √L. (مثلاً: قائمة طولها 100، بنحط قفزة كل 10 أرقام بانتظام).
المشكلة 1: هاض بيطنش كلياً "توزيع" كلمات البحث distribution of query terms. بعض الكلمات بينبحث عنها أكثر من غيرها.
المشكلة 2: هاض الحل سهل لو كان الفهرس ثابت Static وحجمه ما بتغير من البداية. لكن لو بيتحدث باستمرار (الـ L بيتغير)، رح نضطر نعيد حساب وتعديل وتوزيع أماكن القفزات وهاض بياخد مجهود وتكلفة كبيرة جداً harder if L keeps changing.