الگوریتم درجا

الگوریتم درجا (به لاتین: in situ) در علم کامپیوتر الگوریتمی است که ورودی را با استفاده از یک داده ساختار با یک حافظهٔ اضافی کوچک و ثابت تبدیل می‌کند. ورودی معمولاً به وسیلهٔ خروجی که هنگام اجرای الگوریتم به وجود می‌آید، دوباره نوشته می‌شود. الگوریتمی که درجا نباشد گاهی نه در محل (not-in-place) یا خارج از محل (out-of-place) نامیده می‌شود.

یک الگوریتم تا زمانی به‌طور رسمی درجا نامیده می‌شود که ورودی به وسیله خروجی بازنویسی شود. در واقع این شرط نه کافی است (در مواردی که داده‌ها به‌طور مرتب نمایش داده شده) و نه لازم است; ممکن است فضای داده خروجی ثابت باشد یا حتی ممکن است قابل شمارش نباشد؛ برای مثال در حالتی که خروجی در (گردش) جریان باشد. ازسوی دیگر، گاهی اوقات ممکن است عملی تر باشد که فضای داده خروجی را حساب کنیم، تا تعیین کنیم که آیا این الگوریتم درجا است یا نه. مانند مثال اول معکوس زیر؛ این باعث می‌شود که تعریف کردن الگوریتمهای درجا به شدت مشکل شود. در کاربردهای نظری مانند کاهش فضای ورود، همیشه از فضای داده‌های خروجی چشم پوشی می‌شود. (در این مورد ضروری است که داده خروجی فقط نوشتنی باشد.)  

مثال

فرض کنید می‌خواهیم آرایه ای n رقمی را معکوس کنیم یکی از راه‌های ساده این است که:

function reverse(a[0..n])
     allocate b[0..n]
     for i from 0 to n
         b[n - i] = a[i]
     return b

متأسفانه، در اینجا به $(n)O$ فضای بیشتر برای ایجاد آرایه b نیاز است و اغلب عمل تخصیص دادن یک عمل کند است. اگر ما دیگر بهa احتیاج نداشته باشیم، می‌توانیم به جای بازنویسی با معکوس خودش از الگوریتم درجای زیر استفاده کنیم:

function reverse-in-place(a[0..n])
     for i from 0 to floor(n/2)
         swap(a[i], a[n-i])

به عنوان مثالی دیگر، تعدادی الگوریتم مرتب سازی هستند که می‌توانند آرایه‌ها را به آرایه‌های درجا مرتب شده بازآرایی کنند، از جمله: مرتب‌سازی حبابی، مرتب‌سازی شانه‌ای، مرتب‌سازی انتخابی، مرتب‌سازی درجی، مرتب‌سازی هرمی و مرتب‌سازی شِل.

مرتب‌سازی سریع معمولاً به عنوان الگوریتم درجا تعریف می‌شود. ولی در واقع یکی نیست. اکثر پیاده سازی‌ها نیازمند $(ngol)O$ فضا برای پشتیبانی از تقسیم و حل بازگشتی هستند.

اکثر الگوریتم انتخابها نیز درجا هستند، اگرچه بعضی از آن‌ها به‌طور قابل ملاحظه‌ای دادهٔ ورودی آرایه را در فرایند یافتن نتیجه نهایی با اندازهٔ ثابت، بازآرایی می‌کنند.

برخی از الگوریتم‌های دستکاری متن مانند اصلاح شده و معکوس ممکن است درجا انجام شوند.

پیچیدگی محاسباتی

در نظریه پیچیدگی محاسباتی، الگوریتمهای درجا شامل همهٔ الگوریتمهای با پیچیدگی فضایی $(1)O$، کلاس پیچیدگی فضا هستند. این کلاس بسیار محدود است؛ که با یک زبان منظم برابری می‌کند. در واقع حتی شامل هیچ یک از مثال‌های ذکر شده در بالا نمی‌شود.

