بنية بيانات ثابتة

في مجال الحوسبة ، تُعرف بنية البيانات الدائمة ، أو بنية البيانات غير المؤقتة، بأنها بنية بيانات تحتفظ دائمًا بالنسخة السابقة منها عند تعديلها. وتُعتبر هذه البنى غير قابلة للتغيير فعليًا ، إذ لا تُحدِّث عملياتها البنية في مكانها (ظاهريًا)، بل تُنتج دائمًا بنية جديدة مُحدَّثة. وقد طُرِح هذا المصطلح لأول مرة في مقالة دريسكول، وسارناك، وسليتور، وتارجان عام ١٩٨٦. ^{[ ١ ]}

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

تُعد هذه الأنواع من هياكل البيانات شائعة بشكل خاص في البرمجة المنطقية والوظيفية ، ^[²^] حيث أن اللغات في تلك النماذج تثبط (أو تحظر تمامًا) استخدام البيانات القابلة للتغيير.

الاستمرارية الجزئية مقابل الاستمرارية الكاملة

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

تقنيات لحفظ الإصدارات السابقة

النسخ عند الكتابة

إحدى طرق إنشاء بنية بيانات دائمة هي استخدام بنية بيانات مؤقتة توفرها المنصة، مثل المصفوفة، لتخزين البيانات في بنية البيانات، ثم نسخ بنية البيانات بأكملها. هذه تقنية غير فعالة، إذ يجب نسخ بنية البيانات الأساسية بالكامل مع كل عملية كتابة، مما يؤدي إلى أسوأ النتائج. $O(n\cdot m)$ خصائص الأداء لعدد m من التعديلات على مصفوفة بحجم n . يمكن لإدارة الذاكرة بتقنية النسخ عند الكتابة أن تقلل من تكلفة التحديث من $\Theta (n)$ ل $O(Bu)$ ، حيث B هو حجم كتلة الذاكرة و u هو عدد الصفحات التي تم تحديثها في عملية واحدة.

عقدة دهنية

تعتمد طريقة العقدة السمينة على تسجيل جميع التغييرات التي تُجرى على حقول العقدة داخل العقد نفسها، دون حذف القيم القديمة للحقول. يتطلب هذا السماح للعقد بأن تصبح "سمينة" بشكل تعسفي. بمعنى آخر، تحتوي كل عقدة سمينة على نفس المعلومات وحقول المؤشرات الموجودة في العقدة المؤقتة، بالإضافة إلى مساحة لعدد غير محدود من قيم الحقول الإضافية. لكل قيمة حقل إضافية اسم حقل مرتبط بها وختم إصدار يشير إلى الإصدار الذي تم فيه تغيير الحقل المسمى إلى القيمة المحددة. علاوة على ذلك، تحتوي كل عقدة سمينة على ختم إصدار خاص بها، يشير إلى الإصدار الذي تم إنشاء العقدة فيه. الغرض الوحيد من وجود أختام إصدار للعقد هو ضمان احتواء كل عقدة على قيمة واحدة فقط لكل اسم حقل في كل إصدار. لتسهيل التنقل عبر البنية، يكون ختم الإصدار لكل قيمة حقل أصلية في العقدة صفرًا.

تعقيد العقدة الدهنية

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

نسخ المسار

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

تعقيد عملية نسخ المسار

مع إجراء m تعديلًا، يتطلب ذلك وقت بحث إضافي قدره O(log m) . ويُحدَّد وقت التعديل ومساحته بالحد الأقصى لعدد الأسلاف لأي عقدة في بنية البيانات مضروبًا في تكلفة التحديث في بنية البيانات المؤقتة. في شجرة بحث ثنائية متوازنة بدون مؤشرات للآباء، يكون تعقيد وقت التعديل في أسوأ الحالات O(log n + تكلفة التحديث). أما في القائمة المرتبطة، فيكون تعقيد وقت التعديل في أسوأ الحالات O(n + تكلفة التحديث).

مزيج

ابتكر دريسكول وسارناك وسليتور وتارجان ^[¹^] طريقةً تجمع بين تقنيات العقد السمينة ونسخ المسار، محققين تباطؤًا في الوصول بمقدار O(1) وتكلفةً إضافيةً مُستهلكةً بمقدار O(1) في المساحة والوقت لكل تعديل. تفترض طريقتهم بنية بيانات مرتبطة تحتوي على d مؤشرًا واردًا على الأكثر إلى كل عقدة، حيث d ثابت معروف.

يُخزَّن في كل عقدة مربع تعديل واحد. يمكن لهذا المربع أن يحتوي على تعديل واحد للعقدة - إما تعديل لأحد المؤشرات، أو لمفتاح العقدة، أو لأي بيانات أخرى خاصة بالعقدة - بالإضافة إلى طابع زمني لوقت تطبيق هذا التعديل. في البداية، يكون مربع تعديل كل عقدة فارغًا.

عند الوصول إلى أي عقدة، يتم تحديد خانة التعديل، ومقارنة طابعها الزمني بوقت الوصول. (يحدد وقت الوصول إصدار بنية البيانات قيد الدراسة). إذا كانت خانة التعديل فارغة، أو كان وقت الوصول قبل وقت التعديل، فسيتم تجاهل خانة التعديل، وسيتم النظر فقط في الجزء العادي من العقدة. أما إذا كان وقت الوصول بعد وقت التعديل، فسيتم استخدام القيمة الموجودة في خانة التعديل، متجاوزةً القيمة الموجودة في العقدة.

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

باستخدام هذه الخوارزمية ، عند أي وقت t، يوجد على الأكثر مربع تعديل واحد في بنية البيانات عند الوقت t. وبالتالي، فإن التعديل عند الوقت t يقسم الشجرة إلى ثلاثة أجزاء: جزء يحتوي على البيانات من قبل الوقت t، وجزء يحتوي على البيانات من بعد الوقت t، وجزء لم يتأثر بالتعديل.

تعقيد التركيبة

يتطلب حساب الوقت والمساحة اللازمين لإجراء التعديلات تحليلًا مُستهلكًا. يستغرق التعديل مساحة مُستهلكة ثابتة (O(1))، ووقتًا مُستهلكًا ثابتًا (O(1)). لفهم السبب، استخدم دالة الجهد ϕ ، حيث ϕ (T) هو عدد العقد النشطة الكاملة في T. العقد النشطة في T هي ببساطة العقد التي يمكن الوصول إليها من الجذر الحالي في الوقت الحالي (أي بعد آخر تعديل). أما العقد النشطة الكاملة فهي العقد النشطة التي تكون مربعات تعديلها ممتلئة.

