数据结构与算法分析第二版英文版课件chapter8

Primaryvs.SecondaryStoragePrimarystorage:Mainmemory(RAM)SecondaryStorage:PeripheraldevicesDiskdrivesTapedrives1/4/20231优秀课件，精彩无限！Primaryvs.SecondaryStoragePComparisonsRAMisusuallyvolatile.RAMisabout1/4milliontimesfasterthandisk.MediumEarly1996Mid1997Early2000RAM$45.007.001.50Disk1Floppy0.500.360.25Tape0.030.010.0011/4/20232优秀课件，精彩无限！ComparisonsMediumEarly1996MiGoldenRuleofFileProcessingMinimizethenumberofdiskaccesses!1.Arrangeinformationsothatyougetwhatyouwantwithfewdiskaccesses.2.Arrangeinformationtominimizefuturediskaccesses.Anorganizationfordataondiskisoftencalledafilestructure(p261).Disk-basedspace/timetradeoff(p74):Compressinformationtosaveprocessingtimebyreducingdiskaccesses.1/4/20233优秀课件，精彩无限！GoldenRuleofFileProcessingDiskDrives1/4/20234优秀课件，精彩无限！DiskDrives12/19/20224优秀课件，精彩无SectorsAsectoristhebasicunitofI/O.Interleavingfactor:Physicaldistancebetweenlogicallyadjacentsectorsonatrack.1/4/20235优秀课件，精彩无限！Sectors12/19/20225优秀课件，精彩无限！TermsLocalityofReference:Whenrecordisreadfromdisk,nextrequestislikelytocomefromnearthesameplaceinthefile.Cluster:Smallestunitoffileallocation,usuallyseveralsectors.Extent:Agroupofphysicallycontiguousclusters.Internalfragmentation:Wastedspacewithinsectorifrecordsizedoesnotmatchsectorsize;wastedspacewithinclusteriffilesizeisnotamultipleofclustersize.1/4/20236优秀课件，精彩无限！TermsLocalityofReference:WhSeekTimeSeektime:TimeforI/Oheadtoreachdesiredtrack.LargelydeterminedbydistancebetweenI/Oheadanddesiredtrack.Track-to-tracktime:Minimumtimetomovefromonetracktoanadjacenttrack.AverageSeektime:Averagetimetoreachatrackforrandomaccess.1/4/20237优秀课件，精彩无限！SeekTimeSeektime:TimeforIOtherFactorsRotationalDelayorLatency:TimefordatatorotateunderI/Ohead.Onehalfofarotationonaverage.At7200rpm,thisis8.3/2=4.2ms.Transfertime:TimefordatatomoveundertheI/Ohead.At7200rpm:Numberofsectorsread/Numberofsectorspertrack*8.3ms.1/4/20238优秀课件，精彩无限！OtherFactorsRotationalDelayDiskSpecExample16.8GBdiskon10platters=1.68GB/platter13,085tracks/platter256sectors/track512bytes/sectorTrack-to-trackseektime:2.2msAverageseektime:9.5ms4KBclusters,32clusters/track.Interleavingfactorof3.5400RPM1/4/20239优秀课件，精彩无限！DiskSpecExample16.8GBdiskDiskAccessCostExample(1)Reada1MBfiledividedinto2048recordsof512bytes(1sector)each.Assumeallrecordsareon8contiguoustracks.Firsttrack:9.5+11.1/2+3x11.1=48.4msRemaining7tracks:2.2+11.1/2+3x11.1=41.1ms.Total:48.4+7*41.1=335.7ms1/4/202310优秀课件，精彩无限！DiskAccessCostExample(1)ReDiskAccessCostExample(2)Reada1MBfiledividedinto2048recordsof512bytes(1sector)each.Assumeallfileclustersarerandomlyspreadacrossthedisk.256clusters.Clusterreadtimeis(3x8)/256ofarotationforabout1ms.256(9.5+11.1/2+11.1x3x(8/256))isabout4119.2ms.1/4/202311优秀课件，精彩无限！DiskAccessCostExample(2)ReHowMuchtoRead?Readtimeforonetrack:9.5+11.1/2+3x11.1=48.4ms.Readtimeforonesector:9.5+11.1/2+(1/256)11.1=15.1ms.Readtimeforonebyte:9.5+11.1/2=15.05ms.Nearlyalldiskdrivesread/writeonesectorateveryI/Oaccess.Alsoreferredtoasapage.P288:8.2ifclustersarespreadrandomlyacrossthedisk?1/4/202312优秀课件，精彩无限！HowMuchtoRead?ReadtimeforBuffersTheinformationinasectorisstoredinabufferorcache.IfthenextI/Oaccessistothesamebuffer,thennoneedtogotodisk.Thereareusuallyoneormoreinputbuffersandoneormoreoutputbuffers.1/4/202313优秀课件，精彩无限！BuffersTheinformationinaseBufferPoolsAseriesofbuffersusedbyanapplicationtocachediskdataiscalledabufferpool.VirtualmemoryusesabufferpooltoimitategreaterRAMmemorybyactuallystoringinformationondiskand“swapping”betweendiskandRAM.1/4/202314优秀课件，精彩无限！BufferPoolsAseriesofbufferBufferPools1/4/202315优秀课件，精彩无限！BufferPools12/19/202215优秀课件，精OrganizingBufferPoolsWhichbuffershouldbereplacedwhennewdatamustberead?First-in,First-out:Usethefirstoneonthequeue.LeastFrequentlyUsed(LFU):Countbufferaccesses,reusetheleastused.LeastRecentlyused(LRU):Keepbuffersonalinkedlist.Whenbufferisaccessed,bringittofront.Reusetheoneatend.If391047353827comeinto3-bufferpool(emptyinitially)?1/4/202316优秀课件，精彩无限！OrganizingBufferPoolsWhichbBufferpoolADT(1)classBufferPool{//(1)MessagePassingpublic:virtualvoidinsert(void*space,intsz,intpos)=0;virtualvoidgetbytes(void*space,intsz,intpos)=0;};classBufferPool{//(2)BufferPassingpublic:virtualvoid*getblock(intblock)=0;virtualvoiddirtyblock(intblock)=0;virtualintblocksize()=0;};1/4/202317优秀课件，精彩无限！BufferpoolADT(1)classBufferDesignIssuesDisadvantageofmessagepassing:Messagesarecopiedandpassedbackandforth.

Disadvantagesofbufferpassing:Theuserisgivenaccesstosystemmemory(thebufferitself)Theusermustexplicitlytellthebufferpoolwhenbuffercontentshavebeenmodified,sothatmodifieddatacanberewrittentodiskwhenthebufferisflushed.Thepointermightbecomestalewhenthebufferpoolreplacesthecontentsofabuffer.1/4/202318优秀课件，精彩无限！DesignIssuesDisadvantageofmProgrammer’sViewofFilesLogicalviewoffiles:Anarrayofbytes.Afilepointermarksthecurrentposition.Threefundamentaloperations:Readbytesfromcurrentposition(movefilepointer)Writebytestocurrentposition(movefilepointer)Setfilepointertospecifiedbyteposition.1/4/202319优秀课件，精彩无限！Programmer’sViewofFilesLogiC++FileFunctions#include<fstream.h>voidfstream::open(char*name,openmodemode);Example:ios::in|ios::binaryvoidfstream::close();fstream::read(char*ptr,intnumbytes);fstream::write(char*ptr,intnumbtyes);fstream::seekg(intpos);fstream::seekg(intpos,ios::curr);fstream::seekp(intpos);fstream::seekp(intpos,ios::end);1/4/202320优秀课件，精彩无限！C++FileFunctions#include<fsExternalSortingProblem:Sortingdatasetstoolargetofitintomainmemory.Assumedataarestoredondiskdrive.Tosort,portionsofthedatamustbebroughtintomainmemory,processed,andreturnedtodisk.Anexternalsortshouldminimizediskaccesses.1/4/202321优秀课件，精彩无限！ExternalSortingProblem:SortiModelofExternalComputationSecondarymemoryisdividedintoequal-sizedblocks(512,1024,etc…)AbasicI/Ooperationtransfersthecontentsofonediskblockto/frommainmemory.Undercertaincircumstances,readingblocksofafileinsequentialorderismoreefficient.(When?)PrimarygoalistominimizeI/Ooperations.Assumeonlyonediskdriveisavailable.1/4/202322优秀课件，精彩无限！ModelofExternalComputationSKeySortingOften,recordsarelarge,keysaresmall.Ex:PayrollentrieskeyedonIDnumberApproach1:Readinentirerecords,sortthem,thenwritethemoutagain.Approach2:Readonlythekeyvalues,storewitheachkeythelocationondiskofitsassociatedrecord.Afterkeysaresortedtherecordscanbereadandrewritteninsortedorder.1/4/202323优秀课件，精彩无限！KeySortingOften,recordsareSimpleExternalMergesort(1)Quicksortrequiresrandomaccesstotheentiresetofrecords.Better:ModifiedMerge-sortalgorithm.ProcessnelementsinQ(logn)passes.Agroupofsortedrecordsiscalledarun顺串.1/4/202324优秀课件，精彩无限！SimpleExternalMergesort(1)QSimpleExternalMergesort(2)Splitthefileintotwofiles.Readinablockfromeachfile.Takefirstrecordfromeachblock,outputtheminsortedorder.Takenextrecordfromeachblock,outputthemtoasecondfileinsortedorder.Repeatuntilfinished,alternatingbetweenoutputfiles.Readnewinputblocksasneeded.Repeatsteps2-5,exceptthistimeinputfileshaverunsoftwosortedrecordsthataremergedtogether.Eachpassthroughthefilesprovideslargerruns.1/4/202325优秀课件，精彩无限！SimpleExternalMergesort(2)SSimpleExternalMergesort(3)1/4/202326优秀课件，精彩无限！SimpleExternalMergesort(3)1ProblemswithSimpleMergesortIseachpassthroughinputandoutputfilessequential?Whathappensifallworkisdoneonasinglediskdrive?HowcanwereducethenumberofMerge-sortpasses?Ingeneral,externalsortingconsistsoftwophases:BreakthefilesintoinitialrunsMergetherunstogetherintoasinglerun.1/4/202327优秀课件，精彩无限！ProblemswithSimpleMergesortBreakingaFileintoRunsGeneralapproach:Readasmuchofthefileintomemoryaspossible.Performanin-memorysort.Outputthisgroupofrecordsasasinglerun.1/4/202328优秀课件，精彩无限！BreakingaFileintoRunsGenerReplacementSelection(1)Breakavailablememoryintoanarrayfortheheap,aninputbuffer,andanoutputbuffer.Fillthearrayfromdisk.Makeamin-heap.Sendthesmallestvalue(root)totheoutputbuffer.1/4/202329优秀课件，精彩无限！ReplacementSelection(1)BreakReplacementSelection(2)Ifthenextkeyinthefileisgreaterthanthelastvalueoutput,thenReplacetherootwiththiskeyelseReplacetherootwiththelastkeyinthearrayAddthenextrecordinthefiletoanewheap(actually,stickitattheendofthearray).1/4/202330优秀课件，精彩无限！ReplacementSelection(2)IfthRSExample1/4/202331优秀课件，精彩无限！RSExample12/19/202231优秀课件，精彩无ProblemswithSimpleMergeSimplemerge-sort:Placerunsintotwofiles.Mergethefirsttworunstooutputfile,thennexttworuns,etc.Repeatprocessuntilonlyonerunremains.Howmanypassesforrinitialruns?Istherebenefitfromsequentialreading?Isworkingmemorywellused?Needawaytoreducethenumberofpasses.1/4/202332优秀课件，精彩无限！ProblemswithSimpleMergeSimpMulti-wayMerge(1)Withreplacementselection,eachinitialrunisseveralblockslong.Assumeeachrunisplacedinseparatefile.Readthefirstblockfromeachfileintomemoryandperformanr-waymerge.Whenabufferbecomesempty,readablockfromtheappropriaterunfile.Eachrecordisreadonlyoncefromdiskduringthemergeprocess.1/4/202333优秀课件，精彩无限！Multi-wayMerge(1)WithreplacMulti-wayMerge(2)Inpractice,useonlyonefileandseektoappropriateblock.1/4/202334优秀课件，精彩无限！Multi-wayMerge(2)InpracticeLimitstoMulti-wayMerge(1)Assumeworkingmemoryisbblocksinsize.Howmanyrunscanbeprocessedatonetime?Therunsare2bblockslong(onaverage).Howbigafilecanbemergedinonepass?1/4/202335优秀课件，精彩无限！LimitstoMulti-wayMerge(1)ALimitstoMulti-wayMerge(2)Largerfileswillneedmorepasses--buttherunsizegrowsquickly!Inkmergepasses,weprocess2b(k+1)blocks.Example:0.5MBworkingmemory,4KBblocks,yield128blocksforworkingmemory.Averagerunsizeis1MB,so128MBcanbesortedinonepassonaverage.16GBintwomergepasses.1/4/202336优秀课件，精彩无限！LimitstoMulti-wayMerge(2)LGeneralPrinciplesAgoodexternalsortingalgorithmwillseektodothefollowing:Maketheinitialrunsaslongaspossible.Atallstages,overlap重叠、并行input,processingandoutputasmuchaspossible.Useasmuchworkingmemoryaspossible.Applyingmorememoryusuallyspeedsprocessing.Ifpossible,useadditionaldiskdrivesformoreoverlappingofprocessingwithI/O,andallowformoresequentialfileprocessing.1/4/202337优秀课件，精彩无限！GeneralPrinciplesAgoodexterExerciseP2888.2,8.3,8.81/4/202338优秀课件，精彩无限！ExerciseP28812/19/202238优秀课件，精Primaryvs.SecondaryStoragePrimarystorage:Mainmemory(RAM)SecondaryStorage:PeripheraldevicesDiskdrivesTapedrives1/4/202339优秀课件，精彩无限！Primaryvs.SecondaryStoragePComparisonsRAMisusuallyvolatile.RAMisabout1/4milliontimesfasterthandisk.MediumEarly1996Mid1997Early2000RAM$45.007.001.50Disk1Floppy0.500.360.25Tape0.030.010.0011/4/202340优秀课件，精彩无限！ComparisonsMediumEarly1996MiGoldenRuleofFileProcessingMinimizethenumberofdiskaccesses!1.Arrangeinformationsothatyougetwhatyouwantwithfewdiskaccesses.2.Arrangeinformationtominimizefuturediskaccesses.Anorganizationfordataondiskisoftencalledafilestructure(p261).Disk-basedspace/timetradeoff(p74):Compressinformationtosaveprocessingtimebyreducingdiskaccesses.1/4/202341优秀课件，精彩无限！GoldenRuleofFileProcessingDiskDrives1/4/202342优秀课件，精彩无限！DiskDrives12/19/20224优秀课件，精彩无SectorsAsectoristhebasicunitofI/O.Interleavingfactor:Physicaldistancebetweenlogicallyadjacentsectorsonatrack.1/4/202343优秀课件，精彩无限！Sectors12/19/20225优秀课件，精彩无限！TermsLocalityofReference:Whenrecordisreadfromdisk,nextrequestislikelytocomefromnearthesameplaceinthefile.Cluster:Smallestunitoffileallocation,usuallyseveralsectors.Extent:Agroupofphysicallycontiguousclusters.Internalfragmentation:Wastedspacewithinsectorifrecordsizedoesnotmatchsectorsize;wastedspacewithinclusteriffilesizeisnotamultipleofclustersize.1/4/202344优秀课件，精彩无限！TermsLocalityofReference:WhSeekTimeSeektime:TimeforI/Oheadtoreachdesiredtrack.LargelydeterminedbydistancebetweenI/Oheadanddesiredtrack.Track-to-tracktime:Minimumtimetomovefromonetracktoanadjacenttrack.AverageSeektime:Averagetimetoreachatrackforrandomaccess.1/4/202345优秀课件，精彩无限！SeekTimeSeektime:TimeforIOtherFactorsRotationalDelayorLatency:TimefordatatorotateunderI/Ohead.Onehalfofarotationonaverage.At7200rpm,thisis8.3/2=4.2ms.Transfertime:TimefordatatomoveundertheI/Ohead.At7200rpm:Numberofsectorsread/Numberofsectorspertrack*8.3ms.1/4/202346优秀课件，精彩无限！OtherFactorsRotationalDelayDiskSpecExample16.8GBdiskon10platters=1.68GB/platter13,085tracks/platter256sectors/track512bytes/sectorTrack-to-trackseektime:2.2msAverageseektime:9.5ms4KBclusters,32clusters/track.Interleavingfactorof3.5400RPM1/4/202347优秀课件，精彩无限！DiskSpecExample16.8GBdiskDiskAccessCostExample(1)Reada1MBfiledividedinto2048recordsof512bytes(1sector)each.Assumeallrecordsareon8contiguoustracks.Firsttrack:9.5+11.1/2+3x11.1=48.4msRemaining7tracks:2.2+11.1/2+3x11.1=41.1ms.Total:48.4+7*41.1=335.7ms1/4/202348优秀课件，精彩无限！DiskAccessCostExample(1)ReDiskAccessCostExample(2)Reada1MBfiledividedinto2048recordsof512bytes(1sector)each.Assumeallfileclustersarerandomlyspreadacrossthedisk.256clusters.Clusterreadtimeis(3x8)/256ofarotationforabout1ms.256(9.5+11.1/2+11.1x3x(8/256))isabout4119.2ms.1/4/202349优秀课件，精彩无限！DiskAccessCostExample(2)ReHowMuchtoRead?Readtimeforonetrack:9.5+11.1/2+3x11.1=48.4ms.Readtimeforonesector:9.5+11.1/2+(1/256)11.1=15.1ms.Readtimeforonebyte:9.5+11.1/2=15.05ms.Nearlyalldiskdrivesread/writeonesectorateveryI/Oaccess.Alsoreferredtoasapage.P288:8.2ifclustersarespreadrandomlyacrossthedisk?1/4/202350优秀课件，精彩无限！HowMuchtoRead?ReadtimeforBuffersTheinformationinasectorisstoredinabufferorcache.IfthenextI/Oaccessistothesamebuffer,thennoneedtogotodisk.Thereareusuallyoneormoreinputbuffersandoneormoreoutputbuffers.1/4/202351优秀课件，精彩无限！BuffersTheinformationinaseBufferPoolsAseriesofbuffersusedbyanapplicationtocachediskdataiscalledabufferpool.VirtualmemoryusesabufferpooltoimitategreaterRAMmemorybyactuallystoringinformationondiskand“swapping”betweendiskandRAM.1/4/202352优秀课件，精彩无限！BufferPoolsAseriesofbufferBufferPools1/4/202353优秀课件，精彩无限！BufferPools12/19/202215优秀课件，精OrganizingBufferPoolsWhichbuffershouldbereplacedwhennewdatamustberead?First-in,First-out:Usethefirstoneonthequeue.LeastFrequentlyUsed(LFU):Countbufferaccesses,reusetheleastused.LeastRecentlyused(LRU):Keepbuffersonalinkedlist.Whenbufferisaccessed,bringittofront.Reusetheoneatend.If391047353827comeinto3-bufferpool(emptyinitially)?1/4/202354优秀课件，精彩无限！OrganizingBufferPoolsWhichbBufferpoolADT(1)classBufferPool{//(1)MessagePassingpublic:virtualvoidinsert(void*space,intsz,intpos)=0;virtualvoidgetbytes(void*space,intsz,intpos)=0;};classBufferPool{//(2)BufferPassingpublic:virtualvoid*getblock(intblock)=0;virtualvoiddirtyblock(intblock)=0;virtualintblocksize()=0;};1/4/202355优秀课件，精彩无限！BufferpoolADT(1)classBufferDesignIssuesDisadvantageofmessagepassing:Messagesarecopiedandpassedbackandforth.

Disadvantagesofbufferpassing:Theuserisgivenaccesstosystemmemory(thebufferitself)Theusermustexplicitlytellthebufferpoolwhenbuffercontentshavebeenmodified,sothatmodifieddatacanberewrittentodiskwhenthebufferisflushed.Thepointermightbecomestalewhenthebufferpoolreplacesthecontentsofabuffer.1/4/202356优秀课件，精彩无限！DesignIssuesDisadvantageofmProgrammer’sViewofFilesLogicalviewoffiles:Anarrayofbytes.Afilepointermarksthecurrentposition.Threefundamentaloperations:Readbytesfromcurrentposition(movefilepointer)Writebytestocurrentposition(movefilepointer)Setfilepointertospecifiedbyteposition.1/4/202357优秀课件，精彩无限！Programmer’sViewofFilesLogiC++FileFunctions#include<fstream.h>voidfstream::open(char*name,openmodemode);Example:ios::in|ios::binaryvoidfstream::close();fstream::read(char*ptr,intnumbytes);fstream::write(char*ptr,intnumbtyes);fstream::seekg(intpos);fstream::seekg(intpos,ios::curr);fstream::seekp(intpos);fstream::seekp(intpos,ios::end);1/4/202358优秀课件，精彩无限！C++FileFunctions#include<fsExternalSortingProblem:Sortingdatasetstoolargetofitintomainmemory.Assumedataarestoredondiskdrive.Tosort,portionsofthedatamustbebroughtintomainmemory,processed,andreturnedtodisk.Anexternalsortshouldminimizediskaccesses.1/4/202359优秀课件，精彩无限！ExternalSortingProblem:SortiModelofExternalComputationSecondarymemoryisdividedintoequal-sizedblocks(512,1024,etc…)AbasicI/Ooperationtransfersthecontentsofonediskblockto/frommainmemory.Undercertaincircumstances,readingblocksofafileinsequentialorderismoreefficient.(When?)PrimarygoalistominimizeI/Ooperations.Assumeonlyonediskdriveisavailable.1/4/202360优秀课件，精彩无限！ModelofExternalComputationSKeySortingOften,recordsarelarge,keysaresmall.Ex:PayrollentrieskeyedonIDnumberApproach1:Readinentirerecords,sortthem,thenwritethemoutagain.Approach2:Readonlythekeyvalues,storewitheachkeythelocationondiskofitsassociatedrecord.Afterkeysaresortedtherecordscanbereadandrewritteninsortedorder.1/4/202361优秀课件，精彩无限！KeySortingOften,recordsareSimpleExternalMergesort(1)Quicksortrequiresrandomaccesstotheentiresetofrecords.Better:ModifiedMerge-sortalgorithm.ProcessnelementsinQ(logn)passes.Agroupofsortedrecordsiscalledarun顺串.1/4/202362优秀课件，精彩无限！SimpleExternalMergesort(1)QSimpleExternalMergesort(2)Splitthefileintotwofiles.Readinablockfromeachfile.Takefirstrecordfromeachblock,outputtheminsortedorder.Takenextrecordfromeachblock,outputthemtoasecondfileinsortedorder.Repeatuntilfinished,alternatingbetweenoutputfiles.Readnewinputblocksasneeded.Repeatsteps2-5,exceptthistimeinputfileshaverunsoftwosortedrecordsthataremergedtogether.Eachpassthroughthefilesprovideslargerruns.1/4/202363优秀课件，精彩无限！SimpleExternalMergesort(2)SSimpleExternalMergesort(3)1/4/202364优秀课件，精彩无限！SimpleExternalMergesort(3)1ProblemswithSimpleMergesortIseachpassthroughinputandoutputfilessequential?Whathappensifallworkisdoneonasinglediskdrive?HowcanwereducethenumberofMerge-sortpasses?Ingeneral,externalsortingconsistsoftwophases:BreakthefilesintoinitialrunsMergetherunstogetherintoasinglerun.1/4/202365优秀课件，精彩无限！ProblemswithSimpleMergesortBreakingaFileintoRunsGeneralapproach:Readasmuchofthefileintomemoryaspossible.Performanin-memorysort.Outputthisgroupofrecordsasasinglerun.1/4/202366优秀课件，精彩无限！BreakingaFileintoRunsGenerReplacementSelection(1)Breakavailablememoryintoanarrayfortheheap,aninputbuffer,andanoutputbuffer.Fillthearrayfromdisk.Makeamin-heap.Sendthesmallestvalue(root)totheoutputbuffer.1/4/202367优秀课件，精彩无限！ReplacementSelection(1)BreakReplacementSelection(2)Ifthenextkeyinthefileisgreaterthanthelastvalueoutput,thenReplacetherootwiththiskeyelseReplace