2. القوائم المعتمدة على المصفوفات
في هذا الفصل، سندرس تطبيقات واجهتَي List وQueue التي تُخزَّن فيها البيانات الأساسية في مصفوفة تُدعى المصفوفة الخلفية (backing array). يلخِّص الجدول التالي أزمنة تنفيذ العمليات لبنى البيانات المعروضة في هذا الفصل:
| / | / | |
|---|---|---|
| ArrayStack | ||
| ArrayDeque | ||
| DualArrayDeque | ||
| RootishArrayStack |
للبنى التي تعمل بتخزين بياناتها في مصفوفة واحدة مزايا وقيود مشتركة كثيرة:
- توفِّر المصفوفات وصولًا بزمن ثابت إلى أي قيمة فيها. وهذا ما يتيح لعمليتَي و أن تنفَّذا بزمن ثابت.
- ليست المصفوفات ديناميكية إلى حدٍّ كبير. فإضافة عنصر قرب منتصف قائمة أو إزالته يستلزم إزاحة عدد كبير من عناصر المصفوفة لإفساح المجال للعنصر المُضاف حديثًا أو لملء الفراغ الذي نتج عن حذف العنصر. ولهذا تعتمد أزمنة تنفيذ عمليتَي و على و .
- لا يمكن للمصفوفات أن تتوسَّع أو تنكمش. فحين يتجاوز عدد عناصر بنية البيانات حجم المصفوفة الخلفية، لا بد من تخصيص مصفوفة جديدة ونسخ بيانات المصفوفة القديمة إليها. وهذه عملية مكلفة.
النقطة الثالثة مهمة. فأزمنة التنفيذ المذكورة في الجدول أعلاه لا تتضمَّن التكلفة المرتبطة بنمو المصفوفة الخلفية وانكماشها. سنرى أنَّ التكلفة، عند إدارتها بعناية، لا تضيف الكثير إلى تكلفة العملية المتوسطة. وبشكل أدق، إذا بدأنا ببنية بيانات فارغة ونفَّذنا أي تسلسل من عملية من أو ، فإنَّ التكلفة الكلية لنمو المصفوفة الخلفية وانكماشها، على امتداد تسلسل العمليات الـ كاملًا، هي . فعلى الرغم من أنَّ بعض العمليات المنفردة أغلى، فإنَّ التكلفة المُستهلكة (amortized)، عند توزيعها على عمليات الـ جميعًا، لا تتجاوز لكل عملية.
الأقسام الفرعية
2.1 ArrayStack: عمليات مكدّس سريعة باستخدام مصفوفة
الأقسام الفرعية
2.1 ArrayStack: عمليات مكدّس سريعة باستخدام مصفوفة
يطبِّق ArrayStack واجهة القائمة (List) باستخدام مصفوفة تُدعى المصفوفة الخلفية. ويُخزَّن عنصر القائمة ذي الفهرس في . وفي معظم الأوقات تكون أكبر من الحجم المطلوب تمامًا، لذا يُستخدم عدد صحيح لتتبُّع عدد العناصر المُخزَّنة فعليًا في . وبهذه الطريقة، تُخزَّن عناصر القائمة في ,..., ، ودائمًا ما يتحقَّق .
T[] a;
int n;
int size() {
return n;
}
2.1.1 الأساسيات
الوصول إلى عناصر ArrayStack وتعديلها باستخدام و أمرٌ بديهي. فبعد إجراء فحص الحدود (bounds-checking) اللازم، نكتفي بإرجاع أو تعيينه على التوالي.
T get(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
return a[i];
}
T set(int i, T x) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
T y = a[i];
a[i] = x;
return y;
}
يوضِّح الشكل 2.1 عمليتي إضافة العناصر إلى ArrayStack وإزالتها منها. ولتنفيذ عملية نتحقَّق أولًا مما إذا كانت ممتلئة بالفعل. وإن كان الأمر كذلك، نستدعي الدالة لزيادة حجم . وسيُناقَش لاحقًا كيف يُنفَّذ . يكفي في الوقت الحالي أن نعلم أنَّه بعد استدعاء ، يمكننا التأكُّد من . وبانتهاء هذا الأمر، نزيح الآن العناصر إلى اليمين بموضع واحد لإفساح المجال لـ ، ونجعل مساويةً لـ ، ونزِيد .
void add(int i, T x) {
if (i < 0 || i > n) throw new IndexOutOfBoundsException();
if (n + 1 > a.length) resize();
for (int j = n; j > i; j--)
a[j] = a[j-1];
a[i] = x;
n++;
}
إذا تجاهلنا تكلفة الاستدعاء المحتمل لـ ، فإنَّ تكلفة عملية تتناسب مع عدد العناصر التي علينا إزاحتها لإفساح المجال لـ . وعليه فإنَّ تكلفة هذه العملية (مع تجاهل تكلفة تغيير حجم ) هي . وتنفيذ عملية مشابه. فنزيح العناصر إلى اليسار بموضع واحد (مع الكتابة فوق ) وننقص قيمة . وبعد ذلك نتحقَّق مما إذا كان قد أصبح أصغر بكثير من عبر التحقُّق مما إذا كان . وإن كان الأمر كذلك، نستدعي لتقليل حجم .
T remove(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
T x = a[i];
for (int j = i; j < n-1; j++)
a[j] = a[j+1];
n--;
if (a.length >= 3*n) resize();
return x;
}
إذا تجاهلنا تكلفة الدالة ، فإنَّ تكلفة عملية تتناسب مع عدد العناصر التي نزيحها، وهي .
2.1.2 النمو والانكماش
الدالة مباشرة إلى حدٍّ كبير؛ فهي تخصِّص مصفوفة جديدة حجمها وتنسخ عناصر الخاصة بـ إلى أول موضعًا في ، ثم تجعل مساويةً لـ . وعليه، بعد استدعاء ، يكون .
void resize() {
T[] b = newArray(Math.max(n*2,1));
for (int i = 0; i < n; i++) {
b[i] = a[i];
}
a = b;
}
تحليل التكلفة الفعلية لعملية أمرٌ سهل. فهي تخصِّص مصفوفة حجمها وتنسخ عناصر الخاصة بـ إلى . وهذا يستغرق من الوقت. وكان تحليل زمن التنفيذ في القسم السابق يتجاهل تكلفة الاستدعاءات لـ . وفي هذا القسم نحلِّل هذه التكلفة باستخدام تقنية تُعرف باسم التحليل المُستهلك (amortized analysis). وهذه التقنية لا تحاول تحديد تكلفة تغيير الحجم أثناء كل عملية و على حدة، بل تأخذ في الحسبان تكلفة جميع استدعاءات خلال تسلسل من استدعاءً لـ أو . وعلى وجه التحديد، سنبيِّن ما يلي: المُلمَّة 2.1 إذا أُنشئ ArrayStack فارغ ونُفِّذ أي تسلسل من استدعاءً لـ و ، فإنَّ الزمن الكلي المستغرق في جميع استدعاءات هو .
البرهان. سنبيِّن أنَّه في كل مرة يُستدعى فيها يكون عدد الاستدعاءات لـ أو منذ آخر استدعاء لـ لا يقل عن . وعليه، إذا كانت تدل على قيمة أثناء الاستدعاء رقم لـ ، و تدل على عدد استدعاءات ، فإنَّ العدد الكلي للاستدعاءات لـ أو يكون لا يقل عن
وهو ما يُعادل
ومن جهة أخرى، فإنَّ الزمن الكلي المستغرق في جميع استدعاءات هو
إذ لا يزيد عن . ولم يتبقَّ سوى أن نبيِّن أنَّ عدد الاستدعاءات لـ أو بين الاستدعاء رقم والاستدعاء رقم لـ لا يقل عن .
هناك حالتان يجب مراعاتهما. في الحالة الأولى، يُستدعى من لأنَّ المصفوفة الخلفية ممتلئة، أي . فلننظر إلى الاستدعاء السابق لـ : فبعد ذلك الاستدعاء كان حجم هو ، لكن عدد العناصر المُخزَّنة في لم يكن يتجاوز . أما الآن فعدد العناصر المُخزَّنة في هو ، لذا لا بد أن يكون هناك ما لا يقل عن استدعاءً لـ منذ الاستدعاء السابق لـ . أما الحالة الثانية فتحدث عندما يُستدعى من لأنَّ . أيضًا، فبعد الاستدعاء السابق لـ كان عدد العناصر المُخزَّنة في لا يقل عن .2.1 والآن هناك عنصرًا مُخزَّنًا في . وعليه، فإنَّ عدد عمليات منذ آخر استدعاء لـ لا يقل عن
في كلتا الحالتين، يكون عدد الاستدعاءات لـ أو التي تقع بين الاستدعاء رقم لـ والاستدعاء رقم لـ لا يقل عن ، كما هو مطلوب لإتمام البرهان.
2.1.3 الملخَّص تلخِّص المبرهنة التالية أداء ArrayStack: المبرهنة 2.1 يطبِّق ArrayStack واجهة القائمة (List). ومع تجاهل تكلفة الاستدعاءات لـ ، يدعم ArrayStack العمليتين * و في لكل عملية؛ وعمليتَي و في لكل عملية. * وعلاوة على ذلك، فإنَّ البدء من ArrayStack فارغ وتنفيذ أي تسلسل من عملية من و ينتج عن ذلك كليًا من الزمن المستغرق في جميع استدعاءات .
يُعدّ ArrayStack طريقةً كفؤة لتنفيذ مكدّس (Stack). وعلى وجه التحديد، يمكننا تنفيذ بوصفه و بوصفه ، وفي هذه الحالة تعمل هاتان العمليتان بزمن مُستهلك قدره .
الحواشي
....2.1 إنَّ الواردة في هذه الصيغة تأخذ في الحسبان الحالة الخاصة التي تحدث عندما يكون و . opendatastructures.org
2.2 FastArrayStack: ArrayStack مُحسَّن
معظم العمل الذي يؤديه ArrayStack ينطوي على إزاحة البيانات (بواسطة و ) ونسخها (بواسطة ). وفي التنفيذات المعروضة أعلاه، جرى ذلك باستخدام حلقات . ويتبيَّن أنَّ كثيرًا من بيئات البرمجة تملك دوالَّ خاصة شديدة الكفاءة في نسخ كتل البيانات ونقلها. ففي لغة C توجد الدالتان و . وفي لغة C++ توجد خوارزمية . وفي Java هناك الدالة .
void resize() {
T[] b = newArray(Math.max(2*n,1));
System.arraycopy(a, 0, b, 0, n);
a = b;
}
void add(int i, T x) {
if (i < 0 || i > n) throw new IndexOutOfBoundsException();
if (n + 1 > a.length) resize();
System.arraycopy(a, i, a, i+1, n-i);
a[i] = x;
n++;
}
T remove(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
T x = a[i];
System.arraycopy(a, i+1, a, i, n-i-1);
n--;
if (a.length >= 3*n) resize();
return x;
}
عادةً ما تكون هذه الدوال محسَّنة إلى حدٍّ كبير، وقد تستخدم حتى تعليمات آلة خاصة قادرة على إنجاز هذا النسخ بسرعة أكبر بكثير مما نستطيع إنجازه باستخدام حلقة . ورغم أنَّ استخدام هذه الدوال لا يخفض أزمنة التنفيذ من الناحية المقامية (asymptotic)، إلا أنه قد يظل تحسينًا يستحق العناء. ففي تنفيذات Java هنا، أضاف استخدام الدالة الأصلية تحسينات في السرعة بمعامل يتراوح بين 2 و3، تبعًا لأنواع العمليات المنفَّذة. وقد تختلف النتائج لديك. opendatastructures.org
2.3 ArrayQueue: طابور قائم على مصفوفة
الأقسام الفرعية
2.3 ArrayQueue: طابور قائم على مصفوفة
في هذا القسم، نقدِّم بنية بيانات ArrayQueue التي تنفِّذ طابورًا من نوع FIFO (أول داخل أول خارج)؛ إذ تُزال العناصر من الطابور (باستخدام عملية ) بالترتيب نفسه الذي أُضيفت به (باستخدام عملية ). ولاحظ أنَّ ArrayStack خيارٌ سيئ لتنفيذ طابور FIFO. فهو ليس خيارًا جيدًا لأننا سنضطر إلى اختيار أحد طرفي القائمة لإضافة العناصر ثم إزالة العناصر من الطرف الآخر. ويجب أن تعمل إحدى العمليتين على رأس القائمة، ما يستلزم استدعاء أو بقيمة . وهذا يعطي زمن تنفيذ يتناسب مع . ولتحقيق تنفيذ فعَّال للطابور قائم على مصفوفة، نلاحظ أولًا أنَّ المشكلة ستكون سهلة لو كانت لدينا مصفوفة لا نهائية . يمكننا أن نحتفظ بفهرس واحد يتتبَّع العنصر التالي الذي ستُزال قيمته، وبعدد صحيح يعدّ عناصر الطابور. وستُخزَّن عناصر الطابور دائمًا في
في البداية، تُضبَط كلٌّ من و على 0. ولإضافة عنصر، نضعه في ونزِيد . ولإزالة عنصر، نزيله من ، ونزِيد ، وننقص .
بالطبع، تكمن مشكلة هذا الحل في أنه يحتاج مصفوفة لا نهائية. يحاكي ArrayQueue ذلك باستخدام مصفوفة منتهية والحساب ثنائي الباقي (modular arithmetic). وهذا هو نوع الحساب المستخدم عند الحديث عن وقت اليوم. فمثلًا، الساعة 10:00 مضافًا إليها خمس ساعات تعطي 3:00. وصياغةً رسمية، نقول إنَّ
نقرأ الجزء الأخير من هذه المعادلة على أنَّ «15 مُتماثلة (congruent) مع 3 modulo 12.» ويمكن أيضًا أن نتعامل مع كمعامل ثنائي، بحيث
بشكل أعمَّ، لعدد صحيح و عدد صحيح موجب ، يكون هو العدد الصحيح الوحدي الذي يحقِّق لأجل عدد صحيح ما . وبعبارة أقل رسمية، فإن القيمة هي الباقي الذي نحصل عليه عند قسمة على . وفي كثير من لغات البرمجة، ومنها Java، يُمثَّل معامل بالرمز symbol.2.2. ويكون الحساب ثنائي الباقي مفيدًا لمحاكاة مصفوفة لا نهائية، لأنَّ يعطي دائمًا قيمة في المجال . وباستخدام الحساب ثنائي الباقي يمكننا تخزين عناصر الطابور في مواضع المصفوفة
يعامل هذا الأمر المصفوفة بوصفها مصفوفة دائرية (circular array) تُلفّ فيها فهارس المصفوفة الأكبر من «تدور حول نفسها» إلى بداية المصفوفة. ولم يتبقَّ سوى مراعاة ألّا يتجاوز عدد عناصر ArrayQueue حجم .
T[] a;
int j;
int n;
يوضِّح الشكل 2.2 تسلسلًا من عمليتَي و على ArrayQueue. ولتنفيذ ، نتحقَّق أولًا مما إذا كانت ممتلئة، وإن كان الأمر كذلك نستدعي لزيادة حجم . بعد ذلك، نخزِّن في ونزِيد .
boolean add(T x) {
if (n + 1 > a.length) resize();
a[(j+n) % a.length] = x;
n++;
return true;
}
ولتنفيذ ، نخزِّن أولًا لإعادة إرجاعه لاحقًا. بعد ذلك ننقص ونزِيد (حسب ) عبر تعيين . وأخيرًا، نُرجِع القيمة المُخزَّنة لـ . وعند الضرورة، يمكننا استدعاء لتقليل حجم .
T remove() {
if (n == 0) throw new NoSuchElementException();
T x = a[j];
j = (j + 1) % a.length;
n--;
if (a.length >= 3*n) resize();
return x;
}
أخيرًا، إنَّ عملية شديدة الشبه بعملية في ArrayStack. فهي تخصِّص مصفوفة جديدة حجمها وتنسخ
إلى
وتضبط .
void resize() {
T[] b = newArray(Math.max(1,n*2));
for (int k = 0; k < n; k++)
b[k] = a[(j+k) % a.length];
a = b;
j = 0;
}
2.3.1 الملخَّص تلخِّص المبرهنة التالية أداء بنية بيانات ArrayQueue: المبرهنة 2.2 يطبِّق ArrayQueue واجهة الطابور (Queue) من نوع FIFO. ومع تجاهل تكلفة الاستدعاءات لـ ، يدعم ArrayQueue العمليتين و في لكل عملية. وعلاوة على ذلك، فإنَّ البدء من ArrayQueue فارغ وتنفيذ أي تسلسل من عملية من و ينتج عن ذلك كليًا من الزمن المستغرق في جميع استدعاءات .
الحواشي
... symbol.2.2 يُشار إلى هذا أحيانًا بـ«عامل الباقي الغبي» (brain-dead mod operator)، لأنَّه لا ينفِّذ معامل الباقي الرياضي تنفيذًا صحيحًا عندما يكون المعامل الأول سالبًا. opendatastructures.org
2.4 ArrayDeque: عمليات deque سريعة باستخدام مصفوفة
الأقسام الفرعية
2.4 ArrayDeque: عمليات deque سريعة باستخدام مصفوفة
إنَّ ArrayQueue من القسم السابق بنية بيانات تمثِّل تسلسلًا يتيح لنا الإضافة بكفاءة إلى أحد طرفي التسلسل والإزالة من الطرف الآخر. أما بنية بيانات ArrayDeque — أي الصف المزدوج الطرفين (deque) — فتتيح الإضافة والإزالة بكفاءة عند كلا الطرفين. وتنفِّذ هذه البنية واجهة القائمة (List) باستخدام تقنية المصفوفة الدائرية نفسها المستخدَمة لتمثيل ArrayQueue.
T[] a;
int j;
int n;
عمليتا و على ArrayDeque مباشرتان. فهما تجلبان أو تضبطان عنصر المصفوفة .
T get(int i) {
if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
return a[(j+i)%a.length];
}
T set(int i, T x) {
if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
T y = a[(j+i)%a.length];
a[(j+i)%a.length] = x;
return y;
}
تنفيذ أكثر إثارةً للاهتمام قليلًا. وكالمعتاد، نتحقَّق أولًا مما إذا كانت ممتلئة، وإن كان الأمر كذلك نستدعي لتغيير حجم . وتذكَّر أنَّنا نريد أن تكون هذه العملية سريعة عندما يكون صغيرًا (قريبًا من 0) أو عندما يكون كبيرًا (قريبًا من ). وعليه، نتحقَّق مما إذا كان . وإن كان الأمر كذلك، فإنَّنا نزيح العناصر إلى اليسار بموضع واحد. وإلا ( )، فإنَّنا نزيح العناصر إلى اليمين بموضع واحد. انظر الشكل 2.3 لتوضيح عمليتَي و على ArrayDeque.
void add(int i, T x) {
if (i < 0 || i > n) throw new IndexOutOfBoundsException();
if (n+1 > a.length) resize();
if (i < n/2) { // shift a[0],..,a[i-1] left one position
j = (j == 0) ? a.length - 1 : j - 1; //(j-1)mod a.length
for (int k = 0; k <= i-1; k++)
a[(j+k)%a.length] = a[(j+k+1)%a.length];
} else { // shift a[i],..,a[n-1] right one position
for (int k = n; k > i; k--)
a[(j+k)%a.length] = a[(j+k-1)%a.length];
}
a[(j+i)%a.length] = x;
n++;
}
بإجراء الإزاحة بهذه الطريقة، نضمن ألَّا تحتاج قط إلى إزاحة أكثر من عنصرًا. وعليه، فإن زمن تنفيذ عملية (مع تجاهل تكلفة عملية ) هو . وتنفيذ عملية مشابه. فهو إما أن يزيح العناصر إلى اليمين بموضع واحد، أو يزيح العناصر إلى اليسار بموضع واحد، تبعًا لما إذا كان . ومرةً أخرى، هذا يعني أنَّ لا يقضي أكثر من في إزاحة العناصر.
T remove(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
T x = a[(j+i)%a.length];
if (i < n/2) { // shift a[0],..,[i-1] right one position
for (int k = i; k > 0; k--)
a[(j+k)%a.length] = a[(j+k-1)%a.length];
j = (j + 1) % a.length;
} else { // shift a[i+1],..,a[n-1] left one position
for (int k = i; k < n-1; k++)
a[(j+k)%a.length] = a[(j+k+1)%a.length];
}
n--;
if (3*n < a.length) resize();
return x;
}
2.4.1 الملخَّص تلخِّص المبرهنة التالية أداء بنية بيانات ArrayDeque: المبرهنة 2.3 يطبِّق ArrayDeque واجهة القائمة (List). ومع تجاهل تكلفة الاستدعاءات لـ ، يدعم ArrayDeque العمليتين * و في لكل عملية؛ وعمليتَي و في لكل عملية. * وعلاوة على ذلك، فإنَّ البدء من ArrayDeque فارغ وتنفيذ أي تسلسل من عملية من و ينتج عن ذلك كليًا من الزمن المستغرق في جميع استدعاءات .
2.5 DualArrayDeque: بناء deque من مكدَّسين
الأقسام الفرعية
2.5 DualArrayDeque: بناء deque من مكدَّسين
بعد ذلك، نقدِّم بنية بيانات هي DualArrayDeque، التي تحقِّق حدود الأداء نفسها التي يحقِّقها ArrayDeque باستخدام مصفوفة ArrayStack. ورغم أنَّ الأداء المقامي (asymptotic) لـ DualArrayDeque ليس أفضل من أداء ArrayDeque، فإنَّه يظل جديرًا بالدراسة، لأنَّه يقدِّم مثالًا جيدًا على كيفية بناء بنية بيانات متطوِّرة عبر دمج بنَيتي بيانات أبسط. يمثِّل DualArrayDeque قائمة باستخدام مصفوفتي ArrayStack. وتذكَّر أنَّ ArrayStack سريع عندما تعدِّل عليه العمليات عناصر قريبة من نهايته. يضع DualArrayDeque مصفوفتي ArrayStack، المسمَّيتَي و ، متجاورتين ظهرًا لظهر بحيث تكون العمليات سريعة عند أيٍّ من الطرفين.
List<T> front;
List<T> back;
لا يخزِّن DualArrayDeque صراحةً العدد للعناصر التي يحتوي عليها. فهو لا يحتاج إلى ذلك، لأنَّه يحتوي على عنصرًا. ومع ذلك، فإننا سنظل نستخدم في تحليل DualArrayDeque للدلالة على عدد العناصر التي يحتوي عليها.
int size() {
return front.size() + back.size();
}
يخزِّن الـ ArrayStack المسمَّى عناصر القائمة التي فهارسها ، لكنه يخزِّنها بترتيب معكوس. ويحتوي الـ ArrayStack المسمَّى على عناصر القائمة ذات الفهارس في بترتيبها الطبيعي. وبهذه الطريقة، تُترجَم و إلى استدعاءات ملائمة لـ أو على أو ، وتستغرق لكل عملية.
T get(int i) {
if (i < front.size()) {
return front.get(front.size()-i-1);
} else {
return back.get(i-front.size());
}
}
T set(int i, T x) {
if (i < front.size()) {
return front.set(front.size()-i-1, x);
} else {
return back.set(i-front.size(), x);
}
}
ولاحظ أنَّ الفهرس يقابل عنصر عند الموضع ، لأنَّ عناصر مُخزَّنة بترتيب معكوس. ويوضِّح الشكل 2.4 إضافة العناصر إلى DualArrayDeque وإزالتها منها. فعملية تُعالج أو حسبما هو مناسب:
void add(int i, T x) {
if (i < front.size()) {
front.add(front.size()-i, x);
} else {
back.add(i-front.size(), x);
}
balance();
}
تنفِّذ الدالة إعادة الموازنة (rebalancing) لـ ArrayStack المسمَّيين و ، من خلال استدعاء الدالة . ويُشرح تنفيذ أدناه، لكن يكفي في الوقت الحالي أن نعلم أنَّ تضمن، ما لم يكن ، ألَّا يختلف عن بمعامل يفوق 3. وعلى وجه التحديد، و . نحلِّل بعد ذلك تكلفة ، متجاهلين تكلفة الاستدعاءات لـ . فإذا كان ، فإنَّ يُنفَّذ بالاستدعاء إلى . وبما أنَّ هو ArrayStack، فإنَّ تكلفة ذلك هي
ومن جهة أخرى، إذا كان ، فإنَّ يُنفَّذ بوصفه . وتكلفة ذلك هي
ولاحظ أنَّ الحالة الأولى (2.1) تحدث عندما يكون . وتحدث الحالة الثانية (2.2) عندما يكون . وعندما يكون ، لا يمكننا الجزم ما إذا كانت العملية تؤثِّر في أم في ، لكن في كلتا الحالتين تستغرق العملية من الوقت، لأنَّ و . وتلخيصًا للموقف، لدينا
زمن تنفيذ 
وعليه، فإن زمن تنفيذ ، إذا تجاهلنا تكلفة الاستدعاء إلى ، هو . وتُشبه عملية وتحليلُها عملية وتحليلَها.
T remove(int i) {
T x;
if (i < front.size()) {
x = front.remove(front.size()-i-1);
} else {
x = back.remove(i-front.size());
}
balance();
return x;
}
2.5.1 الموازنة
أخيرًا، ننتقل إلى عملية التي تنفِّذها و . وتضمن هذه العملية ألَّا يصير ولا كبيرًا جدًا (أو صغيرًا جدًا). فهي تضمن أنَّ كلًّا من و يحتوي على ما لا يقل عن عنصر، ما لم يكن عدد العناصر أقل من اثنين. وإن لم يكن الأمر كذلك، فإنَّها تنقل عناصر بينهما بحيث يحتوي كلٌّ من و على عنصر و عنصر على الترتيب.
void balance() {
int n = size();
if (3*front.size() < back.size()) {
int s = n/2 - front.size();
List<T> l1 = newStack();
List<T> l2 = newStack();
l1.addAll(back.subList(0,s));
Collections.reverse(l1);
l1.addAll(front);
l2.addAll(back.subList(s, back.size()));
front = l1;
back = l2;
} else if (3*back.size() < front.size()) {
int s = front.size() - n/2;
List<T> l1 = newStack();
List<T> l2 = newStack();
l1.addAll(front.subList(s, front.size()));
l2.addAll(front.subList(0, s));
Collections.reverse(l2);
l2.addAll(back);
front = l1;
back = l2;
}
}
لا يوجد الكثير هنا لتحليله. فإذا قامت بإعادة الموازنة، فإنَّها تنقل عنصرًا وهذا يستغرق من الوقت. وهذا أمر سيئ، لأنَّ يُستدعى مع كل استدعاء لـ و . لكنَّ المُلمَّة التالية تبيِّن أنَّ ، في المتوسط، لا يقضي سوى وقت ثابت لكل عملية. المُلمَّة 2.2 إذا أُنشئ DualArrayDeque فارغ ونُفِّذ أي تسلسل من استدعاءً لـ و ، فإنَّ الزمن الكلي المستغرق في جميع استدعاءات هو .
البرهان. سنبيِّن أنَّه إذا أُجبر على إزاحة عناصر، فإنَّ عدد عمليات و منذ آخر مرة أوزحت فيها العناصر لا يقل عن . وكما في برهان المُلمَّة 2.1، فإنَّ هذا كافٍ لإثبات أنَّ الزمن الكلي الذي يقضيه هو .
سنجري تحليلنا باستخدام تقنية تُعرف باسم طريقة الجهد (potential method). نعرِّف جهد DualArrayDeque، ، بأنه الفرق في الحجم بين و :
والأمر اللافت للنظر في هذا الجهد أنَّ استدعاء أو الذي لا يقوم بأي موازنة يمكن أن يزيد الجهد بما لا يزيد عن 1.
ولاحظ أنَّه مباشرة بعد استدعاء الذي يزيح العناصر، يكون الجهد لا يزيد عن 1، لأنَّ
تخيَّل الحالة السابقة مباشرة لاستدعاء الذي يزيح العناصر، وافترض دون خسارة في العمومية أنَّ يزيح العناصر لأنَّ . ولاحظ أنَّه في هذه الحالة، وعلاوة على ذلك، فإنَّ الجهد في هذه اللحظة يساوي وعليه، فإنَّ عدد الاستدعاءات لـ أو منذ آخر مرة أزاحت فيها العناصر لا يقل عن . وهذا يُتمِّ البرهان.
2.5.2 الملخَّص تلخِّص المبرهنة التالية خصائص DualArrayDeque: المبرهنة 2.4 يطبِّق DualArrayDeque واجهة القائمة (List). ومع تجاهل تكلفة الاستدعاءات لـ و ، يدعم DualArrayDeque العمليتين * و في لكل عملية؛ وعمليتَي و في لكل عملية. * وعلاوة على ذلك، فإنَّ البدء من DualArrayDeque فارغ وتنفيذ أي تسلسل من عملية من و ينتج عن ذلك كليًا من الزمن المستغرق في جميع استدعاءات و .
2.6 RootishArrayStack: مكدّس مصفوفات موفِّر للمساحة
الأقسام الفرعية
2.6 RootishArrayStack: مكدّس مصفوفات موفِّر للمساحة
أحد عيوب جميع بنى البيانات السابقة في هذا الفصل أنَّها، لأنها تخزِّن بياناتها في مصفوفة أو مصفوفتين وتتجنَّب تغيير حجم هاتين المصفوفتين كثيرًا، تكون المصفوفات بكثرة غير ممتلئة إلى حدٍّ كبير. فمثلًا، مباشرة بعد عملية على ArrayStack، تكون المصفوفة الخلفية ممتلئة بمقدار النصف فقط. والأمر أسوأ، إذ توجد أوقات لا يحمل فيها سوى ثلث بيانات. وفي هذا القسم، نناقش بنية بيانات RootishArrayStack التي تعالج مشكلة المساحة المهدورة. يخزِّن RootishArrayStack عدد من العناصر باستخدام مصفوفة. وفي هذه المصفوفات، لا يوجد سوى موضع كحدٍّ أقصى غير مستخدَم في أي لحظة. وتُستخدم جميع المواضع المتبقية لتخزين البيانات. وعليه، فإنَّ هذه البنى تهدر من المساحة كحدٍّ أقصى عند تخزين عنصرًا. ويخزِّن RootishArrayStack عناصره في قائمة من مصفوفة تُدعى كتلًا (blocks) وتُرقَّم . انظر الشكل 2.5. تحتوي الكتلة على عنصرًا. وعليه، فإنَّ الكتل كلها تحتوي إجمالًا على
عنصرًا. ويمكن اشتقاق الصيغة أعلاه على النحو المبيَّن في الشكل 2.6.
List<T[]> blocks;
int n;
الشكل 2.6: عدد المربعات البيضاء يساوي . وعدد المربعات المظلَّلة هو نفسه. ويشكِّل المربعات البيضاء والمظلَّلة معًا مستطيلًا يتكوَّن من مربعًا. 
وكما قد نتوقَّع، تُرتَّب عناصر القائمة بالترتيب داخل الكتل. فعنصر القائمة ذو الفهرس 0 مُخزَّن في الكتلة 0، وعناصر القائمة ذات الفهارس 1 و2 مُخزَّنة في الكتلة 1، وعناصر القائمة ذات الفهارس 3 و4 و5 مُخزَّنة في الكتلة 2، وهكذا. المشكلة الرئيسية التي علينا معالجتها هي، عند معرفة الفهرس ، تحديد الكتلة التي تحتوي وكذلك الفهرس المقابل لـ داخل تلك الكتلة. ويتبيَّن أنَّ تحديد فهرس داخل كتلته أمرٌ سهل. فإذا كان الفهرس في الكتلة ، فإنَّ عدد العناصر في الكتل هو . وعليه، فإنَّ مُخزَّن في الموضع
داخل الكتلة . والإطار تحديبي هو تحديد قيمة . فعدد العناصر التي فهارسها أصغر من أو تساويه هو . ومن جهة أخرى، عدد العناصر في الكتل 0,...,b هو . وعليه، فإنَّ هو أصغر عدد صحيح بحيث
ويمكننا إعادة كتابة هذه المعادلة على النحو
وللمعادلة التربيعية المقابلة حلّان: و . والحلّ الثاني لا معنى له في تطبيقنا لأنَّه يعطي دائمًا قيمة سالبة. وعليه، نحصل على الحل . وبشكل عام، فإنَّ هذا الحل ليس عددًا صحيحًا، لكن عند العودة إلى المتباينة نريد أصغر عدد صحيح بحيث . وهذا ببساطة هو
int i2b(int i) {
double db = (-3.0 + Math.sqrt(9 + 8*i)) / 2.0;
int b = (int)Math.ceil(db);
return b;
}
وبانتهاء هذا الأمر، تكون الدالتان و مباشرتين. فنحسب أولًا الكتلة المناسبة والفهرس المناسب داخل الكتلة، ثم ننفِّذ العملية المناسبة:
T get(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
int b = i2b(i);
int j = i - b*(b+1)/2;
return blocks.get(b)[j];
}
T set(int i, T x) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
int b = i2b(i);
int j = i - b*(b+1)/2;
T y = blocks.get(b)[j];
blocks.get(b)[j] = x;
return y;
}
إذا استخدمنا أيًّا من بنى البيانات في هذا الفصل لتمثيل قائمة ، فإنَّ و تعمل كلٌّ منهما بزمن ثابت. أمَّا الدالة فستبدو مألوفةً الآن. فنتحقَّق أولًا مما إذا كانت بنية البيانات ممتلئة، عبر التحقُّق مما إذا كان عدد الكتل بحيث . وإن كان الأمر كذلك، نستدعي لإضافة كتلة أخرى. وبانتهاء ذلك، نزيح العناصر ذات الفهارس إلى اليمين بموضع واحد لإفساح المجال للعنصر الجديد ذي الفهرس :
void add(int i, T x) {
if (i < 0 || i > n) throw new IndexOutOfBoundsException();
int r = blocks.size();
if (r*(r+1)/2 < n + 1) grow();
n++;
for (int j = n-1; j > i; j--)
set(j, get(j-1));
set(i, x);
}
تفعل الدالة ما نتوقَّعه؛ فهي تضيف كتلة جديدة:
void grow() {
blocks.add(newArray(blocks.size()+1));
}
مع تجاهل تكلفة عملية ، تكون تكلفة عملية مهيمنةً عليها تكلفة الإزاحة، وعليها ، تمامًا مثل ArrayStack. أما عملية فمشابهة لـ . فهي تزيح العناصر ذات الفهارس إلى اليسار بموضع واحد، ثم إن كان هناك أكثر من كتلة فارغة واحدة، تستدعي الدالة لإزالة جميع الكتل غير المستخدَمة ما عدا واحدة:
T remove(int i) {
if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
T x = get(i);
for (int j = i; j < n-1; j++)
set(j, get(j+1));
n--;
int r = blocks.size();
if ((r-2)*(r-1)/2 >= n) shrink();
return x;
}
void shrink() {
int r = blocks.size();
while (r > 0 && (r-2)*(r-1)/2 >= n) {
blocks.remove(blocks.size()-1);
r--;
}
}
مرةً أخرى، مع تجاهل تكلفة عملية ، تكون تكلفة عملية مهيمنةً عليها تكلفة الإزاحة، وعليها . 2.6.1 تحليل النمو والانكماش لا يأخذ التحليل أعلاه لعمليتَي و في الحسبان تكلفة و . ولاحظ أنَّ عملية لا تنسخ أي بيانات، بخلاف و . فهما تخصِّصان أو تحرِّران مصفوفة واحدة فقط بحجم . وفي بعض البيئات يستغرق هذا وقتًا ثابتًا فقط، بينما في بيئات أخرى قد يتطلب وقتًا يتناسب مع . ونلاحظ أنَّ الحالة تكون واضحة مباشرة بعد استدعاء أو : فالكتلة الأخيرة فارغة تمامًا، وكل الكتل الأخرى ممتلئة تمامًا. ولن يحدث استدعاء آخر لـ أو حتى يتم إضافة أو إزالة ما لا يقل عن عنصر. وعليه، فحتى لو استغرق و من الوقت، فإنَّ هذه التكلفة يمكن توزيعها (amortize) على ما لا يقل عن عملية من أو ، بحيث تصبح التكلفة المُستهلكة لـ و هي لكل عملية. 2.6.2 استهلاك المساحة نحلِّل بعد ذلك مقدار المساحة الإضافية التي يستخدمها RootishArrayStack. فعلى وجه التحديد، نريد أن نحسب أي مساحة يستخدمها RootishArrayStack وليست عنصرًا في مصفوفة مستخدَمًا حاليًا للاحتفاظ بعنصر قائمة. ونسمِّي كل هذه المساحة «المساحة المهدورة» (wasted space). وتضمن عملية ألَّا يكون لدى RootishArrayStack أكثر من كتلتين ليستا ممتلئتين تمامًا. وعليه، فإنَّ عدد الكتل المستخدَمة في RootishArrayStack الذي يخزِّن عنصرًا يحقِّق
ومرةً أخرى، فإنَّ تطبيق المعادلة التربيعية على ذلك يعطي
للكتلتين الأخيرتين الحجمان و ، لذا فإنَّ المساحة المهدورة بهاتين الكتلتين لا تتجاوز . وإذا خزَّنَّا الكتل في (مثلًا) ArrayStack، فإنَّ مقدار المساحة المهدورة في القائمة (List) التي تخزِّن تلك الكتل هو أيضًا . أما المساحة الأخرى اللازمة لتخزين والمعلومات المحاسبية الأخرى فهي . وعليه، فإنَّ المقدار الكلي للمساحة المهدورة في RootishArrayStack هو .
بعد ذلك، نُجادل بأنَّ استهلاك المساحة هذا هو الأمثل لأي بنية بيانات تبدأ فارغة وتدعم إضافة عنصر واحد في كل مرة. وبشكل أدق، سنبيِّن أنَّه في لحظة ما أثناء إضافة عنصرًا، تكون بنية البيانات تهدري مساحة لا تقل عن (رغم أنها قد تكون مهدورة للحظة فقط). لنفترض أننا نبدأ ببنية بيانات فارغة ونضيف عنصرًا واحدًا في كل مرة. وفي نهاية هذه العملية، تكون جميع العناصر مخزَّنة في البنية وموزَّعة على مجموعة من كتل الذاكرة . فإذا كان ، فيجب أن تستخدم بنية البيانات مؤشرًا (أو مرجعًا) لتتبُّع تلك الكتل ، وهذه المؤشرات هي المساحة المهدورة. ومن جهة أخرى، إذا كان ، فإنَّ مبدأ الجرس (pigeonhole principle) يفرض أنَّ إحدى الكتل يجب أن يكون حجمها لا يقل عن . فلنفكر في اللحظة التي خُصِّصت فيها هذه الكتلة لأول مرة. فمباشرة بعد تخصيصها كانت هذه الكتلة فارغة، وبالتالي كانت تهدري مساحة قدرها . وعليه، فإنَّ بنية البيانات في لحظة ما أثناء إدراج عنصرًا كانت تهدري مساحة قدرها . 2.6.3 الملخَّص تلخِّص المبرهنة التالية مناقشتنا لبنية بيانات RootishArrayStack: المبرهنة 2.5 يطبِّق RootishArrayStack واجهة القائمة (List). ومع تجاهل تكلفة الاستدعاءات لـ و ، يدعم RootishArrayStack العمليتين * و في لكل عملية؛ وعمليتَي و في لكل عملية. * وعلاوة على ذلك، فإنَّ البدء من RootishArrayStack فارغ وتنفيذ أي تسلسل من عملية من و ينتج عن ذلك كليًا من الزمن المستغرق في جميع استدعاءات و . والمساحة (مقاسة بالكلمات)2.3 التي يستخدمها RootishArrayStack الذي يخزِّن عنصرًا هي .
2.6.4 حساب الجذور التربيعية قد يلاحظ القارئ الذي لديه بعض الاطلاع على نماذج الحساب أنَّ RootishArrayStack، على النحو الموصوف أعلاه، لا يندرج ضمن نموذج word-RAM المعتاد للحساب (القسم 1.4) لأنه يتطلب أخذ جذور تربيعية. ولا تُعدّ عملية الجذر التربيعي في العادة عمليةً أساسية، ولذلك لا تكون عادةً جزءًا من نموذج word-RAM. وفي هذا القسم، نبيِّن أنَّ عملية الجذر التربيعي يمكن تنفيذها بكفاءة. وعلى وجه التحديد، نبيِّن أنَّه لأي عدد صحيح ، يمكن حساب بزمن ثابت، بعد عملية معالجة أولية (preprocessing) من تُنشئ مصفوفتين طول كلٍّ منهما . وتبيِّن المُلمَّة التالية أنَّنا يمكننا اختزال مسألة حساب الجذر التربيعي لـ إلى حساب الجذر التربيعي لقيمة مرتبطة . المُلمَّة 2.3 ليكن وليكن ، حيث . عندئذٍ .
البرهان. يكفي أن نبيِّن أنَّ
بربيع طرفي هذه المتباينة نحصل على
وجمع الحدود نحصل على
وهو واضح تمامًا لأي .
لنبدأ بتقييد المسألة قليلًا، ونفترض أنَّ ، بحيث يكون ، أي أنَّ عدد صحيح له بت في تمثيله الثنائي. ويمكننا أن نأخذ . والآن، يستوفي شروط المُلمَّة 2.3، لذا . وعلاوة على ذلك، فإنَّ جميع بتات ذات الرتبة الدنيا تساوي 0، لذا لا توجد سوى
قيمة ممكنة لـ . وهذا يعني أننا يمكننا استخدام مصفوفة تخزِّن قيمة لكل قيمة ممكنة لـ . وبشكل أدق قليلًا، لدينا
وبهذه الطريقة، يكون ضمن مسافة 2 من لكل . وبعبارة أخرى، إمَّا أن يساوي مدخل المصفوفة القيمة أو أو . ومن يمكننا تحديد قيمة بزيادة حتى تتحقَّق .
int sqrt(int x, int r) {
int s = sqrtab[x>>r/2];
while ((s+1)*(s+1) <= x) s++; // executes at most twice
return s;
}
والآن، فإنَّ هذا لا ينطبق إلا على ، فـ جدول خاص لا يعمل إلا لقيمة معيَّنة . وللتغلُّب على ذلك، يمكننا حساب من مصفوفات المختلفة، واحدة لكل قيمة ممكنة لـ . وتُشكِّل أحجام هذه الجداول تسلسلًا أُسِّيًّا أكبر قيمته لا يتجاوز ، لذا فإنَّ الحجم الكلي لجميع الجداول هو .
غير أنَّه يتبيَّن أنَّ مصفوفة واحدة من تكفي؛ فنحن لا نحتاج سوى مصفوفة واحدة للقيمة . وأي قيمة بحيث يمكن «ترقيتها» بضرب في واستخدام المعادلة
إنَّ الكمية تقع في المجال ، لذا يمكننا البحث عن جذرها التربيعي في . ويَنفِّذ الشيفرة التالية هذه الفكرة لحساب لكل الأعداد الصحيحة غير السالبة في المجال باستخدام مصفوفة بحجم .
int sqrt(int x) {
int rp = log(x);
int upgrade = ((r-rp)/2) * 2;
int xp = x << upgrade; // xp has r or r-1 bits
int s = sqrtab[xp>>(r/2)] >> (upgrade/2);
while ((s+1)*(s+1) <= x) s++; // executes at most twice
return s;
}
حتى الآن افترضنا دون مناقشة مسألة كيفية حساب . وهذه أيضًا مسألة يمكن حلُّها باستخدام مصفوفة بحجم . وفي هذه الحالة تكون الشيفرة بسيطةً بصفة خاصة، لأنَّ هو ببساطة فهرس البت 1 الأكثر أهمية في التمثيل الثنائي لـ . وهذا يعني أنَّه بالنسبة إلى ، يمكننا إزاحة بتات إلى اليمين بمقدار موضعًا قبل استخدامها كفهرس في . ويَنفِّذ الشيفرة التالية ذلك باستخدام مصفوفة بحجم لحساب لكل في المجال .
int log(int x) {
if (x >= halfint)
return 16 + logtab[x>>>16];
return logtab[x];
}
أخيرًا، ومن أجل الاكتمال، نُدرج الشيفرة التالية التي تُهيِّئ و :
void inittabs() {
sqrtab = new int[1<<(r/2)];
logtab = new int[1<<(r/2)];
for (int d = 0; d < r/2; d++)
Arrays.fill(logtab, 1<<d, 2<<d, d);
int s = 1<<(r/4); // sqrt(2^(r/2))
for (int i = 0; i < 1<<(r/2); i++) {
if ((s+1)*(s+1) <= i << (r/2)) s++; // sqrt increases
sqrtab[i] = s;
}
}
وخلاصةً، يمكن تنفيذ الحسابات التي تجريها الدالة بزمن ثابت على word-RAM باستخدام ذاكرة إضافية قدرها لتخزين مصفوفتي و . ويمكن إعادة بناء هاتين المصفوفتين عندما يزداد أو ينقص بمعامل اثنين، ويمكن توزيع تكلفة إعادة البناء على عدد عمليات و التي سبَّبت التغيُّر في بالطريقة نفسها التي حُلِّل بها تكلفة في تنفيذ ArrayStack.
الحواشي
... words)2.3 راجع القسم 1.4 لمناقشة كيفية قياس الذاكرة. opendatastructures.org
2.7 مناقشة وتمارين
معظم بنى البيانات الموصوفة في هذا الفصل تراثية (folklore)، إذ يمكن العثور عليها في تنفيذات ترجع إلى أكثر من 30 عامًا. فمثلًا، يناقش Knuth [46, القسم 2.2.2] تنفيذات للمكدَّسات والطوابير deques (صفوف مزدوجة الطرفين)، التي تتعمَّم بسهولة إلى البنى ArrayStack وArrayQueue وArrayDeque الموصوفة هنا. ويبدو أنَّ Brodnik وآخرون [13] كانوا الأوائل في وصف RootishArrayStack وإثبات حدٍّ أدنى من الشكل مثل ذاك في القسم 2.6.2. وهم أيضًا يقدِّمون بنية مختلفة تستخدم اختيارًا أكثر تعقيدًا لأحجام الكتل من أجل تجنُّب حساب الجذور التربيعية في الدالة . وفي مخطَّطهم، تكون الكتلة التي تحتوي هي الكتلة ، وهو ببساطة فهرس البت 1 الأبرز في التمثيل الثنائي لـ . وتوفِّر بعض معماريات الحاسوب تعليمةً لحساب فهرس البت 1 الأبرز في عدد صحيح. وفي Java، توفِّر الفئة Integer الدالة التي يمكن منها بسهولة حساب . أما البنية المرتبطة بـ RootishArrayStack فهي المتجه المُطبَّق على مستويين (two-level tiered vector) لـ Goodrich وKloss [35]. تدعم هذه البنية عمليتَي و بزمن ثابت، وعمليتَي و في من الوقت. وهذه أزمنة التنفيذ مشابهة لما يمكن بلوغه مع التنفيذ الأدق لـ RootishArrayStack المناقش في التمرين 2.11. التمرين 2.1 في تنفيذ ArrayStack، بعد أول استدعاء لـ ، تحتوي المصفوفة الخلفية على قيمة غير على الرغم من أنَّ ArrayStack يحتوي على عنصرًا فقط. فأين القيمة غير الزائدة؟ ناقش أي عواقب قد تُحدثها هذه القيمة غير في مدير الذاكرة الخاص ببيئة تشغيل Java.
التمرين 2.2 تُدرج الدالة في القائمة (List) جميع عناصر المجموعة (Collection) عند الموضع . (و هي حالة خاصة حيث .) اشرح لماذا، بالنسبة إلى بنى البيانات في هذا الفصل، لا يكون تنفيذ عبر استدعاءات متكررة لـ كفؤًا. صمِّم ونفِّذ تنفيذًا أكثر كفؤة.
التمرين 2.3 صمِّم ونفِّذ RandomQueue. وهذا تنفيذ لواجهة الطابور (Queue) تُزيل فيه عملية عنصرًا يُختار عشوائيًا بانتظام من بين جميع العناصر الموجودة حاليًا في الطابور. (تخيَّل RandomQueue ككيسٍ يمكننا أن نضيف إليه عناصر أو نمدَّ أيدينا داخله ونُزيل عشوائيًا بعض العناصر دون رؤية.) وينبغي أن تعمل عمليتا و في RandomQueue بزمن ثابت لكل عملية.
التمرين 2.4 صمِّم ونفِّذ Treque (طابورًا ثلاثي الأطراف). وهذا تنفيذ للقائمة (List) تعمل فيه و بزمن ثابت وتعمل و في زمن
بعبارة أخرى، تكون التعديلات سريعة إذا كانت قريبة من أيٍّ من الطرفين أو قريبة من منتصف القائمة.
التمرين 2.5 نفِّذ دالة «تدوِّر» (rotate) المصفوفة بحيث ينتقل إلى ، لكل .
التمرين 2.6 نفِّذ دالة «تدوِّر» قائمةً (List) بحيث يصبح عنصر القائمة هو عنصر القائمة . وعندما تُنفَّذ على ArrayDeque أو DualArrayDeque، ينبغي أن تعمل في من الوقت.
التمرين 2.7 عدِّل تنفيذ ArrayDeque بحيث تُنفَّذ الإزاحة التي تجريها و و باستخدام الدالة الأسرع .
التمرين 2.8 عدِّل تنفيذ ArrayDeque بحيث لا يستخدم معامل (الذي يكون مكلفًا على بعض الأنظمة). وبدلًا من ذلك، ينبغي أن يستفيد من الحقيقة التالية: إذا كان قوةً للعدد 2، فإنَّ
(هنا، هو معامل AND على مستوى البتات (bitwise-and).)
التمرين 2.9 صمِّم ونفِّذ نوعًا بديلًا من ArrayDeque لا يجري أي حساب ثنائي الباقي على الإطلاق. وبدلًا من ذلك، تجلس جميع البيانات في كتلة متصلة، بالترتيب، داخل مصفوفة. وعندما تتجاوز البيانات بداية هذه المصفوفة أو نهايتها، تُنفَّذ عملية معدَّلة. وينبغي أن تكون التكلفة المُستهلكة لجميع العمليات مطابقة لتلك في ArrayDeque. تلميح: إنَّ جعل هذا يعمل يتوقف فعليًا على كيفية تنفيذك لعملية . فأنت تريد أن تضع بنية البيانات في حالة لا يمكن فيها للبيانات أن تتجاوز أيًّا من الطرفين حتى بعد تنفيذ ما لا يقل عن عملية. اختبر أداء تنفيذك مقابل ArrayDeque. وحسِّن تنفيذك (باستخدام ) وشاهد ما إذا استطعت أن تجعله يتفوق على تنفيذ ArrayDeque.
التمرين 2.10 صمِّم ونفِّذ نسخة من RootishArrayStack لا تملك سوى من المساحة المهدورة، لكنها قادرة على تنفيذ عمليتَي و في من الوقت.
التمرين 2.11 صمِّم ونفِّذ نسخة من RootishArrayStack لا تملك سوى من المساحة المهدورة، لكنها قادرة على تنفيذ عمليتَي و في من الوقت. (للاطلاع على فكرة كيفية ذلك، انظر القسم 3.3.)
التمرين 2.12 صمِّم ونفِّذ نسخة من RootishArrayStack لا تملك سوى من المساحة المهدورة، لكنها قادرة على تنفيذ عمليتَي و في من الوقت. (انظر القسم 3.3 للحصول على أفكار عن كيفية تحقيق ذلك.)
التمرين 2.13 صمِّم ونفِّذ CubishArrayStack. وهذه البنية ذات المستويات الثلاثة تنفِّذ واجهة القائمة (List) باستخدام من المساحة المهدورة. وفي هذه البنية، تأخذ و وقتًا ثابتًا؛ بينما تأخذ و وقتًا مُستهلكًا قدره .