查找技术的前世今生

查找技术的前世今生送大家两句格言：一个人如果把从别人那里学来的东西算作自己的发现，这也很接近于虚骄。--黑格尔一个永远也不欣赏别人工作的人，也就是一个永远也不被别人欣赏的人。--汪国真讲课原则1.原理上把握，贯彻数学分析

“历史上所有伟大的思想家都在寻找一个真理，一个他人无法辩驳的真理，就像2+2=4，为了寻找这样的真理，要实现这样一个既定目标，还有什么比这个永恒而不变且不受人类情感所左右的方式更合适呢？世上除数学之外，根本不存在所谓真理，可以解答人类全部疑惑的无懈可击的绝对真理—让人无法反驳的论据”。

所以对于“那些数学上不可言说的，我们必须保持缄默”。 --《逻辑哲学论》第七节作者：维特根斯坦2.主流查找技术,讲基础“墙高基下，虽得必失”--南朝宋史学家范晔算法分析的性能指标1.时间复杂度比如：遍历一个数组的时间复杂度是O(n)2.空间复杂度内存耗费的数量级查找查找技术与存储（查和存）查找技术与排序都有着深刻的关系讲解内容：顺序查找法折半查找法hash表法排序二叉树平衡二叉树堆(heap)B-树B+树1.顺序查找法--任何程序员都会伪代码：functionlinear_search(array,key){for(inti=0;i<array.length;i++){ if(array[i]==key){ returni; }}return-1;}科学性能指标:平均查找长度ASL（AverageSearchLength)(n+1)/2折半查找法(binarysearch)1.需要先排序快速排序（可能退化为冒泡排序法），堆排序等，时间复杂度为n*log(n)2.进行折半查找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.动画/~andrzej/java/BS-applet.html二分查找法的平均查找长度当n->无穷大的时候,极限的洛必达法则ASL=log(n+1)-1Hash表法演示动画:http://www.cse.yorku.ca/~aaw/Hang/hash/Hash.html把一大堆元素映射到一段有限的存储空间上。核心思想:1.存放到第几个格子来自于key本身的信息,value只不过是个附加物2.search和insert都需要经过关键的hash函数3.如果不冲突时候，时间复杂度为O(1)4.处理冲突2种方法，链表法，开放线性探测法注意几点:正式的编程语言里(java,python)等，使用的是transfer法Hash表法问题：1.搬移的次数虽然不多，但也是会发生的。2.海量大数据下，比如2T数据，最坏情况下会退化为顺序查找法。排序二叉树(BinarySearchTree)BST1.概念二叉查找树（BinarySearchTree），或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。2.动画/~egolub/Java/BinaryTree.html3.问题如果插入的序列为随机插入，则最坏情况下查找的时间复杂度为logn如果插入的序列为有序(无论正序还是逆序),则最坏情况下查找的时间复杂度为n,会退化为顺序查找排序二叉树的插入和删除1.插入(insert函数)分别沿路径插入到左子树或右子树中2.删除(delete/remove函数)(1)若为叶子，直接删除(2)若只有左子树或只有右子树，则令其孩子代替原位置(3)若左右子树均不为空，则用直接后继(或前驱)代替其现有位置，再将直接后继(或前驱)删掉。改进与优化平衡二叉树（AVLtree）平衡因子(BalanceFactor)概念的引入：四种可能性，平衡旋转技术手段：LLRRRLLR平衡旋转技术(LL)平衡旋转技术(RR)平衡旋转技术(LR)平衡旋转技术(RL)最后，演示动画http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html堆(heap)1.排序2.优先级队列寻路算法等用到堆的两大性质1.堆是一棵完全二叉树(completebinarytree),即除了最后叶子一层的元素之外的其他层的元素包含尽可能多的元素。在最后叶子一层，所有的元素都尽可能在左边的位置。2.堆的每个元素都大于等于孩子节点的元素。（大根堆）可以存储在数组中堆的数组表示完全二叉树可以用一个数组(array)表示:根节点root是array[0]非根节点array[i]的parent节点位于array[(i-1)/2]，使用integerdivision(整数除法)非根节点array[i]的左child节点位于array[2i+1],右child节点位于array[2i+2]。这个关于孩子index=2i+1或2i+2的性质可以由等比数列求和推导得到堆的插入和删除1.插入(insert)risingprocess的过程叫做reheapificationupward.2.删除(remove/delete)removemethod删除一个堆的元素时，我们必须删除最大priority值的元素（优先级队列priorityqueue也可以由堆来实现，因为优先级队列每次拿出的是最大优先级的元素）。如果一个堆只有一个root根元素，则直接删除掉即可，然后减少heap的size；如果一个堆包含多于一个元素的时候，必须调整堆的结构使其满足堆性质。这样做：1.将根节点的引用copy出来。(为了这个method最后的return）2.先将叶子节点move至根节点，这样原来那个位置上的叶子节点就被拿出来了（次被称作out-of-placeelement）3.while（这个被move的out-of-placeelement节点小于他的孩子节点(child)){就将其最大的那个孩子与out-of-placeelement节点的位置交换。}4.returnstep1的answer源代码intDeleteMin(){/*heap[1]istheminimumelement.Soweremoveheap[1].Sizeoftheheapisdecreased.Nowheap[1]hastobefilled.Weputthelastelementinitsplaceandseeifitfits.Ifitdoesnotfit,takeminimumelementamongbothitschildrenandreplacesparentwithit.AgainSeeifthelastelementfitsinthatplace.*//**核心思想：把堆顶的删除，然后把完全二叉树的最后小弟(lastElement)放到合适的位置，这里不是每次向较大的孩子交换swap的办法向下沉淀的，而是先让比lastElement小的元素都挪上去，腾出位置后，lastElement直接放入到那个被腾出来的合适位置。因为大的元素要往下沉，所以没有必要每次交换2个元素（交换会费时间），只需要让这个lastElement元素与大孩子比较，如果lastElement，直接把当前的now赋值为他的孩子即可，而且因为把堆顶删掉了，所以堆顶的now的信息丢掉而赋值他的孩子信息给他也没什么问题。**/intminElement,lastElement,child,now;minElement=heap[1];lastElement=heap[heapSize--];//heapSize先赋值再--，这句非常精妙，表明了最后的元素不在被当做堆中的元素了，虽然数组中仍然存在

