پاورپوینت بازيابي سريع داده ها – مرتب سازي (pptx) 14 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 14 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
بازيابي سريع داده ها – مرتب سازي
بازيابي سريع داده ها – مرتب سازي (Finding data quickly – Sorting)
روشهاي بازيابي سريع داده ها چگونه ميباشند؟
يادآوري جستجوي دودويي (Binary Searching)؟
مقايسه با جست وجوي سري(sequential)؟
محدوديت ها يا معايب جست و جوي دودويي کدامند؟
مرتب سازي کليدها (key sorting) چگونه است؟
روش Indexing چيست؟
مزاياي Indexing کدامند؟
بازيابي سريع داده ها
روشهاي بازيابي سريع داده ها چگونه ميباشند؟
يادآوري جستجوي دودويي (Binary Searching)؟
مثال:
يک فايل با رکورد هاي به طول ثابت را در نظر ميگيريم.
فرض کنيم که در جست و جوي رکوردي با مقدار کليدي مشخصي ميباشيم.
حالت اول: اگر فايل مرتب نشده باشد:
بايستي رکورد هاي آنرا يک به يک خوانده و کليد آنها را با مقدار مورد نظر مقايسه کنيم.
اين کار ممکن است به خواندن کليه رکورد ها منتهي شود. (چرا؟)
حالت دوم: اگر فايل بر حسب کليد مورد نظر مرتب شده باشد:
روش بهينه همان جست و جوي دودويي ميباشد. (چرا؟)
الگوريتم آن در شکل 13-6 کتاب موجود است. (با اشتباه چاپي!)
بازيابي سريع داده ها
يادآوري الگوريتم جستجوي دودويي :
int BinarySearch
(FixedRecordFile & File, RecType & obj, KeyType & key)
{
int low = 0; int high = file.NumRecs()-1;
While (low <= high)
{
int guess = (high + low) / 2;
file.ReadByRRN (obj, guess);
if (obj.Key() == key) return 1;
if (obj.Key() < key ) low = guess +1;
else high = guess - 1;
}
return 0;
}
بازيابي سريع داده ها
مقايسه با جست وجوي سري(sequential)؟
مثال:
جستجوي کليد در يک فايل با تعداد 2000=n رکورد.
حالت اول: جست و جوي سري:
تعداد ماکزيمم رکورد هاي خوانده شده برابر با تعداد کل رکورد ها خواهد بود.
ممکن است تا 2000 رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود، تعداد خواندن رکورد نيز دوبل خواهد شد. (چرا؟)
حالت دوم: جست و جوي دودويي:
تعداد ماکزيمم رکورد هاي خونده شده برابر با 1+log(n) خواهد بود.
ممکن است تا1+log(2000) يعني 11رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود، فقط يک خواندن رکورد اضافه مي گردد.
براي جست و جوي دودويي بايستي طول رکورد ها ثابت باشد. (چرا؟)
بازيابي سريع داده ها
محدوديت ها يا معايب جست و جوي دودويي کدامند؟
جست و جوي يک کليد مشخص معمولا بيش از يک يا دو دسترسي به ديسک نياز دارد. (چرا؟)
مثلا در يک فايل با 10000رکورد، 16 يا 17 دسترسي به ديسک لازم خواهد بود.
نگهداري يک فايل بطور مرتب شده هزينه بالايي خواهد داشت. (کدام؟)
هزينه ها؟ ( CPU ، I/O ، متد برنامه نويسي، ... )
انجام مرتب سازي فايل در حافظه اصلي (RAM) فقط در مورد فايل هاي کوچک عملي ميباشد.
در مورد فايل هاي بزرگتر بايستي تعداد زيادي دسترسي به ديسک پيش بيني شود. (چرا؟)
استفاده از RRN براي فايل هاي حاوي رکورد متغير عملي نخواهد بود.
بازيابي سريع داده ها
روش مرتب سازي کليدها (key sorting) چگونه است؟
روشي برای مرتب سازي فايل هاي بزرگ که در حافظه RAM جا نميگيرند.
هنگام مرتب سازي، از آوردن کل رکورد ها به حافظه خودداري ميگردد.
برای مرتب سازی کافيست فقط مقادير کليد رکوردها در حافظه موجود باشد.
همراه با RRN رکوردها! (چرا؟)
دراينصورت مرتب سازي کل کليد ها در حافظه انجام ميشود. (Internal Sort)
سپس بترتيب کليدها، رکوردها را خوانده و در فايل جديدي مينويسيم.
مرتب سازي کليدها (key sorting)
مرتب سازي کليدها (key sorting) چگونه است؟
مثال: