قائمة التخطي

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

يتم تنفيذ عمليات الإضافة والحذف بشكل مشابه لعمليات القائمة المرتبطة المقابلة، باستثناء أنه يجب إدراج العناصر "الطويلة" في أو حذفها من أكثر من قائمة مرتبطة واحدة.

${\displaystyle {\mathcal {O}}(n)}$تتيح العمليات التي تجبرنا على زيارة كل عقدة بترتيب تصاعدي (مثل طباعة القائمة بأكملها) فرصةً لإجراء عملية إزالة عشوائية لهيكل مستوى قائمة التخطي بطريقة مثلى، مما يجعل قائمة التخطي${\displaystyle {\mathcal {O}}(\log n)}$وقت البحث. (اختر مستوى العقدة المحدودة رقم i ليكون 1 زائد عدد مرات القسمة الممكنة لـ i على 2 قبل أن يصبح الناتج فرديًا. كذلك، i=0 لرأسية اللانهاية السالبة نظرًا لوجود حالة خاصة معتادة لاختيار أعلى مستوى ممكن للعقد اللانهائية السالبة و/أو الموجبة). مع ذلك، يسمح هذا أيضًا بمعرفة مواقع جميع العقد التي تتجاوز المستوى 1 وحذفها.

بدلاً من ذلك، يمكن جعل بنية المستوى شبه عشوائية بالطريقة التالية:

اجعل جميع العقد من المستوى 1 j ← 1 طالما أن عدد العقد في المستوى j أكبر من 1، لكل عقدة رقم i في المستوى j ، إذا كان i فرديًا ولم تكن i هي العقدة الأخيرة في المستوى j اختر عشوائيًا ما إذا كنت تريد ترقيته إلى المستوى j+1 أما إذا كان i زوجيًا ولم تتم ترقية العقدة i-1 قم بترقيته إلى المستوى j+1 نهاية الشرط، كرر j ← j + 1 يكرر

على غرار النسخة غير العشوائية، لا يتم إجراء التوزيع شبه العشوائي إلا عندما يكون هناك سبب آخر لتشغيلها${\displaystyle {\mathcal {O}}(n)}$العملية (التي تزور كل عقدة).

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

قد يكون من المغري إجراء "التحسين" التالي: في الجزء الذي يقول "بعد ذلك، لكل i ..."، تجاهل إجراء رمي العملة لكل زوج من الأعداد الزوجية والفردية. فقط قم برمي العملة مرة واحدة لتحديد ما إذا كنت سترقي الأعداد الزوجية فقط أو الأعداد الفردية فقط. بدلاً من ذلك${\displaystyle {\mathcal {O}}(n\log n)}$لو تم رمي العملة، فلن يكون هناك سوى${\displaystyle {\mathcal {O}}(\log n)}$لسوء الحظ، يمنح هذا المستخدم المُهاجم فرصة 50/50 للتخمين الصحيح بأن جميع العُقد ذات الأرقام الزوجية (من بين العُقد في المستوى 1 أو أعلى) أعلى من المستوى 1. وذلك على الرغم من أن احتمالية تخمين أن عقدة معينة في المستوى N ضئيلة للغاية، حيث N عدد صحيح .

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

كما هو موضح أعلاه، فإن قائمة التخطي قادرة على إنجاز المهام بسرعة${\displaystyle {\mathcal {O}}(\log n)}$إدخال القيم وإزالتها من تسلسل مُرتب، لكن العملية بطيئة.${\displaystyle {\mathcal {O}}(n)}$عمليات البحث عن القيم في موضع معين في التسلسل (أي إرجاع القيمة رقم 500)؛ ومع ذلك، يمكن تحسين سرعة عمليات البحث المفهرسة ذات الوصول العشوائي من خلال تعديل بسيط.${\displaystyle {\mathcal {O}}(\log n)}$.

لكل رابط، قم أيضًا بتخزين عرض الرابط. يُعرَّف العرض بأنه عدد روابط الطبقة السفلية التي يتم اجتيازها بواسطة كل رابط من روابط "المسار السريع" في الطبقة العليا.

على سبيل المثال، إليك عرض الروابط في المثال الموجود أعلى الصفحة:

 1 10 o---> o---------------------------------------------------------> o المستوى الأعلى 1 3 2 5 o---> o--------------> o--------> o-----------> o المستوى 3 1 2 1 2 3 2 o---> o---------> o---> o--------> o--------------> o--------> o المستوى 2 1 1 1 1 1 1 1 1 1 1 1 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o المستوى السفلي الرأس 1 2 3 4 5 6 7 8 9 10 لا شيء عقدة عقدة عقدة عقدة عقدة عقدة عقدة عقدة

لاحظ أن عرض الرابط ذي المستوى الأعلى يساوي مجموع عروض الروابط المكونة له (أي أن الرابط ذو العرض 10 يمتد على الروابط ذات العروض 3 و2 و5 التي تقع أسفله مباشرة). وبالتالي، فإن مجموع جميع العروض متساوٍ في كل مستوى (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2).

لفهرسة قائمة التخطي والعثور على القيمة رقم i، اجتز قائمة التخطي مع حساب عرض كل رابط تم اجتيازه تنازليًا. انزل مستوىً واحدًا كلما كان العرض التالي كبيرًا جدًا.

على سبيل المثال، للعثور على العقدة في الموضع الخامس (العقدة 5)، انتقل عبر رابط بعرض 1 في المستوى الأعلى. الآن، يلزم أربع خطوات أخرى، لكن العرض التالي في هذا المستوى هو 10، وهو كبير جدًا، لذا انزل مستوى واحدًا. انتقل عبر رابط بعرض 3. بما أن خطوة أخرى بعرض 2 ستكون بعيدة جدًا، انزل إلى المستوى الأدنى. الآن، انتقل عبر الرابط الأخير بعرض 1 للوصول إلى المجموع التراكمي المستهدف وهو 5 (1+3+1).

دالة lookupByPositionIndex(i) العقدة ← الرأس i ← i + 1 # لا تحسب الرأس كخطوة للمستوى من الأعلى إلى الأسفل do while i ≥ node.width[level] do # إذا لم تكن الخطوة التالية بعيدة جدًا i ← i - node.width[level] # اطرح العرض الحالي node ← node.next[level] # تقدم للأمام عند المستوى الحالي repeat repeat return node.value end function

تم تفصيل طريقة تنفيذ الفهرسة هذه في كتاب "A skip list cookbook" بقلم ويليام بو ^{[ 7 ]}