Bài giảng Phân tích thiết kế thuật toán: Chương 4 - Nguyễn Văn Linh

Bài giảng "Phân tích thiết kế thuật toán - Chương 4: Cấu trúc dữ liệu và giải thuật lưu trữ ngoài" cung cấp cho người học các kiến thức: Mục tiêu, mô hình và đánh giá các xử lý ngoài, sắp xếp ngoài, lưu trữ thông tin trong tập tin. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế thuật toán: Chương 4 - Nguyễn Văn Linh CHƯƠNG4: CẤUTRÚCDỮLIỆUVÀ GIẢITHUẬTLƯUTRỮNGOÀI NguyễnVănLinh KhoaCôngnghệThôngtin&Truyềnthông ĐẠIHỌCCẦNTHƠ nvlinh@cit.ctu.edu.vnNguyễn Văn Linh NỘIDUNG• Mụctiêu.• Môhìnhvàđánhgiácácxửlýngoài.• Sắpxếpngoài.• Lưutrữthôngtintrongtậptin: – Tậptintuầntự – Tậptinbảngbăm – Tậptinchỉmục – TậptinBcâyNguyễn Văn Linh MỤCTIÊU • Biếtmôhìnhxửlýngoài. • Hiểutiêuchuẩnđểđánhgiágiảithuậtxửlý ngoài.Vậndụngtrongviệccảitiếngiảithuậtxử lýngoài. • Hiểugiảithuậtsắpxếptrộnđểsắpxếpngoàivà phươngphápcảitiếntốcđộsắpxếptrộn. • Hiểucáchthứctổchứclưutrữvàcácgiảithuật tìmkiếm,xen,xoáthôngtintrêncáctậptintuần tự,tậptinchỉmục,tậptinbảngbăm. • Vậndụngđượccáchthứctổchứclưutrữvàcác giảithuậttìmkiếm,xen,xoáthôngtintrêntậptin Bcây.Nguyễn Văn Linh Tạisaophảixửlíngoài• Trongcácgiảithuậtmàchúngtađãđềcậptừtrướctớinay, chúngtađãgiảsửrằngsốlượngcácdữliệuvàolàkhánhỏ đểcóthểchứahếtởbộnhớtrong(mainmemory).• Nhưngđiềugìsẽxảyranếutamuốnxửlýphiếuđiềutra dânsốtoànquốchaythôngtinvềquảnlýđấtđaicảnước chẳnghạn?• Trongcácbàitoánnhưvậy,sốlượngdữliệuvượtquákhả nănglưutrữcủabộnhớtrong.• Ðểcóthểgiảiquyếtcácbàitoánđóchúngtaphảidùngbộ nhớngoàiđểlưutrữvàxửlý.• Cácthiếtbịlưutrữngoàinhưbăngtừ,đĩatừđềucókhả nănglưutrữlớnnhưngđặcđiểmtruynhậphoàntoànkhác vớibộnhớtrong.• Chúngtacầntìmcáccấutrúcdữliệuvàgiảithuậtthíchhợp choviệcxửlýdữliệulưutrữtrênbộnhớngoài Nguyễn Văn Linh Môhìnhxửlíngoài• Hệđiềuhànhchiabộnhớngoàithànhcáckhối(block)cókíchthướcbằng nhau,kíchthướcnàythayđổitùythuộcvàohệđiềuhànhnhưngnóichung làtừ512bytesđến4096bytes.• Cóthểxemmộttậptinbaogồmnhiềumẩutinđượclưutrongcáckhối.• Mỗikhốilưumộtsốnguyênvẹncácmẩutin.• Kiểudữliệutậptinlàkiểuthíchhợpnhấtchoviệcbiểudiễndữliệu đượclưutrongbộnhớngoài. Ghi Ghi Bộnhớ Bộ nhớ Bộnhớ trong đệm ngoài Đọc Đọc Mỗilầntruyxuất1mẩutin Mỗilầntruyxuất1khối Nguyễn Văn Linh Đánhgiácácgiảithuậtxửlýngoài• Ðốivớibộnhớngoàithìthờigiantìmmộtkhốiđểđọc vàobộnhớtronglàrấtlớnsovớithờigianthaotáctrêndữ liệutrongkhốiđó.• Chúngtatậptrungvàoviệcxétsốlầnđọckhốivàobộ nhớtrongvàsốlầnghikhốirabộnhớngoài,tagọichung làphéptruyxuấtkhối(blockaccess).• Nếusốlầntruyxuấtkhốiítthìgiảithuậtcóhiệuquả.• Đểcảitiếngiảithuật,takhôngthểtìmcáchtăngkích thướcmộtkhối(Vìkíchthướccáckhốilàcốđịnh)mà chúngtaphảitìmcáchgiảmsốlầntruyxuấtkhối.Nguyễn Văn Linh Sắpxếpngoài• Sắpxếpngoàilàsắpxếpdữliệuđượctổchức thànhmộttậptinlưutrongbộnhớngoài.• Mỗitậptinbaogồmnhiềumẩutin,mỗimẩutin baogồmnhiềutrường,trongđócómộttrường khoá.• Tươngtựnhưsắpxếptrong,sắpxếpngoàilàsự tổchứclạicácmẩutinsaochocáckhóacủa chúngđượcsắpthứtựtươngứngvớiquyluật sắpxếp.Nguyễn Văn Linh Sắpxếptrộn: Kháiniệmvềđường• Ðườngđộdàiklàmộttậphợpkmẩutinđãđượcsắpthứtự theokhoá.• Chotậptinchứacácmẩutinr1,r2,...,rn,tanóitậptinđượctổ chứcthànhđườngcóđộdàiknếutachiatậptinthànhcác đoạnkmẩutinliêntiếpvàmỗiđoạnlàmộtđường,đoạn cuốicóthểkhôngcóđủkmẩutin,trongtrườnghợpnàyta gọiđoạnấylàđuôi(tail).• Vídụ:Tậptingồm14mẩutincókhóalàcácsốnguyên đượctổchứcthành4đườngđộdài3vàmộtđuôicóđộdài2 5 6 9 13 26 27 1 5 8 12 14 17 23 25 Nguyễn Văn Linh Sắpxếptrộn:Giảithuật• ÐểsắpxếptậptinFcónmẩutintasửdụng4tậptinF1,F2, G1vàG2.• PhânphốicácmẩutincủatậptinđãchoFluânphiênvàotrong haitậptinF1F2.Nhưvậyhaitậptinnàyxemnhưđượctổ chứcthànhcácđườngđộdài1.• Bước1:Ðọc2đường,mỗiđườngđộdài1từh ...