قائمة مرتبطة XOR

📅 آخر تحديث: ٢١ يوليو ٢٠٢٦
✍️ نُشر في: ٢١ يوليو ٢٠٢٦
الموسوعة الحرة

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

وصف

تقوم القائمة المزدوجة المرتبطة العادية بتخزين عناوين عناصر القائمة السابقة واللاحقة في كل عقدة من عقد القائمة، مما يتطلب حقلين للعنوان:

... ABCDE ... –> التالي –> التالي –> التالي –> <– السابق <– السابق <– السابق <–

تقوم قائمة XOR المرتبطة بضغط نفس المعلومات في حقل عنوان واحد عن طريق تخزين عملية XOR الثنائية (المشار إليها هنا بـ ⊕) لعنوان العنصر السابق وعنوان العنصر التالي في حقل واحد:

... ABCDE ... ⇌ أ⊕ ج ⇌ ب⊕ د ⇌ ج⊕ هـ ⇌

بصورة أكثر رسمية:

 الرابط(ب) = العنوان(أ) ⊕ العنوان(ج)، الرابط(ج) = العنوان(ب) ⊕ العنوان(د)، ...

عند استعراض القائمة من اليسار إلى اليمين: إذا كان المؤشر عند العنصر C، يمكن إجراء عملية XOR بين العنصر السابق B والقيمة الموجودة في حقل الربط (B⊕D). وبذلك، يتم الحصول على عنوان D، ويمكن استئناف استعراض القائمة. وينطبق النمط نفسه في الاتجاه المعاكس.

أي addr(D) = link(C) ⊕ addr(B) أين

 link(C) = addr(B)⊕addr(D)

لذا 

 addr(D) = addr(B)⊕addr(D) ⊕ addr(B) addr(D) = addr(B)⊕addr(B) ⊕ addr(D)

منذ

 X⊕X = 0 => addr(D) = 0 ⊕ addr(D)

منذ

 X⊕0 = X => addr(D) = addr(D)

تلغي عملية XOR addr(B)ظهورها مرتين في المعادلة، وكل ما يتبقى لدينا هو addr(D).

لبدء اجتياز القائمة في أي اتجاه من نقطة معينة، يلزم معرفة عنوان عنصرين متتاليين. إذا عُكست عناوين العنصرين المتتاليين، فسيحدث اجتياز القائمة في الاتجاه المعاكس. [ 1 ]

نظرية التشغيل

يكمن المفتاح في العملية الأولى، وخصائص عملية XOR:

  • X⊕X = 0
  • X⊕0 = X
  • X⊕Y = Y⊕X
  • (X⊕Y)⊕Z = X⊕(Y⊕Z)

يحتوي السجل R2 دائمًا على عملية XOR بين عنوان العنصر الحالي C وعنوان العنصر السابق P: C⊕P. تحتوي حقول الربط في السجلات على عملية XOR بين عنواني العنصرين التاليين الأيسر والأيمن، على سبيل المثال L⊕R. ينتج عن عملية XOR بين R2 (C⊕P) وحقل الربط الحالي (L⊕R) النتيجة التالية: C⊕P⊕L⊕R.

  • إذا كان العنصر السابق هو L، فإن P(=L) و L يلغيان بعضهما البعض ويتركان C⊕R.
  • إذا كان العنصر السابق هو R، فإن P(=R) و R يلغي بعضهما البعض، مما يترك C⊕L.

في كل حالة، تكون النتيجة هي عملية XOR بين العنوان الحالي والعنوان التالي. ثم تُجرى عملية XOR بين هذا العنوان والعنوان الحالي في R1، ليتبقى العنوان التالي. أما R2 فيحتوي على زوج XOR المطلوب بين العنوان الحالي (الآن) والعنوان السابق له.

سمات

  • يكفي إجراء عمليتين XOR للانتقال من عنصر إلى آخر، وتكفي نفس التعليمات في كلتا الحالتين. لنفترض قائمة تحتوي على عناصر {…B C D…}، حيث R1 وR2 هما سجلان يحتويان على عنوان العنصر الحالي (مثلاً C) وسجل عمل يحتوي على نتيجة عملية XOR بين العنوان الحالي والعنوان السابق (مثلاً C⊕D). يمكن تمثيل هذه العملية كتعليمات System/360 .