يتضمن كل تعديل عددًا من النسخ، ولنقل k ، متبوعًا بتغيير واحد في مربع التعديل. لنفترض كل نسخة من النسخ k . كل نسخة تكلف مساحة ووقتًا ثابتين (O(1))، لكنها تُنقص دالة الجهد بمقدار واحد. (أولًا، يجب أن تكون العقدة المراد نسخها ممتلئة ونشطة، لذا فهي تُساهم في دالة الجهد. مع ذلك، لن تنخفض دالة الجهد إلا إذا لم يكن الوصول إلى العقدة القديمة ممكنًا في الشجرة الجديدة. ولكن من المعروف أنها غير قابلة للوصول في الشجرة الجديدة - ستكون الخطوة التالية في الخوارزمية هي تعديل العقدة الأصلية للإشارة إلى النسخة. أخيرًا، من المعروف أن مربع تعديل النسخة فارغ. وبالتالي، تم استبدال عقدة نشطة ممتلئة بعقدة نشطة فارغة، وينخفض ϕ بمقدار واحد.) الخطوة الأخيرة هي ملء مربع التعديل، وهو ما يكلف وقتًا ثابتًا (O(1)) ويزيد ϕ بمقدار واحد.

بجمع كل ذلك، يكون التغير في ϕ هو Δϕ = 1 − k . وبالتالي، تستغرق الخوارزمية مساحة O( k + Δϕ ) = O(1) ووقت O( k + Δϕ + 1) = O(1).

الشكل المعمم للاستمرارية

يُعدّ نسخ المسار إحدى الطرق البسيطة لتحقيق استمرارية البيانات في بنية بيانات معينة، مثل أشجار البحث الثنائية. من المفيد وجود استراتيجية عامة لتنفيذ الاستمرارية تعمل مع أي بنية بيانات. لتحقيق ذلك، نعتبر الرسم البياني الموجه $G.$ نفترض أن لكل رأس $v$ في $G$ عددًا ثابتًا $c$ من الحواف الخارجة، والتي تُمثلها مؤشرات. لكل رأس تسمية تُمثل البيانات. نفترض أن لكل رأس عددًا محدودًا $d$ من الحواف المؤدية إليه، والتي نُعرّفها بـ inedges( $v$ ). نسمح بإجراء العمليات المختلفة التالية على $G.$

CREATE-NODE(): يقوم بإنشاء رأس جديد بدون حواف واردة أو صادرة.
CHANGE-EDGE( $v$ , $i$ , $u$ ): تُغير الحافة ^رقم $i$ من $v$ لتشير إلى $u$
CHANGE-LABEL( $v$ , $x$ ): يغير قيمة البيانات المخزنة في $v$ إلى $x$

تُنفَّذ أيٌّ من العمليات المذكورة أعلاه في وقتٍ مُحدَّد، والغرض من تمثيل الرسم البياني المُستمر هو إمكانية الوصول إلى أي نسخة من $G$ في أي وقت مُحدَّد. ولهذا الغرض، نُعرِّف جدولًا لكل رأس $v$ في $G.$ يحتوي الجدول على $c$ أعمدة و $d+1$ صفوف. يحتوي كل صف، بالإضافة إلى مؤشرات الحواف الصادرة، على تسمية تمثل البيانات عند الرأس ووقت $t$ الذي نُفذت فيه العملية. بالإضافة إلى ذلك، توجد مصفوفة inedges( $v$ ) التي تتعقب جميع الحواف الواردة إلى $v$ . عندما يمتلئ جدول، يتم إنشاء جدول جديد يحتوي على $d+1$ يمكن إنشاء صفوف. يصبح الجدول القديم غير نشط ويصبح الجدول الجديد هو الجدول النشط.

إنشاء عقدة

يؤدي استدعاء CREATE-NODE إلى إنشاء جدول جديد وتعيين جميع المراجع إلى قيمة فارغة (null).

حافة التغيير

إذا افترضنا أنه يتم استدعاء CHANGE-EDGE( $v$ , $i$ , $u$ )، فهناك حالتان يجب أخذهما في الاعتبار.

يوجد صف فارغ في جدول الرأس $v$ : في هذه الحالة، ننسخ الصف الأخير في الجدول ونغير الحافة رقم $i$ للرأس $v$ لتشير إلى الرأس الجديد $u$
جدول الرؤوس $v$ ممتلئ: في هذه الحالة، نحتاج إلى إنشاء جدول جديد. ننسخ الصف الأخير من الجدول القديم إلى الجدول الجديد. نحتاج إلى المرور على مصفوفة inedges( $v$ ) لكي يشير كل رأس في المصفوفة إلى الجدول الجديد الذي تم إنشاؤه. بالإضافة إلى ذلك، نحتاج إلى تغيير المدخل v $في$ inedges(w) لكل رأس $w$ بحيث توجد الحافة $v,w$ في الرسم البياني $G.$

تغيير الملصق

يعمل تمامًا مثل CHANGE-EDGE باستثناء أنه بدلاً من تغيير الحافة ^رقم $i$ للرأس، نقوم بتغيير التسمية ^رقم $i$ .

كفاءة بنية البيانات المستمرة المعممة

لتقييم كفاءة النظام المقترح أعلاه، نستخدم وسيطًا يُعرَّف بنظام الائتمان. يُمثل الائتمان عملة. على سبيل المثال، يُمكن استخدام الائتمان لدفع ثمن طاولة. ينص الوسيط على ما يلي:

إنشاء جدول واحد يتطلب رصيدًا واحدًا
كل استدعاء لـ CREATE-NODE يأتي برصيدين
كل مكالمة إلى CHANGE-EDGE تأتي مع رصيد واحد

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

