查找技術(shù)的前世今生

查找技術(shù)的前世今生送大家兩句格言：一個(gè)人如果把從別人那里學(xué)來的東西算作自己的發(fā)現(xiàn)，這也很接近于虛驕。--黑格爾一個(gè)永遠(yuǎn)也不欣賞別人工作的人，也就是一個(gè)永遠(yuǎn)也不被別人欣賞的人。--汪國真講課原則1.原理上把握，貫徹?cái)?shù)學(xué)分析

“歷史上所有偉大的思想家都在尋找一個(gè)真理，一個(gè)他人無法辯駁的真理，就像2+2=4，為了尋找這樣的真理，要實(shí)現(xiàn)這樣一個(gè)既定目標(biāo)，還有什么比這個(gè)永恒而不變且不受人類情感所左右的方式更合適呢？世上除數(shù)學(xué)之外，根本不存在所謂真理，可以解答人類全部疑惑的無懈可擊的絕對(duì)真理—讓人無法反駁的論據(jù)”。

所以對(duì)于“那些數(shù)學(xué)上不可言說的，我們必須保持緘默”。 --《邏輯哲學(xué)論》第七節(jié)作者：維特根斯坦2.主流查找技術(shù),講基礎(chǔ)“墻高基下，雖得必失”--南朝宋史學(xué)家范曄算法分析的性能指標(biāo)1.時(shí)間復(fù)雜度比如：遍歷一個(gè)數(shù)組的時(shí)間復(fù)雜度是O(n)2.空間復(fù)雜度內(nèi)存耗費(fèi)的數(shù)量級(jí)查找查找技術(shù)與存儲(chǔ)（查和存）查找技術(shù)與排序都有著深刻的關(guān)系講解內(nèi)容：順序查找法折半查找法hash表法排序二叉樹平衡二叉樹堆(heap)B-樹B+樹1.順序查找法--任何程序員都會(huì)偽代碼：functionlinear_search(array,key){for(inti=0;i<array.length;i++){ if(array[i]==key){ returni; }}return-1;}科學(xué)性能指標(biāo):平均查找長(zhǎng)度ASL（AverageSearchLength)(n+1)/2折半查找法(binarysearch)1.需要先排序快速排序（可能退化為冒泡排序法），堆排序等，時(shí)間復(fù)雜度為n*log(n)2.進(jìn)行折半查找intbinary_search(intarray[],intlow,inthigh,inttarget){while(low<=high){intmid=(low+high)/2;if(array[mid]>target)high=mid-1;elseif(array[mid]<target)low=mid+1;else//findthetargetreturnmid;}//thearraydoesnotcontainthetargetreturn-1;}3.動(dòng)畫/~andrzej/java/BS-applet.html二分查找法的平均查找長(zhǎng)度當(dāng)n->無窮大的時(shí)候,極限的洛必達(dá)法則ASL=log(n+1)-1Hash表法演示動(dòng)畫:http://www.cse.yorku.ca/~aaw/Hang/hash/Hash.html把一大堆元素映射到一段有限的存儲(chǔ)空間上。核心思想:1.存放到第幾個(gè)格子來自于key本身的信息,value只不過是個(gè)附加物2.search和insert都需要經(jīng)過關(guān)鍵的hash函數(shù)3.如果不沖突時(shí)候，時(shí)間復(fù)雜度為O(1)4.處理沖突2種方法，鏈表法，開放線性探測(cè)法注意幾點(diǎn):正式的編程語言里(java,python)等，使用的是transfer法Hash表法問題：1.搬移的次數(shù)雖然不多，但也是會(huì)發(fā)生的。2.海量大數(shù)據(jù)下，比如2T數(shù)據(jù)，最壞情況下會(huì)退化為順序查找法。排序二叉樹(BinarySearchTree)BST1.概念二叉查找樹（BinarySearchTree），或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；它的左、右子樹也分別為二叉排序樹。2.動(dòng)畫/~egolub/Java/BinaryTree.html3.問題如果插入的序列為隨機(jī)插入，則最壞情況下查找的時(shí)間復(fù)雜度為logn如果插入的序列為有序(無論正序還是逆序),則最壞情況下查找的時(shí)間復(fù)雜度為n,會(huì)退化為順序查找排序二叉樹的插入和刪除1.插入(insert函數(shù))分別沿路徑插入到左子樹或右子樹中2.刪除(delete/remove函數(shù))(1)若為葉子，直接刪除(2)若只有左子樹或只有右子樹，則令其孩子代替原位置(3)若左右子樹均不為空，則用直接后繼(或前驅(qū))代替其現(xiàn)有位置，再將直接后繼(或前驅(qū))刪掉。改進(jìn)與優(yōu)化平衡二叉樹（AVLtree）平衡因子(BalanceFactor)概念的引入：四種可能性，平衡旋轉(zhuǎn)技術(shù)手段：LLRRRLLR平衡旋轉(zhuǎn)技術(shù)(LL)平衡旋轉(zhuǎn)技術(shù)(RR)平衡旋轉(zhuǎn)技術(shù)(LR)平衡旋轉(zhuǎn)技術(shù)(RL)最后，演示動(dòng)畫http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html堆(heap)1.排序2.優(yōu)先級(jí)隊(duì)列尋路算法等用到堆的兩大性質(zhì)1.堆是一棵完全二叉樹(completebinarytree),即除了最后葉子一層的元素之外的其他層的元素包含盡可能多的元素。在最后葉子一層，所有的元素都盡可能在左邊的位置。2.堆的每個(gè)元素都大于等于孩子節(jié)點(diǎn)的元素。（大根堆）可以存儲(chǔ)在數(shù)組中堆的數(shù)組表示完全二叉樹可以用一個(gè)數(shù)組(array)表示:根節(jié)點(diǎn)root是array[0]非根節(jié)點(diǎn)array[i]的parent節(jié)點(diǎn)位于array[(i-1)/2]，使用integerdivision(整數(shù)除法)非根節(jié)點(diǎn)array[i]的左child節(jié)點(diǎn)位于array[2i+1],右child節(jié)點(diǎn)位于array[2i+2]。這個(gè)關(guān)于孩子index=2i+1或2i+2的性質(zhì)可以由等比數(shù)列求和推導(dǎo)得到堆的插入和刪除1.插入(insert)risingprocess的過程叫做reheapificationupward.2.刪除(remove/delete)removemethod刪除一個(gè)堆的元素時(shí)，我們必須刪除最大priority值的元素（優(yōu)先級(jí)隊(duì)列priorityqueue也可以由堆來實(shí)現(xiàn)，因?yàn)閮?yōu)先級(jí)隊(duì)列每次拿出的是最大優(yōu)先級(jí)的元素）。如果一個(gè)堆只有一個(gè)root根元素，則直接刪除掉即可，然后減少heap的size；如果一個(gè)堆包含多于一個(gè)元素的時(shí)候，必須調(diào)整堆的結(jié)構(gòu)使其滿足堆性質(zhì)。這樣做：1.將根節(jié)點(diǎn)的引用copy出來。(為了這個(gè)method最后的return）2.先將葉子節(jié)點(diǎn)move至根節(jié)點(diǎn)，這樣原來那個(gè)位置上的葉子節(jié)點(diǎn)就被拿出來了（次被稱作out-of-placeelement）3.while（這個(gè)被move的out-of-placeelement節(jié)點(diǎn)小于他的孩子節(jié)點(diǎn)(child)){就將其最大的那個(gè)孩子與out-of-placeelement節(jié)點(diǎn)的位置交換。}4.returnstep1的answer源代碼intDeleteMin(){/*heap[1]istheminimumelement.Soweremoveheap[1].Sizeoftheheapisdecreased.Nowheap[1]hastobefilled.Weputthelastelementinitsplaceandseeifitfits.Ifitdoesnotfit,takeminimumelementamongbothitschildrenandreplacesparentwithit.AgainSeeifthelastelementfitsinthatplace.*//**核心思想：把堆頂?shù)膭h除，然后把完全二叉樹的最后小弟(lastElement)放到合適的位置，這里不是每次向較大的孩子交換swap的辦法向下沉淀的，而是先讓比lastElement小的元素都挪上去，騰出位置后，lastElement直接放入到那個(gè)被騰出來的合適位置。因?yàn)榇蟮脑匾鲁粒詻]有必要每次交換2個(gè)元素（交換會(huì)費(fèi)時(shí)間），只需要讓這個(gè)lastElement元素與大孩子比較，如果lastElement，直接把當(dāng)前的now賦值為他的孩子即可，而且因?yàn)榘讯秧攧h掉了，所以堆頂?shù)膎ow的信息丟掉而賦值他的孩子信息給他也沒什么問題。**/intminElement,lastElement,child,now;minElement=heap[1];lastElement=heap[heapSize--];//heapSize先賦值再--，這句非常精妙，表明了最后的元素不在被當(dāng)做堆中的元素了，雖然數(shù)組中仍然存在

源代碼(2)，接上頁/*nowreferstotheindexatwhichwearenow*/for(now=1;now*2<=heapSize;now=child)//注意這里的for循環(huán)每次循環(huán)體執(zhí)行結(jié)束后，是先執(zhí)行最后一個(gè)分號(hào)后的now=child,再判斷for中間的那句--是否退出循環(huán)的條件的，所以如果一般而言now最后會(huì)在循環(huán)結(jié)束后賦值為child，但是注意這里使用了break.因此直接會(huì)退出循環(huán)，而不執(zhí)行now=child{/*childistheindexoftheelementwhichisminimumamongboththechildren*//*Indexesofchildrenarei*2andi*2+1*/child=now*2;/*child!=heapSizebeacuseheap[heapSize+1]doesnotexist,whichmeansithasonlyonechild*/if(child!=heapSize&&heap[child+1]<heap[child]){child++;}/*Tocheckifthelastelementfitsotnotitsufficestocheckifthelastelementislessthantheminimumelementamongboththechildren*/if(lastElement>heap[child]){heap[now]=heap[child];}else/*Itfitsthere*/{break;//直接break出循環(huán)，now現(xiàn)在指向的就是把所有的大于lastElement挪上去后的騰出來的合適位置}}heap[now]=lastElement;returnminElement;}數(shù)學(xué)分析1.一個(gè)堆的高度為[logn]+12.推導(dǎo)堆排序

85

26

74

58

63

91

12

32

26

85

85

26

63

91

63

91

12

85

12

85

26

12

12

26

32

91

32

91

63

32

32

63

12

91

12

85

85

12

12

74

74

12

85

32

74

32

32

74

74

58

58

63

63

58

63

12

58

12

12

58

58

26

32

26

26

32

32

12

12

26

26

12

26

12動(dòng)畫演示:/~jarc/idsv/lesson3.html2.百度經(jīng)典面試題問題.有海量的服務(wù)器的IP訪問日志，如何在內(nèi)存及其有限的機(jī)器(幾k的內(nèi)存，比如嵌入式設(shè)備等)上，從中找出訪問最頻繁的幾個(gè)IP？解法：時(shí)間換空間importheapqli=[random.randint(0,i)foriinxrange(1000)]#top10,還有個(gè)參數(shù)指定key，可以這樣寫key=lambdaentry:entry["count"]，在對(duì)list里每一項(xiàng)都是字典類型時(shí)的使用heapq.nlargest(10,li)sorted(li,reverse=True)[:10]B-樹講解前的準(zhǔn)備（硬盤的結(jié)構(gòu)和原理）硬盤的結(jié)構(gòu)(2)硬盤的磁頭越來越接近于磁道磁頭的結(jié)構(gòu)磁盤整體結(jié)構(gòu)示意圖B-樹AB-treeofordermisanm-waytree(i.e.,atreewhereeachnodemayhaveuptomchildren)inwhich:1. thenumberofkeysineachnon-leafnodeisonelessthanthenumberofitschildrenandthesekeyspartitionthekeysinthechildreninthefashionofasearchtree（見縫插針）2. allleavesareonthesamelevel（葉子同級(jí)）3. allnon-leafnodesexcepttherootha