در external merge sort و به طور خاص two-way merge sort ما در pass اول، همه صفحات رو یکی یکی می خونیم و مرتب می کنیم که این نیاز به فقط یک بافر داره.
در pass دوم، دو تا دوتا این صفحات مرتب شده رو مرج می کنیم. این جا با دو تا بافر ورودی و یک خروجی مشکل حل میشه، یعنی با یک بافر، صفحه اول، با بافر دیگه، صفحه دوم، و جواب مرج توی بافر خروجی.
حالا برای pass سوم که صفحاتی که باید مرج بشن ۲ صفحه ای هستن، چه طوری می تونیم با یک بافر ورودی یک دوصفحه ایِ مرتب شده رو با یکی دیگه مرج کنیم؟
در واقع سوالم اینه که چه طوری این دو صفحه مرتب شده رو توی یک بافر (یک صفحه بافر) میاریم؟
سوالمو خودم الان فکر کنم می تونم جواب بدم.
این بافر صرفا برای انتقال استفاده میشه. می تونیم صفحه اول که مرتب میشه رو بفرستیم رو حافظه و بعد صفحه بعدی رو.
اگر موافقید اعلام کنید(یا حداقل اعلام وجود کنید :دی)
در مورد سوال شما اطلاعاتی ندارم، دلیل جواب ندادن هم همین بی اطلاعی بود.
صرفا اعلام وجود ...
سلام .
اول اینکه اگه سوال شما مدتیه که جوابی بهش داده نشده و کسی نظری نداده مطمئن باشید دیده نشده و به آرشیو رفته. میتونستید با یه ارسال اون رو دوباره بالا بیارید تا اگه کسی باشه که بتونه کمکت کنه، سوالت رو ببینه
دوما اعلام وجود و اینا چیه دوست من نوشتی
در مورد سوالتون چون تجربشه نوشتنش رو دارم یکم توضیح میدم :
خب ببینید همونطوری که خودتون هم به نتیجه رسیدین دقیقا کار بافرها برای دریافت اطلاعات از فایل (که همون واحد های صفحه یا معمولترش همون بلاک هستش) و نوشتن اطلاعات خروجی مراحل الگوریتم در فایل هستش . در مورد الگوریتم two-way Ext Merge Sort هم بافرها نقش زیر رو دارند.
مرحله اول خب کاملا معلومه شما هر صفحه رو میاری تو حافظه (توسط یک بافر ورودی) و اعدد داخلش رو مرتب میکنی (فرض ۳ تا عدد داخل هر صفحه قرار گرفته) و دوباره این صفحه مرتب شده رو میریزی رو فایل (توسط یک بافر خروجی )
مرحله دوم چون شما هر صفحه رو جداگانه مرتب کردی پس مجبوری یه واحد بالاتر یعنی دو تا صفحه رو با هم بیاری تو حافظه و مقایسه و مرتبشون کنی
پس : ابتدا صفحه اول بعد صفحه دوم رو میاری تو حافظه (اعداد داخل هر دو صفحه مرتب شده هستند) حالا با همون الگوریتم merge این ۶ تا عدد متعلق به دو صفحه رو باید مرتب کنی . فقط نکته ای رو که باید توجه کنیم اینه که چون ما واحد انتقالمون صفحه هستش پس وقتی ترتیب ۳ تا عدد رو (توسط الگوریتم merge) از این ۶ تا عدد به دست آوردیم همون لحظه بافر خروجی رو روی فایل درون یه صفحه ذخیره میکنیم (به این نکته هم باید توجه داشت که هر عددی که در طی الگوریتم merge انتخاب شد باید درون بافر/صفحه خروجی قرار گیرد) . بعد دوباره ترتیب ۳ عدد بعدی رو هم که به دست آوردیم اونا رو هم توی یه صفحه دیگه روی فایل مینویسیم . به این ترتیب تعداد بافر های (هم اندازه صفحات) مورد نیاز مرحله دوم الگوریتم ۳ تا هستش (۲ تا ورودی و ۱ خروجی)
مابقی کار رو هم فک کنم خودتون دیگه بلد باشید
البته پیاده سازی مرحله دوم و در کل این الگوریتم یکم جزعی تر هست و حتی میشه با تغییرات روی اون خ کاراترش کرد(مثلا افزایش بافرها)، حالا اگه خواستین بگین تا بیشتر توضیح بدم ولی فک کنم با توجه به اینکه خودتون هم به نتیجه رسیدین همین توضیح کافی باشه . کلیتش همین بود که توضیح دادم
موفق باشید
این موضوع هم جز سرفصل ارشده؟
من که اولین باره میبینم
(۱۳ دى ۱۳۹۳ ۱۲:۳۷ ق.ظ)nazanin2020 نوشته شده توسط: این موضوع هم جز سرفصل ارشده؟
من که اولین باره میبینم
خیر جزو سرفصل درس پایگاه داده م در دانشگاه بود (دکتر شاکری، دانشگاه تهران).
ممنون
واقعا دیدمش موندم این از کجا اومده