CREATE-NODE: يكتسب هذا الأمر رصيدين، أحدهما يُستخدم لإنشاء الجدول والآخر يُمنح للصف الذي يُضاف إليه. وبذلك يتم الحفاظ على الثابت.
تغيير الحافة: هناك حالتان يجب أخذهما في الاعتبار. الحالة الأولى تحدث عندما يكون هناك صف فارغ واحد على الأقل في الجدول. في هذه الحالة، يتم استخدام رصيد واحد للصف المُضاف حديثًا. الحالة الثانية تحدث عندما يكون الجدول ممتلئًا. في هذه الحالة، يصبح الجدول القديم غير نشط و $d+1$ يتم تحويل الرصيد إلى الجدول الجديد بالإضافة إلى الرصيد الواحد المكتسب من استدعاء CHANGE-EDGE. لذا، لدينا إجمالاً $d+2$ تُستخدم نقاط الاعتماد. نقطة اعتماد واحدة لإنشاء الجدول الجديد. نقطة اعتماد أخرى لإضافة الصف الجديد إلى الجدول، أما نقاط $الاعتماد$ المتبقية فتُستخدم لتحديث جداول الرؤوس الأخرى التي تحتاج إلى الإشارة إلى الجدول الجديد. نستنتج من ذلك أن الثابت مُحافظ عليه.
تغيير الملصق: يعمل تمامًا مثل تغيير الحافة.

وخلاصة القول، نستنتج أن امتلاك $n_{1}$ استدعاءات CREATE_NODE و $n_{2}$ ستؤدي استدعاءات CHANGE_EDGE إلى إنشاء $2\cdot n_{1}+n_{2}$ طاولات. بما أن لكل طاولة حجمًا $O(d)$ دون الأخذ في الاعتبار الاستدعاءات المتكررة، فإن ملء الجدول يتطلب $O(dc)$ لذلك، فإن مقدار العمل المطلوب لإكمال سلسلة من العمليات محدود بعدد الجداول التي تم إنشاؤها مضروبًا في $O(dc)$ يمكن تنفيذ كل عملية وصول في $O(\log(d))$ وهناك $m$ عملية على الحواف والتسميات، وبالتالي يتطلب ذلك $m\cdot O(\log(d))$ نستنتج أنه توجد بنية بيانات يمكنها إكمال أي تسلسل $n$ من عمليات إنشاء العقدة، وتغيير الحافة، وتغيير التسمية، بالإضافة إلى m من عمليات الوصول في $O(n\cdot dc)+m\cdot O(\log(d))$ .

تطبيقات هياكل البيانات المستمرة

البحث عن العنصر التالي أو تحديد موقع النقطة

من التطبيقات المفيدة التي يمكن حلها بكفاءة باستخدام تقنية الثبات، البحث عن العنصر التالي. لنفترض وجود $n$ قطعة مستقيمة غير متقاطعة، موازية لمحور السينات. نريد بناء بنية بيانات تستعلم عن نقطة $p$ وتعيد القطعة المستقيمة التي تقع فوقها $($ إن وجدت). سنبدأ بحل مسألة البحث عن العنصر التالي باستخدام الطريقة البسيطة، ثم سنوضح كيفية حلها باستخدام طريقة بنية البيانات الثابتة.

الطريقة الساذجة

نبدأ بقطعة مستقيمة عمودية تبدأ من اللانهاية، ونمسح هذه القطع من اليسار إلى اليمين. نتوقف مؤقتًا عند كل نقطة نهاية لهذه القطع. تقسم الخطوط العمودية المستوى إلى شرائح عمودية. إذا كان لدينا $n$ قطعة مستقيمة، فيمكننا الحصول على $2\cdot n+1$ شرائح عمودية لأن كل جزء يحتوي علىنقطتا نهاية. لا تبدأ أي قطعة مستقيمة أو تنتهي داخل الشريط. كل قطعة مستقيمة إما لا تلامس الشريط أو تعبره بالكامل. يمكننا اعتبار القطع المستقيمة كأجسام مرتبة ترتيبًا معينًا من الأعلى إلى الأسفل. ما يهمنا هو موقع النقطة التي ننظر إليها ضمن هذا الترتيب. نرتب نقاط نهاية القطع المستقيمة حسب إحداثياتها $السينية$ . لكل شريط $s_{i}$ نقوم بتخزين أجزاء المجموعة الفرعية التي تتقاطع $s_{i}$ في قاموس. عندما يمر الخط العمودي عبر القطع المستقيمة، نضيف القطعة إلى القاموس كلما تجاوز نقطة النهاية اليسرى لها. وعندما يتجاوز نقطة النهاية اليمنى، نحذفها من القاموس. عند كل نقطة نهاية، نحفظ نسخة من القاموس ونخزن جميع النسخ مرتبة حسب إحداثيات $x$ . بالتالي، لدينا بنية بيانات قادرة على الإجابة عن أي استعلام. للعثور على القطعة المستقيمة فوق النقطة $p$ ، ننظر إلى إحداثي $x للنقطة$ $p$ لمعرفة أي نسخة أو شريط تنتمي إليه. ثم ننظر إلى إحداثي y للعثور على القطعة المستقيمة التي فوقها. لذا، نحتاج إلى بحثين ثنائيين، أحدهما لإحداثي $x$ للعثور على الشريط أو النسخة، والآخر لإحداثي $y$ للعثور على القطعة المستقيمة التي فوقها. وبالتالي، يستغرق الاستعلام وقتًا محددًا $.$ $O(\log(n))$ في بنية البيانات هذه، تُعدّ المساحة هي المشكلة، فإذا افترضنا أن لدينا أجزاءً مُهيكلة بطريقة تبدأ فيها كل جزء قبل نهاية أي جزء آخر، فإن المساحة المطلوبة لبناء البنية باستخدام الطريقة البسيطة ستكون $O(n^{2})$ دعونا نرى كيف يمكننا بناء بنية بيانات مستمرة أخرى بنفس وقت الاستعلام ولكن بمساحة أفضل.

طريقة بنية البيانات المستمرة

