关闭

关闭

关闭

封号提示

内容

首页 英文第二版-Programming.Pearls

英文第二版-Programming.Pearls.pdf

英文第二版-Programming.Pearls

zgq110486 2010-12-18 评分 0 浏览量 0 0 0 0 暂无简介 简介 举报

简介:本文档为《英文第二版-Programming.Pearlspdf》,可适用于IT/计算机领域,主题内容包含ProgrammingPearls,SecondEditionbyJonBentleyAddisonWesley,Inc,ISBNxipp$This符等。

ProgrammingPearls,SecondEditionbyJonBentleyAddisonWesley,Inc,ISBNxipp$Thisbookisacollectionofessaysaboutaglamorousaspectofsoftware:programmingpearlswhoseoriginsliebeyondsolidengineering,intherealmofinsightandcreativityThisbookprovidesaguideforbothstudentsandexperiencedprogrammersabouthowtodesignandcreateprograms,andhowtothinkaboutprogrammingThebookisfullofsmallcasestudies,realexamples,andinterestingexercisesforlearningabouthowtoprogramThiswebpagecontainssamplesfromthewholeworkforyoutoinvestigateForteachers,thelinksbelowleadtosomeofthecentralmaterialsuitableforclassroomuseSteveMcConnelldescribesthebookas``acelebrationofdesigninthesmall''BrowsethissitetosampleityourselfWhat'snewonthiswebsiteFromTheBookTableofContentsPrefacePartI:PreliminariesColumn:CrackingtheOysterColumn:Aha!AlgorithmsSketchColumn:WritingCorrectProgramsSketchColumn:ASmallMatterofProgrammingSketchPartII:PerformanceColumn:TheBackoftheEnvelopeColumn:AlgorithmDesignTechniquesSketchPartIII:TheProductColumn:HeapsSketchColumn:StringsofPearlsEpilogtotheFirstEditionEpilogtotheSecondEditionAppendix:AnEstimationQuizAppendix:CostModelsforTimeandSpaceAppendix:RulesforCodeTuningSolutionsforColumnColumnColumnColumnIndexAboutTheBookWhyaSecondEditionToReadersoftheFirstEditionAbouttheFirstEditionErrataSupportingMaterialSourceCodeWebSitesRelevanttotheBookAnimationofSortingAlgorithmsTricksoftheTradeTeachingMaterialOtherLinkslAddisonWesleyComputerEngineeringPublishingGrouplProgrammingPearlsatAddisonWesleylBookstores:Amazoncom,BarnesNoble,Borderscom,Fatbraincom,QuantumBooksCopyrightLucentTechnologiesAllrightsreservedThuOctWhat'sNewontheProgrammingPearlsWebSiteNovemberColumnisnowonthesite,completewithanewprogramforletterlevelMarkovtext,andnewexamplesofwordfrequencies,longrepeatedstrings,andletterlevelandwordlevelMarkovtextOctoberTherulesforcodetuningfrommybookWritingEfficientProgramsarenowonline,andsoisaPowerpointShowonCacheConsciousAlgorithmsandDataStructuresAugustTheerratajustkeepsongrowingIfyouseeerrors,pleasesendtheminJulyProgrammingPearlsisoftenusedforteachingundergraduatesThispagedescribeshowsomeofthetopicsinthebookcanbeincorporatedintocollegeclassroomsMarchAthemerunningthroughthebookconcernstheTricksoftheTradeThispagedescribesthattopicandcontainsaPowerpointShowonthesubjectCopyrightLucentTechnologiesAllrightsreservedMonNovStringsofPearls(ColumnofProgrammingPearls)WearesurroundedbystringsStringsofbitsmakeintegersandfloatingpointnumbersStringsofdigitsmaketelephonenumbers,andstringsofcharactersmakewordsLongstringsofcharactersmakewebpages,andlongerstringsyetmakebooksExtremelylongstringsrepresentedbythelettersA,C,GandTareingeneticists'databasesanddeepinsidethecellsofmanyreadersofthisbookProgramsperformadazzlingvarietyofoperationsonsuchstringsTheysortthem,countthem,searchthem,andanalyzethemtodiscernpatternsThiscolumnintroducesthosetopicsbyexaminingafewclassicproblemsonstringsTheRestoftheColumnThesearetheremainingsectionsinthecolumnWordsPhrasesGeneratingTextPrinciplesProblemsFurtherReadingRelatedContentTheteachingmaterialcontainsoverheadtransparenciesbasedonSectionsandtheslidesareavailableinbothPostscriptandAcrobatThecodeforColumncontainsimplementationsofthealgorithmsTheSolutionstoColumngiveanswersforsomeoftheProblemsThiscolumnconcentratesonprogrammingtechniques,andusesthosetechniquestobuildseveralprogramsforprocessinglargetextfilesAfewexamplesoftheprograms'outputinthetextillustratethestructureofEnglishdocumentsThiswebsitecontainssomeadditionalfunexamples,whichmaygivefurtherinsightintothestructureoftheEnglishlanguageSectioncountsthewordsinonedocumentherearemoreexamplesofwordfrequencycountsSectionsearchesforlargeportionsofduplicatedtextherearemoreexamplesoflongrepeatedstringsSectiondescribesrandomlygeneratedMarkovtextthesepagescontainaddtionalexamplesofMarkovtext,generatedattheletterlevelandwordlevelThewebreferencesdescribeseveralwebsitesdevotedtorelatedtopicsCopyrightLucentTechnologiesAllrightsreservedWedOctWords(SectionofProgrammingPearls)Ourfirstproblemistoproducealistofthewordscontainedinadocument(Feedsuchaprogramafewhundredbooks,andyouhaveafinestartatawordlistforadictionary)ButwhatexactlyisawordWe'llusethetrivialdefinitionofasequenceofcharacterssurroundedbywhitespace,butthismeansthatwebpageswillcontainmany``words''like``<html>'',``<body>''and``''ProblemaskshowyoumightavoidsuchproblemsOurfirstCprogramusesthesetsandstringsoftheStandardTemplateLibrary,inaslightmodificationoftheprograminSolution:intmain(void){setSset::iteratorjstringtwhile(cin>>t)Sinsert(t)for(j=Sbegin()j!=Send()j)cout<<*j<<"n"return}ThewhileloopreadstheinputandinsertseachwordintothesetS(bytheSTLspecification,duplicatesareignored)Theforlooptheniteratesthroughtheset,andwritesthewordsinsortedorderThisprogramiselegantandfairlyefficient(moreonthattopicsoon)OurnextproblemistocountthenumberoftimeseachwordoccursinthedocumentHerearethemostcommonwordsintheKingJamesBible,sortedindecreasingnumericorderandalignedinthreecolumnstosavespace:theshalltheyandhebeofuntoistoIwithAndhisnotthataallinforthouAlmosteightpercentofthe,wordsinthetextweretheword``the''(asopposedtopercentofthewordsinthissentence)Byourdefinitionofword,``and''and``And''havetwoseparatecountsClickformoreexamplesofwordfrequencycountsThesecountswereproducedbythefollowingCprogram,whichusestheStandardTemplateLibrarymaptoassociateanintegercountwitheachstring:intmain(void){mapMmap::iteratorjstringtwhile(cin>>t)Mtfor(j=Mbegin()j!=Mend()j)cout<<j>first<<""<<j>second<<"n"return}ThewhilestatementinsertseachwordtintothemapMandincrementstheassociatedcounter(whichisinitializedtozeroatinitialization)Theforstatementiteratesthroughthewordsinsortedorderandprintseachword(first)anditscount(second)ThisCcodeisstraightforward,succinctandsurprisinglyfastOnmymachine,ittakessecondstoprocesstheBibleAboutsecondsgotoreading,secondstotheinsertions,andsecondstowritingtheouputWecanreducetheprocessingtimebybuildingourownhashtable,usingnodesthatcontainapointertoaword,acountofhowoftenthewordhasbeenseen,andapointertothenextnodeinthetableHereisthehashtableafterinsertingthestrings``in'',``the''and``in'',intheunlikelyeventthatbothstringshashto:We'llimplementthehashtablewiththisCstructure:typedefstructnode*nodeptrtypedefstructnode{char*wordintcountnodeptrnext}nodeEvenbyourloosedefinitionof``word'',theBiblehasonly,distinctwordsWe'llfollowtheoldloreofusingaprimenumbernearthatforourhashtablesize,andthepopularmultiplierof:#defineNHASH#defineMULTnodeptrbinNHASHOurhashfunctionmapsastringtoapositiveintegerlessthanNHASH:unsignedinthash(char*p)unsignedinth=for(*pp)h=MULT*h*preturnhNHASHUsingunsignedintegersensuresthathremainspositiveThemainfunctioninitializeseverybinto,readsthewordandincrementsthecountofeach,theniteratesthroughthehashtabletowritethe(unsorted)wordsandcounts:intmain(void)fori=,NHASH)bini=whilescanf("s",buf)!=EOFincword(buf)fori=,NHASH)for(p=binip!=p=p>next)printp>word,p>countreturnTheworkisdonebyincword,whichincrementsthecountassociatedwiththeinputword(andinitializesitifitisnotalreadythere):voidincword(char*s)h=hash(s)for(p=binhp!=p=p>next)ifstrcmp(s,p>word)==(p>count)returnp=malloc(sizeof(hashnode))p>count=p>word=malloc(strlen(s))strcpy(p>word,s)p>next=binhbinh=pTheforlooplooksateverynodewiththesamehashvalueIfthewordisfound,itscountisincrementedandthefunctionreturnsIfthewordisnotfound,thefunctionmakesanewnode,allocatesspaceandcopiesthestring(experiencedCprogrammerswouldusestrdupforthetask),andinsertsthenodeatthefrontofthelistThisCprogramtakesaboutsecondstoreaditsinput(thesameastheCversion),butonlysecondsfortheinsertions(downfrom)andonlysecondstowritetheoutput(downfrom)Thecompleteruntimeisseconds(downfrom),andtheprocessingtimeisseconds(downfrom)Ourcustommadehashtable(inlinesofC)isanorderofmagnitudefasterthanthemapsfromtheCStandardTemplateLibraryThislittleexerciseillustratesthetwomainwaystorepresentsetsofwordsBalancedsearchtreesoperateonstringsasindivisibleobjectsthesestructuresareusedinmostimplementationsoftheSTL'ssetsandmapsTheyalwayskeeptheelementsinsortedorder,sotheycanefficientlyperformoperationssuchasfindingapredecessororreportingtheelementsinorderHashing,ontheotherhand,peeksinsidethecharacterstocomputeahashfunction,andthenscatterskeysacrossabigtableItisveryfastontheaverage,butitdoesnotoffertheworstcaseperformanceguaranteesofbalancedtrees,orsupportotheroperationsinvolvingorderNext:SectionPhrasesCopyrightLucentTechnologiesAllrightsreservedWedOctProblems(SectionofProgrammingPearls)TheSolutionstoColumngiveanswersforsomeoftheseproblemsThroughoutthiscolumnwehaveusedthesimpledefinitionthatwordsareseparatedbywhitespaceManyrealdocuments,suchasthoseinHTMLorRTF,containformattingcommandsHowcouldyoudealwithsuchcommandsArethereanyothertasksthatyoumightneedtoperformOnamachinewithamplemainmemory,howcouldyouusetheCSTLsetsormapstosolvethesearchingprobleminSectionHowmuchmemorydoesitconsumecomparedtoMcIlroy'sstructureHowmuchspeedupcanyouachievebyincorporatingthespecialpurposemallocofSolutionintothehashingprogramofSectionWhenahashtableislargeandthehashfunctionscattersthedatawell,almosteverylistinthetablehasonlyafewelementsIfeitheroftheseconditionsisviolated,though,thetimespentsearchingdownthelistcanbesubstantialWhenanewstringisnotfoundinthehashtableinSection,itisplacedatthefrontofthelistTosimulatehashingtrouble,setNHASHtoandexperimentwiththisandotherliststrategies,suchasappendingtotheendofthelist,ormovingthemostrecentlyfoundelementtothefrontofthelistWhenwelookedattheoutputofthewordfrequencyprogramsinSection,itwasmostinterestingtoprintthewordsindecreasingfrequencyHowwouldyoumodifytheCandCprogramstoaccomplishthistaskHowwouldyouprintonlytheMmostcommonwords,whereMisaconstantsuchasorGivenanewinputstring,howwouldyousearchasuffixarraytofindthelongestmatchinthestoredtextHowwouldyoubuildaGUIinterfaceforthistaskOurprogramforfindingduplicatedstringswasveryfastfor``typical''inputs,butitcanbeveryslow(greaterthanquadratic)forsomeinputsTimetheprogramonsuchaninputDosuchinputseverariseinpracticeHowwouldyoumodifytheprogramforfindingduplicatedstringstofindthelongeststringthatoccursmorethanMtimesGiventwoinputtexts,findthelongeststringthatoccursinbothShowhowtoreducethenumberofpointersintheduplicationprogrambypointingonlytosuffixesthatstartonwordboundariesWhateffectdoesthishaveontheoutputproducedbytheprogramImplementaprogramtogenerateletterlevelMarkovtextHowwouldyouusethetoolsandtechniquesofSectiontogenerate(orderornonMarkov)randomtextTheprogramforgeneratingwordlevelMarkovtextisatthisbook'swebsiteTryitonsomeofyourdocumentsHowcouldyouusehashingtospeeduptheMarkovprogramShannon'squoteinSectiondescribesthealgorithmheusedtoconstructMarkovtextimplementthatalgorithminaprogramItgivesagoodapproximationtotheMarkovfrequencies,butnottheexactformexplainwhynotImplementaprogramthatscanstheentirestringfromscratchtogenerateeachword(andtherebyusesthetruefrequencies)Howwouldyouusethetechniquesofthiscolumntoassembleawordlistforadictionary(theproblemthatDougMcIlroyfacedinSection)HowwouldyoubuildaspellingcheckerwithoutusingadictionaryHowwouldyoubuildagrammarcheckerwithoutusingrulesofgrammarInvestigatehowtechniquesrelatedtokgramanalysisareusedinapplicationssuchasspeechrecognitionanddatacompressionNext:SectionFurtherReadingCopyrightLucentTechnologiesAllrightsreservedWedOctSolutions(ToColumnofProgrammingPearls)ThisCprogramusestheStandardLibraryqsorttosortafileofintegersintintcomp(int*x,int*y){return*x*y}intaintmain(void){inti,n=while(scanf("d",an)!=EOF)nqsort(a,n,sizeof(int),intcomp)for(i=i<ni)printf("dn",ai)return}ThisCprogramusesthesetcontainerfromtheStandardTemplateLibraryforthesamejobintmain(void){setSintiset::iteratorjwhile(cin>>i)Sinsert(i)for(j=Sbegin()j!=Send()j)cout<<*j<<"n"return}SolutionsketchestheperformanceofbothprogramsThesefunctionsusetheconstantstoset,clearandtestthevalueofabit:#defineBITSPERWORD#defineSHIFT#defineMASKxF#defineNintaNBITSPERWORDvoidset(inti){ai>>SHIFT|=(<<(iMASK))}voidclr(inti){ai>>SHIFT=~(<<(iMASK))}inttest(inti){returnai>>SHIFT(<<(iMASK))}ThisCcodeimplementsthesortingalgorithm,usingthefunctionsdefinedinSolutionintmain(void){intifor(i=i<Ni)clr(i)while(scanf("d",i)!=EOF)set(i)for(i=i<Ni)if(test(i))printf("dn",i)return}IusedtheprograminSolutiontogenerateafileofonemilliondistinctpositiveintegers,eachlessthantenmillionThistablereportsthecostofsortingthemwiththesystemcommandlinesort,theCandCprogramsinSolution,andthebitmapcode:SystemSortCSTLCqsortCbitmapsTotalSecsComputeSecsMegabytesThefirstlinereportsthetotaltime,andthesecondlinesubtractsoutthesecondsofinputoutputrequiredtoreadandwritethefilesEventhoughthegeneralCprogramusestimesthememoryandCPUtimeofthespecializedCprogram,itrequiresjusthalfthecodeandismucheasiertoextendtootherproblemsSeeColumn,especiallyProblemThiscodeassumesthatrandint(l,u)returnsarandomintegerinlufori=,n)xi=ifori=,k)swap(i,randint(i,n))printxiTheswapfunctionexchangesthetwoelementsinxTherandintfunctionisdiscussedindetailinSectionRepresentingalltenmillionnumberswithabitmaprequiresthatmanybits,ormillionbytesEmployingthefactthatnophonenumbersbeginwiththedigitszerooronereducesthememorytoexactlyonemillionbytesAlternatively,atwopassalgorithmfirstsortstheintegersthrough,,using,,=,wordsofstorage,thensorts,,through,,inasecondpassAkpassalgorithmsortsatmostnnonrepeatedpositiveintegerslessthannintimeknandspacenkIfeachintegerappearsatmosttentimes,thenwecancountitsoccurrencesinafourbithalfbyte(ornybble)UsingthesolutiontoProblem,wecansortthecompletefileinasinglepasswith,,bytes,orinkpasseswith,,kbytesTheeffectofinitializingthevectordatancanbeaccomplishedwithasignaturecontainedintwoadditionalnelementvectors,fromandto,andanintegertopIftheelementdataihasbeeninitialized,thenfromi<topandtofromi=iThusfromisasimplesignature,andtoandtoptogethermakesurethatfromisnotaccidentallysignedbytherandomcontentsofmemoryBlankentriesofdataareuninitializedinthispicture:Thevariabletopisinitiallyzerothearrayelementiisfirstaccessedbythecodefromi=toptotop=idatai=topThisproblemandsolutionarefromExerciseofAho,HopcroftandUllman'sDesignandAnalysisofComputerAlgorithms,publishedbyAddisonWesleyinItcombineskeyindexingandawilysignatureschemeItcanbeusedformatricesaswellasvectorsThestoreplacedthepaperorderformsinaxarrayofbins,usingthelasttwodigitsofthecustomer'sphonenumberasthehashindexWhenthecustomertelephonedanorder,itwasplacedintheproperbinWhenthecustomerarrivedtoretrievethemerchandise,thesalespersonsequentiallysearchedthroughtheordersintheappropriatebinthisisclassical``openhashingwithcollisionresolutionbysequentialsearch''Thelasttwodigitsofthephonenumberarequiteclosetorandomandthereforeanexcellenthashfunction,whilethefirsttwodigitswouldbeahorriblehashfunctionwhySomemunicipalitiesuseasimilarschemetorecorddeedsinsetsofrecordbooksThecomputersatthetwofacilitieswerelinkedbymicrowave,butprintingthedrawingsatthetestbasewouldhaverequireda

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +1积分

资料评分:

/49
仅支持在线阅读

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料