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