يمكننا أن نلاحظ أن ما يستغرق وقتًا فعليًا في بنية البيانات المستخدمة في الطريقة البسيطة هو أنه كلما انتقلنا من شريط إلى آخر، نحتاج إلى أخذ لقطة من بنية البيانات التي نستخدمها للحفاظ على ترتيبها. يمكننا أن نلاحظ أنه بمجرد حصولنا على الأجزاء المتقاطعة $s_{i}$ عندما ننتقل إلى $s_{i+1}$ إما أن يخرج شيء أو يدخل شيء. إذا كان الفرق بين ما هو موجود $s_{i}$ وماذا يوجد في $s_{i+1}$ إذا كانت هناك عملية إدراج أو حذف واحدة فقط، فليس من المستحسن نسخ كل شيء من $s_{i}$ ل $s_{i+1}$ يكمن السر في أنه بما أن كل نسخة تختلف عن سابقتها بإضافة أو حذف عنصر واحد فقط، فإننا نحتاج إلى نسخ الأجزاء المتغيرة فقط. لنفترض أن لدينا شجرة جذرها $T.$ عند إدخال مفتاح $k$ في الشجرة، نُنشئ ورقة جديدة تحتوي على $k$ . إجراء عمليات تدوير لإعادة توازن الشجرة سيُعدّل فقط عُقد المسار من $k$ إلى $T.$ قبل إدخال المفتاح $k$ في الشجرة، ننسخ جميع العُقد على المسار من $k$ إلى $T.$ الآن لدينا نسختان من الشجرة، الأصلية التي لا تحتوي على $k$ ، والشجرة الجديدة التي تحتوي على $k$ وجذرها نسخة من جذر $T.$ بما أن نسخ المسار من $k$ إلى $T$ لا يزيد وقت الإدخال بأكثر من عامل ثابت، فإن الإدخال في بنية البيانات الدائمة يستغرق $O(\log(n))$ للحذف، نحتاج إلى تحديد العقد التي ستتأثر به. لكل عقدة $v$ متأثرة، ننسخ المسار من الجذر إليها. سينتج عن ذلك شجرة جديدة جذرها نسخة من جذر الشجرة الأصلية. ثم نجري عملية الحذف على الشجرة الجديدة. سنحصل في النهاية على نسختين من الشجرة: الأصلية التي تحتوي على العقدة $v$ ، $والجديدة$ التي لا تحتوي عليها $.$ بما أن أي عملية حذف تُعدّل فقط المسار من الجذر إلى $v،$ فإن أي خوارزمية حذف مناسبة تعمل في $O(\log(n))$ وبالتالي، فإن عملية الحذف في بنية البيانات الدائمة تستغرق $O(\log(n))$ كل تسلسل من عمليات الإضافة والحذف سيؤدي إلى إنشاء تسلسل من القواميس أو الإصدارات أو الأشجار $S_{1},S_{2},\dots S_{i}$ حيث كل $S_{i}$ هو نتيجة العمليات $S_{1},S_{2},\dots S_{i}$ إذا كان كل $S_{i}$ إذا احتوى على $m$ عنصرًا، فسيتم البحث في كل عنصر. $S_{i}$ يأخذ $O(\log(m))$ باستخدام بنية البيانات المستمرة هذه، يمكننا حل مشكلة البحث عن العنصر التالي في $O(\log(n))$ وقت الاستعلام و $O(n\cdot \log(n))$ مساحة بدلاً من $O(n^{2})$ تجدون أدناه شفرة المصدر لمثال يتعلق بمشكلة البحث التالية.

أمثلة على هياكل البيانات المستمرة

تتميز هياكل البيانات الوظيفية البحتة بالاستمرارية التلقائية. ولعل أبسط هيكل بيانات مستمر هو القائمة المرتبطة أحادية الاتجاه، أو القائمة القائمة على cons ، وهي قائمة بسيطة من الكائنات ، حيث يحمل كل كائن مرجعًا إلى الكائن التالي في القائمة. وتستمر هذه القائمة لأن ذيلها قابل للاستخراج، أي آخر k عنصرًا ، ويمكن إضافة عقد جديدة أمامه. ولن يتكرر الذيل، بل سيصبح مشتركًا بين القائمة القديمة والجديدة. وطالما أن محتويات الذيل غير قابلة للتغيير، فإن هذه المشاركة ستكون غير مرئية للبرنامج.

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

ينبغي مقارنة هياكل البيانات المستمرة التي تعتمد على هياكل غير قابلة للتغيير ("وظيفية بحتة") بالهياكل التي تستخدم التحديثات المدمرة (الطفرة) والتي يتم جعلها مستمرة باستخدام تقنيات نسخ العقدة السمينة أو المسار، الموضحة أعلاه.

القوائم المرتبطة

تُعدّ القوائم المرتبطة أحادية الاتجاه بنية البيانات الأساسية في اللغات الوظيفية. ^{[ 10 ]} بعض اللغات المشتقة من ML ، مثل Haskell ، وظيفية بحتة، لأنه بمجرد تخصيص عقدة في القائمة، لا يمكن تعديلها، بل يمكن نسخها أو الإشارة إليها أو حذفها بواسطة جامع البيانات المهملة عندما لا يكون هناك أي إشارة إليها. (تجدر الإشارة إلى أن ML نفسها ليست وظيفية بحتة، ولكنها تدعم مجموعة فرعية من عمليات القوائم غير المدمرة، وهذا ينطبق أيضًا على لهجات لغة Lisp (معالجة القوائم) الوظيفية مثل Scheme و Racket ).

انظر إلى القائمتين:

xs = [0, 1, 2] ys = [3, 4, 5]

سيتم تمثيل هذه الأشياء في الذاكرة بواسطة:

حيث تشير الدائرة إلى عقدة في القائمة (يمثل السهم الخارج العنصر الثاني من العقدة وهو مؤشر إلى عقدة أخرى).

والآن، دمج القائمتين:

zs = xs ++ ys

ينتج عن ذلك بنية الذاكرة التالية:

لاحظ أن العقد في القائمة xsقد نُسخت، بينما العقد في القائمة الأخرى ysمشتركة. ونتيجة لذلك، تبقى القوائم الأصلية ( xsو ys) كما هي دون تغيير.

والسبب في النسخ هو أنه لا يمكن تعديل العقدة الأخيرة في xs(العقدة التي تحتوي على القيمة الأصلية 2) لتشير إلى بداية ys، لأن ذلك سيؤدي إلى تغيير قيمة xs.

الأشجار

لنفترض شجرة بحث ثنائية ، ^{[ 10 ]} حيث يكون لكل عقدة في الشجرة الثابت المتكرر الذي ينص على أن جميع العقد الفرعية الموجودة في الشجرة الفرعية اليسرى لها قيمة أقل من أو تساوي القيمة المخزنة في العقدة، والعقد الفرعية الموجودة في الشجرة الفرعية اليمنى لها قيمة أكبر من القيمة المخزنة في العقدة.

على سبيل المثال، مجموعة البيانات

xs = [a, b, c, d, f, g, h]

يمكن تمثيلها بشجرة البحث الثنائية التالية:

الدالة التي تُدخل البيانات في الشجرة الثنائية وتحافظ على الثابت هي:

دالة إدراج ( x ، E ) = T ( E ، x ، E ) | إدراج ( x ، s) كـ T ( a ، y ، b )) = إذا كان x < y، فإن T ( إدراج ( x ، a )، y ، b ) وإلا إذا كان x > y، فإن T ( a ، y ، إدراج ( x ، b )) وإلا s

