التجميع الأولي

في برمجة الحاسوب ، يُعدّ التكتل الأولي ظاهرة تُسبب تدهورًا في أداء جداول التجزئة ذات الاستكشاف الخطي . تنص هذه الظاهرة على أنه عند إضافة عناصر إلى جدول تجزئة ذي استكشاف خطي، فإنها تميل إلى التكتل معًا في سلاسل طويلة (أي مناطق متصلة طويلة في جدول التجزئة لا تحتوي على خانات فارغة). إذا كان جدول التجزئة عند عامل تحميل قدره${\displaystyle 1-1/x}$لبعض المعلمات${\displaystyle x\geq 2}$ثم الطول المتوقع للتسلسل الذي يحتوي على عنصر معين${\displaystyle u}$يكون${\displaystyle \Theta (x^{2})}$وهذا يؤدي إلى استغراق عمليات الإضافة والاستعلامات السلبية الوقت المتوقع${\displaystyle \Theta (x^{2})}$في جدول تجزئة ذي فحص خطي.

للتكتل الأولي سببان:

• الفائز يستمر بالفوز: كلما طالت سلسلة العناصر، زادت احتمالية تراكم عناصر إضافية فيها. وهذا يُنشئ حلقة تغذية راجعة إيجابية تُساهم في تأثير التكتل. مع ذلك، لا يُؤدي هذا وحده إلى الانفجار التربيعي. ^{[ 1 ] [ 2 ]}
• ربط السلاسل: قد لا يؤدي إدخال عنصر واحد إلى زيادة طول السلسلة التي ينتمي إليها بمقدار عنصر واحد فحسب، بل قد يؤدي أيضًا إلى ربط سلسلتين طويلتين نسبيًا. وهذا ما يسبب التضخم التربيعي في طول السلسلة المتوقع. ^{[ 1 ]}

هناك طريقة أخرى لفهم التجميع الأولي وهي فحص الانحراف المعياري لعدد العناصر التي تُجزأ إلى منطقة معينة داخل جدول التجزئة. ^{[ 2 ]} لنفترض منطقة فرعية من جدول التجزئة بحجم${\displaystyle x^{2}}$العدد المتوقع للعناصر التي يتم تجزئة بياناتها في المنطقة هو${\displaystyle (1-1/x)x^{2}=x^{2}-x}$من ناحية أخرى، فإن الانحراف المعياري لعدد هذه العناصر هو${\displaystyle \Theta (x)}$ويترتب على ذلك أنه باحتمال${\displaystyle \Omega (1)}$، سيتجاوز عدد العناصر التي يتم تجزئتها في المنطقة حجمها${\displaystyle x^{2}}$من المنطقة. وهذا يعني بشكل بديهي أن المناطق ذات الحجم${\displaystyle \Theta (x^{2})}$غالباً ما يحدث تجاوز في المناطق الأكبر حجماً، بينما لا يحدث ذلك عادةً. تُستخدم هذه الفكرة البديهية كنقطة انطلاق للتحليلات الرسمية للتكتل الأولي. ^{[ 2 ] [ 3 ] [ 4 ]}

يؤدي التجميع الأساسي إلى تدهور الأداء لكل من عمليات الإدخال والاستعلامات في جدول التجزئة ذي البحث الخطي. يجب أن تنتقل عمليات الإدخال إلى نهاية التشغيل، وبالتالي تستغرق الوقت المتوقع.${\displaystyle \Theta (x^{2})}$[ ^{1 ]} يجب أن تصل الاستعلامات السلبية (أي الاستعلامات التي تبحث عن عنصر تبين أنه غير موجود) إلى نهاية عملية التنفيذ، وبالتالي تستغرق أيضًا الوقت المتوقع ^.${\displaystyle \Theta (x^{2})}$^{[ 1 ]} يمكن أن تنتهي الاستعلامات الإيجابية بمجرد العثور على العنصر المطلوب. ونتيجة لذلك، فإن الوقت المتوقع للاستعلام عن عنصر عشوائي في جدول التجزئة هو${\displaystyle \Theta (x)}$^{[ 1 ]} ومع ذلك ، تستغرق الاستعلامات الإيجابية للعناصر المُدرجة حديثًا (مثل عنصر تم إدراجه للتو) الوقت المتوقع${\displaystyle \Theta (x^{2})}$[ ^{1 ]​}

تنطبق هذه الحدود أيضًا على البحث الخطي مع الحذف المؤجل (أي استخدام علامات الحذف)، طالما يتم إعادة بناء جدول التجزئة (ومسح علامات الحذف) بشكل شبه متكرر. يكفي إجراء إعادة البناء هذه مرة واحدة على الأقل كل${\displaystyle n/(2x)}$الإضافات. ^{[ 2 ]}

تصف العديد من الكتب الدراسية تأثير "الفائز يستمر في الفوز" (حيث كلما طالت السلسلة، زادت احتمالية تراكم عناصر إضافية فيها) باعتباره السبب الوحيد للتكتل الأولي. ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]} ومع ذلك، وكما أشار كنوت، ^{[ 1 ]} فإن هذا ليس السبب الرئيسي للتكتل الأولي.

تذكر بعض الكتب الدراسية أن الوقت المتوقع للحصول على رد إيجابي هو${\displaystyle \Theta (x)}$[ ^{11 ] [ 12 ]، مع} الاستشهاد عادةً بكنوث. ^{[ 1 ]} ينطبق هذا على الاستعلام عن عنصر عشوائي . مع ذلك، قد تستغرق بعض الاستعلامات الإيجابية أوقات تشغيل متوقعة أطول بكثير. على سبيل المثال، إذا قام شخص ما بإدراج عنصر ثم استعلم عن هذا العنصر مباشرةً، فسيستغرق الاستعلام نفس الوقت الذي استغرقه الإدراج، وهو${\displaystyle \Theta (x^{2})}$في انتظار ذلك.

يُعدّ البحث الخطي المرتب ^{[ 13 ]} (والذي يُشار إليه غالبًا باسم تجزئة روبن هود ^{[ 14 ]} ) أسلوبًا لتقليل تأثير التجميع الأولي على الاستعلامات. يقوم البحث الخطي المرتب بترتيب العناصر داخل كل عملية تشغيل وفقًا لتجزئتها. وبالتالي، يمكن إنهاء الاستعلام بمجرد مصادفة أي عنصر تكون تجزئته أكبر من تجزئته للعنصر المطلوب الاستعلام عنه. ينتج عن ذلك أن تستغرق الاستعلامات الإيجابية والسلبية الوقت المتوقع.${\displaystyle O(x)}$.

التجزئة المقبرة هي نوع من أنواع البحث الخطي المرتب، تُزيل التأثيرات التقاربية للتجميع الأولي لجميع العمليات. ^{[ 2 ]} تترك التجزئة المقبرة فجوات استراتيجية داخل عمليات التشغيل، يمكن لعمليات الإدخال اللاحقة الاستفادة منها. تُضاف هذه الفجوات، التي يمكن اعتبارها بمثابة شواهد قبور (مثل تلك التي تُنشئها عمليات الحذف الكسولة )، إلى الجدول أثناء عمليات إعادة البناء شبه المنتظمة. تُسرّع هذه الفجوات عمليات الإدخال التي تتم حتى حدوث عملية إعادة البناء شبه المنتظمة التالية. تستغرق كل عملية في جدول التجزئة المقبرة الوقت المتوقع.${\displaystyle O(x)}$.

توصي العديد من المصادر باستخدام الاستكشاف التربيعي كبديل للاستكشاف الخطي الذي يتجنب تجريبياً آثار التجميع الأولي.