X R2,Link R2 <- C⊕D ⊕ B⊕D (أي B⊕C، حيث "Link" هو حقل الرابط) في السجل الحالي، الذي يحتوي على B⊕D) XR R1,R2 R1 <- C ⊕ B⊕C (أي B، : السجل التالي)
  • يُشار إلى نهاية القائمة بتخيل عنصر قائمة عند العنوان صفر موضوعًا بجوار نقطة النهاية، كما في المثال {0 A B C…}. سيكون حقل الربط عند A هو 0⊕B. يلزم وجود تعليمة إضافية في التسلسل أعلاه بعد عمليتي XOR لاكتشاف نتيجة صفرية في تحديد عنوان العنصر الحالي.
  • يمكن جعل نقطة نهاية القائمة انعكاسية بجعل مؤشر الرابط يساوي صفرًا. المؤشر الصفري هو مرآة . (نتيجة عملية XOR لعناوين الجار الأيسر والأيمن، لكونها متطابقة، تساوي صفرًا).

العيوب

  • لا تستطيع أدوات تصحيح الأخطاء ذات الأغراض العامة تتبع سلسلة XOR، مما يجعل عملية تصحيح الأخطاء أكثر صعوبة؛ [ 2 ]
  • ثمن انخفاض استخدام الذاكرة هو زيادة في تعقيد الكود، مما يجعل الصيانة أكثر تكلفة؛
  • معظم مخططات جمع البيانات المهملة لا تعمل مع هياكل البيانات التي لا تحتوي على مؤشرات حرفية ؛
  • لا تدعم جميع اللغات تحويل الأنواع بين المؤشرات والأعداد الصحيحة، كما أن عملية XOR على المؤشرات غير محددة في بعض السياقات؛
  • أثناء اجتياز القائمة، يلزم عنوان العقدة التي تم الوصول إليها سابقًا لحساب عنوان العقدة التالية، وستكون المؤشرات غير قابلة للقراءة إذا لم يتم اجتياز القائمة - على سبيل المثال، إذا كان المؤشر إلى عنصر قائمة موجودًا في بنية بيانات أخرى؛
  • لا توفر القوائم المرتبطة XOR بعض المزايا المهمة للقوائم المرتبطة المزدوجة، مثل القدرة على حذف عقدة من القائمة بمعرفة عنوانها فقط أو القدرة على إدراج عقدة جديدة قبل أو بعد عقدة موجودة عند معرفة عنوان العقدة الموجودة فقط.

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

الاختلافات

يمكن تطبيق المبدأ الأساسي لقائمة XOR المرتبطة على أي عملية ثنائية قابلة للعكس. استبدال XOR بالجمع أو الطرح يعطي صيغًا مختلفة قليلاً، ولكنها متكافئة إلى حد كبير.

قائمة مرتبطة إضافية

... ABCDE ... ⇌ أ + ج ⇌ ب + د ⇌ ج + هـ ⇌

يتمتع هذا النوع من القوائم بنفس خصائص قائمة XOR المرتبطة، باستثناء أن حقل الارتباط الصفري لا يُعد "نسخة طبق الأصل". ويُحدد عنوان العقدة التالية في القائمة بطرح عنوان العقدة السابقة من حقل الارتباط الخاص بالعقدة الحالية.

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

... ABCDE ... ⇌ CA ⇌ DB ⇌ EC ⇌

يختلف هذا النوع من القوائم عن قائمة XOR التقليدية في أن تسلسل التعليمات اللازمة لاجتياز القائمة للأمام يختلف عن التسلسل اللازم لاجتيازها للخلف. يُحدد عنوان العقدة التالية، عند الانتقال للأمام، بإضافة حقل الربط إلى عنوان العقدة السابقة؛ بينما يُحدد عنوان العقدة التي تسبقها بطرح حقل الربط من عنوان العقدة التالية.

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

انظر أيضاً

مراجع

  1. ↑ "قائمة XOR المرتبطة - قائمة مرتبطة ثنائية فعالة من حيث الذاكرة | المجموعة 1 - GeeksforGeeks" . GeeksforGeeks . 23-05-2011 . تم الاسترجاع في 29-10-2018 .
  2. ↑ غادبوا، ديفيد؛ وآخرون . "الأسئلة الشائعة حول جمع البيانات المهملة - مسودة" . تم الاطلاع عليه في 5 ديسمبر 2018 .