بعد التنفيذ

ys = insert ("e", xs)

يتم إنتاج التكوين التالي:

لاحظ نقطتين: أولاً، xsتبقى الشجرة الأصلية ( ) موجودة. ثانياً، تتشارك الشجرة القديمة والجديدة في العديد من العقد. يصعب إدارة هذا الثبات والمشاركة دون استخدام آلية لجمع البيانات المهملة (GC) لتحرير العقد التي لا توجد لها مراجع نشطة تلقائياً، ولهذا السبب تُعدّ آلية جمع البيانات المهملة ميزة شائعة في لغات البرمجة الوظيفية .

شجرة تشعبية مُرتبطة بمصفوفة تجزئة ثابتة

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

وُصفت أشجار التجزئة المُرتبطة بمصفوفات التجزئة لأول مرة في ورقة بحثية نُشرت عام ٢٠٠١ بقلم فيل باجويل بعنوان "أشجار التجزئة المثالية". قدّمت هذه الورقة جدول تجزئة قابلًا للتعديل حيث "تكون أوقات الإضافة والبحث والحذف قصيرة وثابتة، بغض النظر عن حجم مجموعة المفاتيح، وتكون العمليات من رتبة O(1). ويمكن ضمان أوقات قصيرة في أسوأ الحالات لعمليات الإضافة والبحث والحذف، وتكون تكلفة الأخطاء أقل من تكلفة عمليات البحث الناجحة". ^{[ ١٢ ]} ثم قام ريتش هيكي بتعديل بنية البيانات هذه لتصبح دائمة بالكامل لاستخدامها في لغة برمجة كلوجر . ^{[ ١٣ ]}

من الناحية المفاهيمية، تعمل أشجار البحث المُرتبطة بمصفوفة التجزئة بشكل مشابه لأي شجرة عامة ، حيث تخزن العقد بشكل هرمي وتسترجعها باتباع مسار وصولًا إلى عنصر معين. ويكمن الاختلاف الرئيسي في أن أشجار البحث المُرتبطة بمصفوفة التجزئة تستخدم أولًا دالة تجزئة لتحويل مفتاح البحث إلى عدد صحيح (عادةً 32 أو 64 بت). ثم يُحدد المسار أسفل الشجرة باستخدام شرائح من التمثيل الثنائي لهذا العدد الصحيح للفهرسة في مصفوفة متفرقة عند كل مستوى من مستويات الشجرة. وتتصرف عقد الأوراق في الشجرة بشكل مشابه للمجموعات المستخدمة في إنشاء جداول التجزئة ، وقد تحتوي أو لا تحتوي على عدة مرشحين اعتمادًا على تصادمات التجزئة . ^{[ 11 ]}

تستخدم معظم تطبيقات أشجار البحث المُرتبطة بمصفوفة تجزئة مستمرة عامل تفرع قدره 32. وهذا يعني أنه عمليًا، على الرغم من أن عمليات الإضافة والحذف والبحث في شجرة بحث مُرتبطة بمصفوفة تجزئة مستمرة لها تعقيد حسابي من رتبة O (log n )، إلا أنها في معظم التطبيقات تُعتبر ذات زمن ثابت فعليًا، إذ يتطلب الأمر عددًا هائلاً من المدخلات لجعل أي عملية تستغرق أكثر من اثنتي عشرة خطوة. ^{[ 14 ]}

الاستخدام في لغات البرمجة

هاسكل

لغة هاسكل هي لغة وظيفية بحتة ، ولذلك لا تسمح بالتعديل. وعليه، فإن جميع هياكل البيانات في هذه اللغة ثابتة، إذ يستحيل عدم الحفاظ على الحالة السابقة لهيكل بيانات ذي دلالات وظيفية. ^{[ 15 ]} ويعود ذلك إلى أن أي تغيير في هيكل البيانات من شأنه أن يجعل الإصدارات السابقة منه غير صالحة يُعد انتهاكًا لشفافية المرجعية .

تحتوي مكتبة هاسكل القياسية على تطبيقات فعالة ومستمرة للقوائم المرتبطة، ^{[ 16 ]} والخرائط (المنفذة كأشجار متوازنة الحجم)، ^{[ 17 ]} والمجموعات ^{[ 18 ]} من بين أمور أخرى. ^{[ 19 ]}

كلوجر

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

يدعو مصممو لغة كلوجر إلى استخدام هياكل البيانات الثابتة بدلاً من هياكل البيانات القابلة للتغيير، لأنها تتمتع بدلالات قيمية تمنحها ميزة إمكانية مشاركتها بحرية بين الخيوط باستخدام أسماء مستعارة رخيصة، وسهولة إنشائها، واستقلالها عن اللغة. ^{[ 22 ]}

تشكل هياكل البيانات هذه أساس دعم Clojure للحوسبة المتوازية ، حيث إنها تسمح بإعادة محاولات العمليات بسهولة لتجنب تضارب البيانات ودلالات المقارنة والتبديل الذرية . ^{[ 23 ]}

إلم

لغة البرمجة Elm وظيفية بحتة مثل Haskell، مما يجعل جميع هياكل بياناتها دائمة بالضرورة. فهي تحتوي على تطبيقات دائمة للقوائم المرتبطة، بالإضافة إلى المصفوفات والقواميس والمجموعات الدائمة. ^{[ 24 ]}

تستخدم لغة Elm تطبيقًا مخصصًا لنموذج كائن المستند الافتراضي (DOM) يستفيد من طبيعة بيانات Elm المستمرة. وفي عام 2016، أفاد مطورو Elm أن نموذج كائن المستند الافتراضي هذا يسمح للغة Elm بعرض صفحات HTML بشكل أسرع من أطر عمل JavaScript الشائعة مثل React و Ember و Angular . ^{[ 25 ]}

جافا

لغة برمجة جافا ليست وظيفية بالدرجة الأولى. مع ذلك، تتضمن حزمة JDK الأساسية java.util.concurrent بنيتين ثابتتين هما CopyOnWriteArrayList و CopyOnWriteArraySet، تُنفذان باستخدام تقنيات النسخ عند الكتابة. أما تطبيق الخرائط المتزامنة المعتاد في جافا، ConcurrentHashMap، فهو غير ثابت. تتوفر مجموعات ثابتة بالكامل في مكتبات خارجية، ^{[ 26 ]} أو لغات JVM أخرى.

جافا سكريبت