به همین دلیل، ما نیز الگوریتم‌های L را مطرح می‌کنیم، کلاس این مسائل به فضای اضافی $(logn)O$ نیاز دارند تا درجا باشند. اگرچه به نظر می‌رسد که با تعریف قبلی ما در تناقض است، ما باید فرض کنیم که در جهان انتزاعی ورودی ما می‌تواند به‌طور قراردادی بزرگ باشد. بر روی یک کامپیوتر واقعی، یک اشاره گر فقط به یک مقدار فضای ثابت و کوچک نیاز دارد. چون مقدار حافظهٔ فیزیکی محدود است، اما به‌طور کلی $(logn)O$ بیت نیاز است تا اندیس را در لیستی با سایز n مشخص کند.

آیا به این معنی است که مرتب‌سازی سریع یک الگوریتم درجا است؟ هرگز. از لحاظ فنی، این به$(n^{l}og2)O$ فضا نیاز دارد، از آنجایی که هر یک از $(logn)O$ چارچوب پشته شامل تعداد ثابتی اشاره گر هستند. (سایز هر کدام از آن‌ها $(logn)O$ است.)

شناسایی الگوریتمهای درجا با L دارای مفاهیم جالبی است؛ به‌طور مثال، به این معنی است که الگوریتمهای درجای (نسبتاً پیچیده) وجود دارند که تعیین می‌کنند آیا یک مسیر بین دو گره در یک گراف بدون جهت وجود دارد یا نه. مشکل این است که به $(n)O$ فضای اضافی برای استفاده الگوریتمهای معمولی مورد نیاز است. مانند جستجوی عمق اول (یک بیت برای هر گره).

نقش تصادفی

در بسیاری از موارد، فضای مورد نیاز برای یک الگوریتم می‌تواند با استفاده از الگوریتم تصادفی به شدت کاهش یابد. به عنوان مثال، می‌خواهیم بدانیم دو راس درون یک گراف n راسی در یک مؤلفهٔ همبند گراف هستند. الگوریتم درجای ساده شناخته شده‌ای به صورت قطعی برای تعیین این موضوع وجود ندارد، ولی اگر ما به سادگی از یک راس شروع کنیم و به‌طور تصادفی با $^{3}n02$ گام بر روی رئوس پیش برویم، شانس اینکه به راسی که آن را از قبل انتخاب کرده‌ایم برسیم و این دو در یک مولفه همبندی باشند، بالا می‌رود. به‌طور مشابه، الگوریتمهای درجای تصادفی ساده‌ای برای آزمون اولیه وجود دارند. مانند آزمون اولیه میلرـ رابین. و همچنین الگوریتمهای درجای تصادفی ساده وجود دارند، مثل الگوریتم پولارد . برای بررسی بیشتر این پدیده RL و BPL را ببینید.

برنامه‌نویسی تابعی

زبانهای برنامه نویسی تابعی گاهی دلسردکننده‌است. آن‌ها اغلب الگوریتمهای درجایی که داده‌ها را بازنویسی می‌کنند، به‌طور صریح پشتیبانی نمی‌کنند، از این رو این یک نوع اثر زیان‌آور است؛ در عوض، آن‌ها فقط اجازه می‌دهند داده‌های جدید ساخته شود. با این حال، کامپایلرهای زبان‌های تابعی خوب اغلب زمانی که یک شیء ساخته شده بسیار شبیه به شیء موجود باشد، تشخیص می‌دهند و سپس شیء قدیمی توسط آن‌ها دور انداخته می‌شود و این به یک جهش ساده "under-the-hood" بهینه سازی می‌شود.

توجه داشته باشید که ممکن است در اصل برای به دقت ساختن الگوریتمهای درجایی که داده‌ها را تغییر نمی‌دهند (مگر این که داده‌ها دیگر مورد استفاده قرار نگرفته باشند) ولی این در عمل به ندرت انجام می‌شود. ساختمان داده‌های تابعی را ببینید.

منابع

 http://en.wikipedia.org/wiki/In-place_algorithm

پیوند به بیرون

• Table of in-place and not-in-place algorithms