خوارزمية في المكان

تحتاج هذه المقالة إلى مصادر إضافية للتحقق . يُرجى المساعدة في تحسين هذه المقالة عن طريق إضافة مصادر موثوقة . قد يتم الطعن في المواد غير الموثقة وإزالتها. البحث عن المصادر:  "In-place algorithm" – news  · magazines  · books  · scholar  · JSTOR ( January 2015 ) ( Learn how and when to remove this message )

في علوم الكمبيوتر ، الخوارزمية الموجودة في المكان هي خوارزمية تعمل مباشرة على بنية بيانات الإدخال دون الحاجة إلى مساحة إضافية تتناسب مع حجم الإدخال. بعبارة أخرى، تعدل المدخلات في مكانها، دون إنشاء نسخة منفصلة من بنية البيانات. تسمى الخوارزمية غير الموجودة في المكان أحيانًا غير الموجودة في المكان أو خارج المكان .

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

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

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

 دالة عكسية (a[0..n - 1])
     تخصيص b[0..n - 1]
     بالنسبة إلى i من 0 إلى n - 1
         ب[ن − 1 − ي] := أ[ي]
     العودة ب

لسوء الحظ، يتطلب هذا مساحة إضافية قدرها O ( n ) لتوفير المصفوفات aو bفي نفس الوقت. كما أن التخصيص وإلغاء التخصيص غالبًا ما يكونان عمليات بطيئة. نظرًا لأننا لم نعد بحاجة إلى a، فيمكننا بدلاً من ذلك الكتابة فوقه باستخدام عكسه الخاص باستخدام خوارزمية المكان هذه والتي ستحتاج فقط إلى عدد ثابت (2) من الأعداد الصحيحة للمتغيرات المساعدة iو tmp، بغض النظر عن حجم المصفوفة.

 دالة reverse_in_place(a[0..n-1])
      لـ i من 0 إلى floor((n-2)/2)
         tmp := a[i]
         أ[ي] := أ[ن − 1 − ي]
         a[n − 1 − i] := tmp

كمثال آخر، تقوم العديد من خوارزميات الفرز بإعادة ترتيب المصفوفات إلى ترتيب مرتب في مكانها، بما في ذلك: فرز الفقاعات ، وفرز المشط ، وفرز التحديد ، وفرز الإدراج ، وفرز الكومة ، وفرز شل . تتطلب هذه الخوارزميات عددًا قليلًا من المؤشرات، لذا فإن تعقيد مساحتها هو O (log n ) . ^[1]

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

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

من الممكن إجراء بعض خوارزميات معالجة النصوص مثل التقليم والعكس في مكانها.

في نظرية التعقيد الحسابي ، يتضمن التعريف الصارم للخوارزميات الموضعية جميع الخوارزميات ذات التعقيد المكاني O (1) ، فئة DSPACE (1). هذه الفئة محدودة للغاية؛ فهي تساوي اللغات العادية . ^[2] في الواقع، لا تتضمن حتى أيًا من الأمثلة المذكورة أعلاه.

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

إن تحديد الخوارزميات الموجودة في المكان باستخدام L له بعض الآثار المثيرة للاهتمام؛ على سبيل المثال، يعني هذا أن هناك خوارزمية (معقدة إلى حد ما) في المكان لتحديد ما إذا كان هناك مسار بين عقدتين في رسم بياني غير موجه ، ^[3] وهي مشكلة تتطلب مساحة إضافية قدرها O ( n ) باستخدام خوارزميات نموذجية مثل البحث بالعمق أولاً (بت تمت زيارته لكل عقدة). وهذا بدوره ينتج خوارزميات في المكان لمشاكل مثل تحديد ما إذا كان الرسم البياني ثنائي الأجزاء أو اختبار ما إذا كان الرسم البيانيان يحتويان على نفس عدد المكونات المتصلة .

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

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

لاحظ أنه من الممكن من حيث المبدأ إنشاء خوارزميات موضعية بعناية لا تعدل البيانات (ما لم تكن البيانات لم تعد مستخدمة)، ولكن نادرًا ما يتم ذلك في الممارسة العملية.

• جدول خوارزميات الفرز في المكان وغير المكان