يُستخدم إطار عمل React الشهير لتطوير واجهات المستخدم الأمامية بلغة JavaScript بشكل متكرر مع نظام إدارة حالة يُطبّق بنية Flux ، ^{[ 27 ]}^{[ 28 ]} ومن أشهر تطبيقاتها مكتبة Redux في JavaScript . تستوحي مكتبة Redux تصميمها من نمط إدارة الحالة المُستخدم في لغة البرمجة Elm، ما يعني أنها تُلزم المستخدمين بالتعامل مع جميع البيانات على أنها بيانات دائمة. ^[²⁹^] ونتيجةً لذلك، يُوصي مشروع Redux في بعض الحالات باستخدام مكتبات لهياكل بيانات دائمة مُحكمة وفعّالة. ويُقال إن هذا يُتيح أداءً أفضل من مقارنة أو نسخ كائنات JavaScript العادية. ^[³⁰^]

تعتمد مكتبة Immutable.js، وهي إحدى مكتبات هياكل البيانات الدائمة، على هياكل البيانات التي وفرتها ونشرتها لغتا Clojure وScala. ^{[ 31 ]} وقد ذُكرت في وثائق Redux كإحدى المكتبات التي توفر خاصية عدم قابلية التغيير. ^{[ 30 ]} وتُضيف Mori.js هياكل بيانات مشابهة لتلك الموجودة في Clojure إلى JavaScript. ^{[ 32 ]} أما Immer.js، فتُقدم منهجًا مبتكرًا حيث يتم "إنشاء الحالة الدائمة التالية عن طريق تغيير الحالة الحالية". ^{[ 33 ]} إلا أن Immer.js تستخدم كائنات JavaScript الأصلية، وليست هياكل بيانات دائمة فعّالة، مما قد يُسبب مشاكل في الأداء عند التعامل مع أحجام بيانات كبيرة.

مقدمة

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

مع ذلك، توفر بعض أنظمة برولوج عملياتٍ مُدمِّرة مثل setarg/3، والتي قد تأتي بأشكالٍ مختلفة، مع أو بدون نسخ، ومع أو بدون تراجع عن تغيير الحالة. وهناك حالاتٌ يُستخدم فيها setarg/3 لتوفير طبقةٍ تصريحيةٍ جديدة، مثل مُحلِّل القيود. ^{[ 35 ]}

سكالا

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

جمع القمامة

نظرًا لأن هياكل البيانات المستمرة غالبًا ما تُنفذ بطريقة تسمح للإصدارات المتتالية من هيكل البيانات بمشاركة الذاكرة الأساسية ^{[ 38 ]،} فإن الاستخدام الأمثل لهذه الهياكل يتطلب عمومًا شكلًا من أشكال نظام جمع البيانات المهملة التلقائي، مثل عدّ المراجع أو التحديد والمسح ^{[ 39 ]} . في بعض المنصات التي تُستخدم فيها هياكل البيانات المستمرة، يُعدّ عدم استخدام جمع البيانات المهملة خيارًا متاحًا، مع العلم أن ذلك قد يؤدي إلى تسرب الذاكرة ، ولكنه قد يكون له في بعض الحالات تأثير إيجابي على الأداء العام للتطبيق ^{[ 40 ] .}

انظر أيضاً

مراجع

