جميع القيم الأصغر الأقرب

في علوم الحاسوب ، تُعرف مشكلة إيجاد جميع القيم الأصغر الأقرب (ANSV) بأنها: بالنظر إلى مصفوفة${\displaystyle A[1..n]}$، احسب لكل موضع${\displaystyle i}$الفهرس ${\displaystyle P[i]=\max\{\,j<i\mid A[j]<A[i]\,\}}$باستخدام قيمة حارس (مثل${\displaystyle 0}$) عندما لا يكون هناك مثل هذا${\displaystyle j}$موجود. القيمة الأصغر المقابلة هي${\displaystyle A[P[i]]}$تشير بعض العروض التقديمية إلى${\displaystyle A[P[i]]}$لكن العديد من التطبيقات تتطلب الفهارس${\displaystyle P[i]}$.

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

لنفترض أن المدخل هو متتالية فان دير كوربوت الثنائية

0، 8، 4، 12، 2، 10، 6، 14، 1، 9، 5، 13، 3، 11، 7، 15.

العنصر الأول من المتتالية (0) ليس له قيمة سابقة. أقرب قيمة أصغر (الوحيدة) قبل 8 و4 هي 0. جميع القيم الثلاث السابقة لـ 12 أصغر، لكن أقربها هي 4. بالاستمرار على نفس المنوال، فإن أقرب القيم الأصغر السابقة لهذه المتتالية (مع الإشارة إلى عدم وجود قيمة أصغر سابقة بشرطة) هي

—, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.

في معظم التطبيقات، يجب حساب مواقع أقرب القيم الأصغر، وليس القيم نفسها، وفي العديد من التطبيقات يجب حساب نفس العملية لعكس التسلسل من أجل إيجاد القيمة الأصغر التالية الأقرب في التسلسل.

يذكر بيركمان وشيبر وفيشكين (1993) العديد من المشكلات الأخرى التي يمكن حلها بكفاءة بالتوازي باستخدام حساب أقرب قيمة أصغر. ومن بينها ما يلي:

• خوارزميات الدمج ، لحساب خطوة الدمج في فرز الدمج . تتكون مدخلات هذه الخوارزميات من مصفوفتين مرتبتين من الأرقام؛ والمخرجات المطلوبة هي نفس مجموعة الأرقام في مصفوفة مرتبة واحدة. عند دمج المصفوفتين المرتبتين، الأولى بترتيب تصاعدي والثانية بترتيب تنازلي، فإن القيمة السابقة لكل قيمة في المخرجات هي إما أقرب قيمة أصغر منها أو أقرب قيمة أصغر منها (أيهما أكبر)، ويمكن حساب موضع كل قيمة في مصفوفة المخرجات المرتبة بسهولة من موضعَي هاتين القيمتين الأصغر منها.
• بناء الأشجار الديكارتية . الشجرة الديكارتية هي بنية بيانات قدمها فيليمين (1980) ودرسها جابو، وبنتلي ، وتارجان (1984) لاحقًا لتطبيقات البحث في النطاقات . كما تظهر الأشجار الديكارتية في تعريف بنيتي بيانات شجرة البحث الثنائية العشوائية (Treap) وشجرة البحث الثنائية العشوائية للبحث الثنائي . تحتوي الشجرة الديكارتية لسلسلة من القيم على عقدة لكل قيمة. جذر الشجرة هو أصغر قيمة في السلسلة؛ أما بالنسبة لأي عقدة أخرى، فإن والد تلك العقدة هو إما أقرب قيمة أصغر سابقة لها أو أقرب قيمة أصغر لاحقة لها (أيهما أكبر). وبالتالي، يمكن بناء الأشجار الديكارتية في وقت خطي باستخدام خوارزمية البحث عن أقرب القيم الأصغر.
• مطابقة الأقواس . إذا تم إدخال سلسلة من أحرف الأقواس المفتوحة والمغلقة، بالإضافة إلى عمق التداخل لكل قوس، فإن التطابق مع كل قوس مفتوح هو القوس المغلق التالي الذي لا يتجاوز عمق تداخله، وبالتالي يمكن إيجاده من خلال حساب جميع القيم الأصغر الأقرب، مع ترجيح الأقواس المغلقة في حالة التعادل. أما إذا لم يتم تحديد أعماق التداخل، فيمكن حسابها باستخدام مجموع البادئات .

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

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

S = بنية بيانات مكدس فارغ جديد، لكل x في تسلسل الإدخال، كرر ما يلي: طالما أن S غير فارغ والعنصر العلوي من S أكبر من أو يساوي x، كرر ما يلي: بوب إس إذا كانت المجموعة S فارغة ، لا توجد قيمة أصغر سابقة لـ x آخر أقرب قيمة أصغر إلى x هي العنصر العلوي في S ادفع x إلى S

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

