مرتب‌سازی خارجی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مرتب‌سازی خارجی (به انگلیسی: External Sorting) اصطلاحی است که به دسته ای از الگوریتم های مرتب سازی که برای sort کردن مقادیر بزرگ داده به کار میروند ، اتلاق میشود . مرتب سازی خارجی زمانی به کار میرود که محدودیت در حافظه اصلی (عموماً RAM) وجود دارد و در عوض داده به جای این که روی RAM قرار بگیرد روی حافظه ای خارجی و کندتر قرار داشته باشد (مثلاً روی Hard drive).

External Sorting معمولاً از استراتژی sort-merge استفاده میکند. در فرایند مرتب سازی تکه های به اندازه کافی کوچک داده که در حافظه اصلی (RAM) جا میگیرند ، از فایل مورد نظر خوانده شده ، مرتب سازی شده ، و در یک فایل کمکی نوشته و ذخیره میشوند. در مرحله ادغام ، تکه فایل های ذخیره شده با هم ترکیب میشوند و یک فایل بزرگ و واحد و در عین حال مرتب شده را میسازند .

مرتب سازی ادغامی خارجی[ویرایش]

الگوریتم external merge sort مثالی از External Sorting میباشد ، که تکه های داده را که در RAM قرار میگیرند مرتب سازی میکند ، سپس تکه هایی که مرتب شده‌اند را با هم ادغام میکند. به طور مثال برای مرتب کردن یک فایل با حجم 900MB ، فقط 100 MB حافظه RAM در اختیار داریم ، به صورت زیر عمل میکنیم :

۱. 100MB از داده را خوانده و روی RAM قرار میدهیم و توسط یکی از متدهای مرتب سازی مثل مرتب‌سازی سریع آنرا مرتب میکنیم .

۲. داده مرتب شده را روی هارد دیسک ذخیره میکنیم.

۳. این دو مرحله را برای تمام تکه های 100 مگابایتی که در مراحل بعد میخوانیم ، انجام میدهیم ، حالا باید تکه های مرتب شده را ادغام کنیم تا یک فایل خروجی واحد داشته باشیم.

۴. 10MB اول هر فایل مرتب شده را در بافر ورودی در RAM میریزیم (9 فایل با حجم 10MB) و 10MB باقی‌مانده را به بافر خروجی اختصاص میدهیم ( در عمل اگر بافر خروجی را بزرگتر و بافر ورودی را کمی کوچکتر در نظر بگیریم ممکن است عملکرد بهتری داشته باشیم.)

۵. نه مرحله ادغام انجام میدهیم و نتیجه را در بافر خروجی ذخیره میکنیم. اگر بافر خروجی پر شد ، آنرا در فایل نهایی ذخیره میکنیم و بافر خروجی را خالی میکنیم. اگر هر کدام از 9 بافر ورودی خالی شدند آنرا با 10MB بعدی از فایل 100MB مربوطه پر میکنیم تا زمانی که کل فایل 100 مگا بایتی تمام شود. این گامی کلیدی است که باعث میشود external merge به درستی کار کند ، چرا که الگوریتم merge معمولی ، یکباره تکه فایل را میخواند در حالیکه هر تکه نباید به طور کامل لود شود ، بلکه قسمت های پشت سرهم از آن تکه ، آن هم در صورت نیاز باید لود شوند.


ویکی‌پدیای انگلیسی