پاورپوینت الگوریتم طراحی 3 (pptx) 28 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 28 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
1
Time complexity of external sort
چون زمان مورد نياز براي خواندن و نوشتن از / بر ديسك بسيار بيشتر از زمان مورد نياز براي انجام محاسبات در CPU است ،
بر خلاف ساير روشهاي مرتب سازي ، پيچيدگي محاسباتي مرتب سازي خارجي بر مبناي تعداد دفعات خواندن / نوشتن بر روي حافظي خارجي استوار است ،نه بر مبناي تعداد عمليات انجام شده در CPU .
2
3
Some important notes
زمان جستجو (Seek Time): زمان قرار گرفتن هد خواندن يا نوشتن در تراک مورد نظر بر روی
ديسک.
اين زمان به تعداد تراک های موجود بين مکان هايی که هد ميخواهد بين آنها حرکت کند ، بستگی دارد.
زمان تاخير (Latency Time) : زمان لازم برای قرار گرفتن سکتور مورد نظر در يک تراک در زير head برای خواندن يا نوشتن.
زمان انتقال (Transmission Time) : زمان انتقال يا ارسال داده از / به ديسک
به / از حافظه اصلی
بلاک (Block) : واحدی از اطلاعات که از ديسک خوانده شده و يا بر روی آن نوشته ميشود.
هر بلاک معمولا دارای چند رکورد است. اين واحد disk page size = B, ناميده میشود.
4
External Sort
فرض کنيد فايلی حاوی 4500 رکورد را ميخواهيد مرتب کنيد ، رکورد های
A1, A2, …. A4500 .
فرض کنيد کامپيوتر در دسترس شما دارای حافظه اصلی برای جای دادن حد اکثر 750 رکورد است.
فايل ورودی بر روی ديسک قرار دارد و در هر بلاک 250 رکورد جاي ميگيرد (B= 250)
فرض کنيد ديسک ديگری بعنوان ديسک موقت (Scratch) در اختيار داريد.
توجه کنيد که قرار است بر روی ديسک ورودی اولیه چيزی ننويسيد.
5
External Sort
2 بلاک داده (500 رکورد = 2× 250) را از ديسک ورودی خوانده و در حافظه اصلی قرار ميدهيم
با استفاده از مثلا Insertion sort یا Heap sort در هر زمان 2 بلاک
(3*250= 500) رکورد را در حافظه اصلی مرتب ميکنيم.
3. داده های مرتب شده را بر روی ديسک موقت می نويسيم.
در اين مرحله ديسک موقت به شکل زير است ، که داده ها در هر رانش (Run) مرتب شده هستند.
ديسک موقت
In Run 1, all 500 records are sorted in the main memory and written on scratch disk.
This is true for all other runs.
6
External Sort, 2 Way Merge
چون فرض کرده ايم که حافظه اصلي دارای حافظه مورد نياز برای 750 رکورد است آنرا به 3 بافر با اندازه 250 رکورد تقسيم ميکنيم.
7
Read the 1st 250 records of Run 1 from scratch disk into Buffer 1
Read the 1st 250 records of Run 2 into Buffer 2
Merge buffers 1 and 2 into Buffer 3.
As soon as buffer 3 gets full,
- write it (250 records) on scratch disk,
- empty buffer 3.
- continue merging the remaining records left in buffers 1 and 2
Note that this process will terminate when buffer 3 gets full 2 times and 2 times writing it on scratch disk is carried on.
8
External Sort, 2 Way Merge
We repeat this procedure for Run 3 & 4, and Run 5 & 6.
At the end of this step we have the following arrangement.
Scratch disk 2
Scratch disk 1
9
External Sort, 2 Way Merge
This process of
coping the 1st 250 records from Run 1 (in scratch disk 1) into Buffer 1,
and the 1st 250 records from Run 2 (in scratch disk 1) into Buffer 2,
Merge them into Buffer 3,
When buffer 3 gets full, Write buffer 3 on Scratch disk 2
Empty Buffer 3
Continue merging the remaining records in buffers 1 and 2 into buffer 3.
When buffer 3 gets full, Write buffer 3 on Scratch disk 2
Empty Buffer 3
Is continued until all Runs from scratch disk 1 in this level are merged into New Runs.
Note that the number of Runs in each level is at most ½ of the
number of Runs in its previous level.