1 2 دريسكول جيه آر، سارناك إن، سليتور دي دي، تارجان آر إي (1986). "جعل هياكل البيانات مستدامة". وقائع الندوة السنوية الثامنة عشرة لجمعية ACM حول نظرية الحوسبة - STOC '86 . الصفحات 109-121 . CiteSeerX 10.1.1.133.4630 . doi : 10.1145/12130.12142 . ISBN 978-0-89791-193-1. S2CID 364871 .
1 2 كابلان، حاييم (2001). "هياكل البيانات المستمرة" . دليل هياكل البيانات وتطبيقاتها .
↑ كونشون، سيلفان؛ فيلياتر، جان كريستوف (2008)، "هياكل البيانات شبه المستمرة"، لغات البرمجة والأنظمة ، سلسلة محاضرات في علوم الحاسوب، المجلد 4960، سبرينغر برلين هايدلبرغ، الصفحات 322-336 ، doi : 10.1007/978-3-540-78739-6_25 ، ISBN 9783540787389
↑ تيارك، باجويل، فيليب رومبف (2011). أشجار RRB: متجهات غير قابلة للتغيير بكفاءة . OCLC 820379112 . {{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
↑ برودال، جيرث ستولتينغ؛ ماكريس، كريستوس؛ تسيتشلاس، كوستاس (2006)، "قوائم مرتبة قابلة للتسلسل في أسوأ الحالات ذات وقت ثابت وظيفيًا بحتًا"، الخوارزميات - ESA 2006 ، سلسلة محاضرات في علوم الحاسوب، المجلد 4168، سبرينغر برلين هايدلبرغ، الصفحات 172-183 ، CiteSeerX 10.1.1.70.1493 ، doi : 10.1007/11841036_18 ، ISBN 9783540388753
↑ لينهوف، هانز-بيتر؛ سميد، ميشيل (1994). "استخدام هياكل البيانات المستمرة لإضافة قيود النطاق إلى مشاكل البحث". RAIRO- المعلوماتية النظرية والتطبيقات . 28 (1): 25-49 . doi : 10.1051/ita/1994280100251 .
↑ نيل سارناك؛ روبرت إي. تارجان (1986). "تحديد موقع نقطة مستوية باستخدام أشجار البحث المستمرة" (ملف PDF) . مجلة اتصالات رابطة مكائن الحوسبة . 29 (7): 669-679 . doi : 10.1145/6138.6151 . S2CID 8745316. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 10 أكتوبر 2015. تم الاطلاع عليه بتاريخ 6 أبريل 2011 .
↑ كريس أوكازاكي. "هياكل البيانات الوظيفية البحتة (أطروحة)" (PDF) .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
↑ ليليينزين، أولي (2013). "المجموعات والخرائط المستمرة بشكل متداخل". arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
1 2 هذا المثال مأخوذ من أوكاساكي. انظر قائمة المراجع.
١ ٢ مؤتمر BoostCon (١٣ يونيو ٢٠١٧)، C++Now ٢٠١٧: فيل ناش "الكأس المقدسة؟! شجرة بحثية مستمرة مُرتبطة بمصفوفة تجزئة للغة C++" ، مؤرشف من الأصل بتاريخ ٢١ ديسمبر ٢٠٢١ ، تم استرجاعه بتاريخ ٢٢ أكتوبر ٢٠١٨
↑ فيل، باجويل (2001). "أشجار التجزئة المثالية" .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
↑ "هل وصلنا بعد؟" . InfoQ . تم الاطلاع عليه بتاريخ 22-10-2018 .
↑ ستايندورفر، مايكل جيه؛ فينجو، يورغن جيه. (23 أكتوبر 2015). "تحسين عمليات البحث المُرتبطة بمصفوفات التجزئة لمجموعات JVM غير القابلة للتغيير السريعة والخفيفة" . إشعارات ACM SIGPLAN . 50 (10): 783-800 . doi : 10.1145/2814270.2814312 . ISSN 0362-1340 . S2CID 10317844 .
↑ "لغة هاسكل" . www.haskell.org . تم الاطلاع عليه بتاريخ 22-10-2018 .
↑ "Data.List" . hackage.haskell.org . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ "Data.Map.Strict" . hackage.haskell.org . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ "Data.Set" . hackage.haskell.org . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ "الأداء/المصفوفات - هاسكل ويكي" . wiki.haskell.org . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ "كلوجر - الاختلافات مع لغات ليسب الأخرى" . clojure.org . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ "Clojure - Data Structures" . clojure.org . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ "كلمة رئيسية: قيمة القيم" . InfoQ . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ "Clojure - Atoms" . clojure.org . تم الاطلاع عليه بتاريخ 30-11-2018 .
↑ "core 1.0.0" . package.elm-lang.org . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ "blog/blazing-fast-html-round-two" . elm-lang.org . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ "المجموعات الدائمة (غير القابلة للتغيير) للغة جافا وكوتلن" . github.com . تم الاطلاع عليه بتاريخ 13-12-2023 .
↑ "Flux | بنية التطبيقات لبناء واجهات المستخدم" . facebook.github.io . مؤرشف من الأصل بتاريخ 27-10-2020 . تم الاطلاع عليه بتاريخ 23-10-2018 .
↑ مورا، أوسميل (18 يوليو 2016). "كيفية التعامل مع الحالة في React" . نظام React البيئي . تم الاسترجاع في 23 أكتوبر 2018 .
↑ "اقرأني - ريدكس" . redux.js.org . تم الاطلاع عليه بتاريخ 23-10-2018 .
1 2 "البيانات غير القابلة للتغيير - ريدكس" . redux.js.org . تم الاسترجاع في 23-10-2018 .
↑ "Immutable.js" . facebook.github.io . مؤرشف من الأصل بتاريخ 2015-08-09 . تم الاطلاع عليه بتاريخ 2018-10-23 .
↑ "موري" .
^ "إمير" . جيثب . 26 أكتوبر 2021.
↑ دجامبوليان، آرا م.؛ بويزومولت، باتريس (1993)، تطبيق لغة برولوج - باتريس بويزومولت ، مطبعة جامعة برينستون، رقم ISBN 9780691637709
^ استخدام الزئبق لتنفيذ حل المجال المحدود – هينك فانديكاستيلي، بارت ديموين، يواكيم فان دير أويرا ، 1999
↑ "جوهر البرمجة الكائنية الوظيفية والإمكانات العملية للغة سكالا - مدونة كودسنتريك إيه جي" . مدونة كودسنتريك إيه جي . 31 أغسطس 2015. تاريخ الاطلاع: 23 أكتوبر 2018 .
↑ ClojureTV (2013-01-07)، ذكاء فائق: هياكل البيانات الوظيفية في سكالا - دانيال سبيواك ، تم الاطلاع عليه بتاريخ 23-10-2018
^ "فلاديمير كوستيوكوف - المشاركات / الشرائح" . kostyukov.net . تم الاسترجاع 2018/11/30 .
↑ "الأشياء غير القابلة للتغيير وجمع القمامة" . wiki.c2.com . تم الاطلاع عليه بتاريخ 30-11-2018 .
↑ "الحدود الأخيرة في أداء جافا: إزالة جامع البيانات المهملة" . InfoQ . تم الاطلاع عليه بتاريخ 30 نوفمبر 2018 .

روابط خارجية

تطبيق جافا خفيف الوزن لأشجار الأحمر والأسود المستمرة
هياكل بيانات مستمرة فعّالة في لغة C# ( مؤرشفة بتاريخ ٢١ ديسمبر ٢٠١٧ على موقع Wayback Machine)
PersistentBST على GitHub - مستودع GitHub يحتوي على تطبيقات لأشجار البحث الثنائية المستمرة باستخدام تقنيات Fat Nodes وCopy-on-Write وPath Copying. لاستخدام تطبيقات أشجار البحث الثنائية المستمرة، ما عليك سوى استنساخ المستودع واتباع التعليمات الواردة في ملف README.

[Driscoll-1] 1 2 دريسكول جيه آر، سارناك إن، سليتور دي دي، تارجان آر إي (1986). "جعل هياكل البيانات مستدامة". وقائع الندوة السنوية الثامنة عشرة لجمعية ACM حول نظرية الحوسبة - STOC '86 . الصفحات 109-121 . CiteSeerX 10.1.1.133.4630 . doi : 10.1145/12130.12142 . ISBN 978-0-89791-193-1. S2CID 364871 .

[kaplan2-2] 1 2 كابلان، حاييم (2001). "هياكل البيانات المستمرة" . دليل هياكل البيانات وتطبيقاتها .

[3] كونشون، سيلفان؛ فيلياتر، جان كريستوف (2008)، "هياكل البيانات شبه المستمرة"، لغات البرمجة والأنظمة ، سلسلة محاضرات في علوم الحاسوب، المجلد 4960، سبرينغر برلين هايدلبرغ، الصفحات 322-336 ، doi : 10.1007/978-3-540-78739-6_25 ، ISBN 9783540787389

[4] تيارك، باجويل، فيليب رومبف (2011). أشجار RRB: متجهات غير قابلة للتغيير بكفاءة . OCLC 820379112 . {{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

[5] برودال، جيرث ستولتينغ؛ ماكريس، كريستوس؛ تسيتشلاس، كوستاس (2006)، "قوائم مرتبة قابلة للتسلسل في أسوأ الحالات ذات وقت ثابت وظيفيًا بحتًا"، الخوارزميات - ESA 2006 ، سلسلة محاضرات في علوم الحاسوب، المجلد 4168، سبرينغر برلين هايدلبرغ، الصفحات 172-183 ، CiteSeerX 10.1.1.70.1493 ، doi : 10.1007/11841036_18 ، ISBN 9783540388753

[6] لينهوف، هانز-بيتر؛ سميد، ميشيل (1994). "استخدام هياكل البيانات المستمرة لإضافة قيود النطاق إلى مشاكل البحث". RAIRO- المعلوماتية النظرية والتطبيقات . 28 (1): 25-49 . doi : 10.1051/ita/1994280100251 .

[sarnak2-7] نيل سارناك؛ روبرت إي. تارجان (1986). "تحديد موقع نقطة مستوية باستخدام أشجار البحث المستمرة" (ملف PDF) . مجلة اتصالات رابطة مكائن الحوسبة . 29 (7): 669-679 . doi : 10.1145/6138.6151 . S2CID 8745316. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 10 أكتوبر 2015. تم الاطلاع عليه بتاريخ 6 أبريل 2011 .

[okasaki2-8] كريس أوكازاكي. "هياكل البيانات الوظيفية البحتة (أطروحة)" (PDF) .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=

[9] ليليينزين، أولي (2013). "المجموعات والخرائط المستمرة بشكل متداخل". arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=

[auto-10] 1 2 هذا المثال مأخوذ من أوكاساكي. انظر قائمة المراجع.

[:1-11] ١ ٢ مؤتمر BoostCon (١٣ يونيو ٢٠١٧)، C++Now ٢٠١٧: فيل ناش "الكأس المقدسة؟! شجرة بحثية مستمرة مُرتبطة بمصفوفة تجزئة للغة C++" ، مؤرشف من الأصل بتاريخ ٢١ ديسمبر ٢٠٢١ ، تم استرجاعه بتاريخ ٢٢ أكتوبر ٢٠١٨

[12] فيل، باجويل (2001). "أشجار التجزئة المثالية" .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=

[13] "هل وصلنا بعد؟" . InfoQ . تم الاطلاع عليه بتاريخ 22-10-2018 .

[14] ستايندورفر، مايكل جيه؛ فينجو، يورغن جيه. (23 أكتوبر 2015). "تحسين عمليات البحث المُرتبطة بمصفوفات التجزئة لمجموعات JVM غير القابلة للتغيير السريعة والخفيفة" . إشعارات ACM SIGPLAN . 50 (10): 783-800 . doi : 10.1145/2814270.2814312 . ISSN 0362-1340 . S2CID 10317844 .

[15] "لغة هاسكل" . www.haskell.org . تم الاطلاع عليه بتاريخ 22-10-2018 .

[16] "Data.List" . hackage.haskell.org . تم الاطلاع عليه بتاريخ 23-10-2018 .

[17] "Data.Map.Strict" . hackage.haskell.org . تم الاطلاع عليه بتاريخ 23-10-2018 .

[18] "Data.Set" . hackage.haskell.org . تم الاطلاع عليه بتاريخ 23-10-2018 .

[19] "الأداء/المصفوفات - هاسكل ويكي" . wiki.haskell.org . تم الاطلاع عليه بتاريخ 23-10-2018 .

[20] "كلوجر - الاختلافات مع لغات ليسب الأخرى" . clojure.org . تم الاطلاع عليه بتاريخ 23-10-2018 .

[21] "Clojure - Data Structures" . clojure.org . تم الاطلاع عليه بتاريخ 23-10-2018 .

[22] "كلمة رئيسية: قيمة القيم" . InfoQ . تم الاطلاع عليه بتاريخ 23-10-2018 .

[23] "Clojure - Atoms" . clojure.org . تم الاطلاع عليه بتاريخ 30-11-2018 .

[24] "core 1.0.0" . package.elm-lang.org . تم الاطلاع عليه بتاريخ 23-10-2018 .

[25] "blog/blazing-fast-html-round-two" . elm-lang.org . تم الاطلاع عليه بتاريخ 23-10-2018 .

[26] "المجموعات الدائمة (غير القابلة للتغيير) للغة جافا وكوتلن" . github.com . تم الاطلاع عليه بتاريخ 13-12-2023 .

[27] "Flux | بنية التطبيقات لبناء واجهات المستخدم" . facebook.github.io . مؤرشف من الأصل بتاريخ 27-10-2020 . تم الاطلاع عليه بتاريخ 23-10-2018 .

[28] مورا، أوسميل (18 يوليو 2016). "كيفية التعامل مع الحالة في React" . نظام React البيئي . تم الاسترجاع في 23 أكتوبر 2018 .

[29] "اقرأني - ريدكس" . redux.js.org . تم الاطلاع عليه بتاريخ 23-10-2018 .

[:0-30] 1 2 "البيانات غير القابلة للتغيير - ريدكس" . redux.js.org . تم الاسترجاع في 23-10-2018 .

[31] "Immutable.js" . facebook.github.io . مؤرشف من الأصل بتاريخ 2015-08-09 . تم الاطلاع عليه بتاريخ 2018-10-23 .

[32] "موري" .

[33] "إمير" . جيثب . 26 أكتوبر 2021.

[34] دجامبوليان، آرا م.؛ بويزومولت، باتريس (1993)، تطبيق لغة برولوج - باتريس بويزومولت ، مطبعة جامعة برينستون، رقم ISBN 9780691637709

[35] استخدام الزئبق لتنفيذ حل المجال المحدود – هينك فانديكاستيلي، بارت ديموين، يواكيم فان دير أويرا ، 1999

[36] "جوهر البرمجة الكائنية الوظيفية والإمكانات العملية للغة سكالا - مدونة كودسنتريك إيه جي" . مدونة كودسنتريك إيه جي . 31 أغسطس 2015. تاريخ الاطلاع: 23 أكتوبر 2018 .

[37] ClojureTV (2013-01-07)، ذكاء فائق: هياكل البيانات الوظيفية في سكالا - دانيال سبيواك ، تم الاطلاع عليه بتاريخ 23-10-2018

[38] "فلاديمير كوستيوكوف - المشاركات / الشرائح" . kostyukov.net . تم الاسترجاع 2018/11/30 .

[39] "الأشياء غير القابلة للتغيير وجمع القمامة" . wiki.c2.com . تم الاطلاع عليه بتاريخ 30-11-2018 .

[40] "الحدود الأخيرة في أداء جافا: إزالة جامع البيانات المهملة" . InfoQ . تم الاطلاع عليه بتاريخ 30 نوفمبر 2018 .

[ ١ ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]،

[ 10 ]

[ ١٢ ]

[ ١٣ ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]،

[ 39 ]

[ 40 ] .

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