لا تحتاج خوارزمية تسلسلية خطية أبسط ( بارباي، فيشر ، ونافارو (2012)A[1,n] ، اللمة 1) إلى مكدس؛ إذ تفترض أن تسلسل الإدخال مُعطى كمصفوفة بحجم n، وتخزن فهرس jالقيمة الأصغر السابقة للقيمة رقم i^فيA[i] . P[i]نفترض وجود حد أدنى إجمالي اصطناعي عند A[0]:

for i from 1 to n: j = i-1 بينما A[j] >= A[i]: j = P[j] P[i] = j

أظهر بيركمان وشيبر وفيشكين (1993) كيفية حل مشكلة إيجاد أقرب القيم الأصغر بكفاءة على جهاز الوصول العشوائي المتوازي للقراءة والكتابة المتزامنة . بالنسبة لتسلسل من n قيمة، مخزنة كمصفوفة ، استخدموا شجرة لوغاريتمية مزدوجة لإثبات إمكانية حل المشكلة في زمن O(log  log n ) باستخدام كمية خطية من العمل الكلي. بالنسبة للتسلسلات التي تكون فيها جميع القيم أعدادًا صحيحة في الفترة [1، s ]، حسّن بيركمان وماتياس وراغدي (1998) هذا الحد إلى O(log log log s )؛ كما أظهروا أنه بالنسبة لقيم s الكبيرة بما فيه الكفاية ، فإن الحد الزمني اللوغاريتمي المزدوج السابق هو أفضل ما يمكن تحقيقه للمشكلة. منذ هذا العمل، تم تطوير خوارزميات متوازية لمشكلة إيجاد أقرب القيم الأصغر على نماذج أخرى للحوسبة المتوازية، بما في ذلك الحواسيب المتوازية ذات شبكة اتصالات ذات بنية مكعبة فائقة ، ^{[ 3 ]} ونموذج التوازي المتزامن الضخم . ^{[ 4 ]}    

• بارباي، جيريمي؛ فيشر، يوهانس؛ نافارو، غونزالو (2012)، "أشجار LRM: الفهارس المضغوطة، والفرز التكيفي، والتباديل المضغوطة"، علوم الحاسوب النظرية ، 459 : 26-41 ، arXiv : 1009.5863 ، doi : 10.1016/j.tcs.2012.08.010.
• بيركمان، عمر؛ ماتياس، يوسي؛ راغدي، برابهاكار (1998)، "حدود عليا وسفلى متوازية لوغاريتمية ثلاثية للحد الأدنى والحد الأدنى للمدى على نطاقات صغيرة"، مجلة الخوارزميات ، 28 (2): 197-215 ، doi : 10.1006/jagm.1997.0905.
• بيركمان، عمر؛ شيبر، باروخ ؛ فيشكين، أوزي (1993)، "خوارزميات متوازية لوغاريتمية مزدوجة مثلى تعتمد على إيجاد جميع القيم الأصغر الأقرب"، مجلة الخوارزميات ، 14 (3): 344-370 ، doi : 10.1006/jagm.1993.1018.
• بيرن، مارشال؛ إبستين، ديفيد ؛ تينغ، شانغ هوا (1999)، "البناء المتوازي للأشجار الرباعية والتثليثات النوعية" (ملف PDF) ، المجلة الدولية للهندسة الحسابية والتطبيقات ، 9 (6)، دار النشر العالمية العلمية: 517-532 ، doi : 10.1142/S0218195999000303.
• جابو، هارولد ن .؛ بنتلي، جون لويس ؛ تارجان، روبرت إي. (1984)، "التحجيم والتقنيات ذات الصلة لمسائل الهندسة"، وقائع الندوة السنوية السادسة عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '84 ، نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة، الصفحات 135-143 ، doi : 10.1145/800057.808675 ، ISBN  0-89791-133-4، S2CID 17752833 .
• هي، شين؛ هوانغ، تشون-هسي (2001)، "خوارزمية BSP فعالة من حيث الاتصال لجميع القيم الأصغر الأقرب"، مجلة الحوسبة المتوازية والموزعة ، 61 (10): 1425-1438 ، doi : 10.1006/jpdc.2001.1741.
• كرافتس، د.؛ بلاكستون، سي جي (1996)، "جميع القيم الأصغر الأقرب على المكعب الفائق"، معاملات IEEE للأنظمة المتوازية والموزعة ، 7 (5): 456-462 ، Bibcode : 1996ITPDS...7..456K ، doi : 10.1109/71.503770.
• فيليمين، جان (1980)، "نظرة موحدة على هياكل البيانات"، مجلة الاتصالات ACM ، 23 (4)، نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM: 229-239 ، doi : 10.1145/358841.358852.