源代码(2)，接上页/*nowreferstotheindexatwhichwearenow*/for(now=1;now*2<=heapSize;now=child)//注意这里的for循环每次循环体执行结束后，是先执行最后一个分号后的now=child,再判断for中间的那句--是否退出循环的条件的，所以如果一般而言now最后会在循环结束后赋值为child，但是注意这里使用了break.因此直接会退出循环，而不执行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出循环，now现在指向的就是把所有的大于lastElement挪上去后的腾出来的合适位置}}heap[now]=lastElement;returnminElement;}数学分析1.一个堆的高度为[logn]+12.推导堆排序

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动画演示:/~jarc/idsv/lesson3.html2.百度经典面试题问题.有海量的服务器的IP访问日志，如何在内存及其有限的机器(几k的内存，比如嵌入式设备等)上，从中找出访问最频繁的几个IP？解法：时间换空间importheapqli=[random.randint(0,i)foriinxrange(1000)]#top10,还有个参数指定key，可以这样写key=lambdaentry:entry["count"]，在对list里每一项都是字典类型时的使用heapq.nlargest(10,li)sorted(li,reverse=True)[:10]B-树讲解前的准备（硬盘的结构和原理）硬盘的结构(2)硬盘的磁头越来越接近于磁道磁头的结构磁盘整体结构示意图B-树AB-treeofordermisanm-waytree(i.e.,atreewhereeachnodemayhaveuptomchildren)inwhich:1. thenumberofkeysineachnon-leafnodeisonelessthanthenumberofitschildrenandthesekeyspartitionthekeysinthechildreninthefashionofasearchtree（见缝插针）2. allleavesareonthesamelevel（叶子同级）3. allnon-leafnodesexcepttherootha