http://blog.gregwym.info/tag/search/ http://blog.gregwym.info/jiang-chrome-sou-suo-mo-ren-ding-wei-dao-google-com.html 2011-11-25T22:46:19+08:00 不同系统, 配置文件的位置不太一样.Windows在%USERPROFILE%\Local Settings\Application Data\Google\Chrome\User DataMac OS X在~/Library/Application Support/Google/Chrome/Linux在$HOME/?.config/google-chrome用编辑器打开Local State这个文件, 找到以下两行"last_known_googleurl": "http://www.google.***/","last_prompted_googleurl": "http://www.google.***/",将它们改为："last_known_googleurl": "http://www.google.com/","last_prompted_googleurl": "http://www.google.com/",打开Chrome以后随便搜索个东西...他会提示你正在使用google.com, 要不要更换到google.***|.选择继续使用, 大功告成! 嘿嘿 http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-qi--range-search-query.html 2011-04-08T12:06:40+08:00 在我总结这个Module之前允许我吐槽一下...`Assignment 5, 泥玛那个是什么脑残傻缺的ADT啊`! 放着Slide里这么好的三种ADT你不用啊`!!! 你跑去弄什么x-min-heap外加y-BST, 还弄个好听的名字叫Heap-tree`!!! 泥玛就是个残废啊`有木有有木有~!!! 不光残废啊, 是连TA自己都搞不懂到底该怎么用啊`!!! 连"You can slightly break the heap proerty"都说出来了...这种东西随便写写就让他过去吧`!!!!! 以后做工程真的用, 程序怎么死的都不知道啊`!!! 吐槽完毕= =`回归正题我们日常生活中的很多数据并不是一对一的KVP (不懂KVP的请去看, 总结四 - BST篇).拿Slide里的例子来说, 买一台电脑, 不光要看它的CPU是什么型号, 还要看内存多大, 硬盘多大, 显卡怎么样, 价钱多少, etc. 这样的数据都是一个key对多个value.这种情况下, 如果我需要找一台CPU 2.2GHz以上+内存4G-8G的电脑, 就需要从我的data中进行Range Search Query, 而且是2D的Range Search. 如果我在这个条件上再+要至少3T硬盘存xx...那就是3D的Range Search了.我们之前学习的Sort也好, Tree也好, 都是针对1D数据的排序和搜索, 碰到2D和3D就都傻了.以下三个ADT就能很好的解决这个问题.Quadtree 将所有数据放在一个平面空间里 (咱们想象力能及的只有2D和3D空间, 这里以2D举例) 将整个平面以对边中点的连线为基准, 切两刀分成四份 (3D空间的话, 需要多切一刀...) 针对每一个切出来的平面重复上一步, 直到这个平面内只有一个item为止 也就是说, Quadtree每个node最多有4个child, 如果以整个平面的中心为坐标中点的话, 这4个child代表每一个象限内的点的集合, 以此类推. 所有item都只存在于leaf中 Search和BST一样, 不解释 Insert就一个规则, 只要不是单身汉, 别管他3p还是5p, 都要给他们拆散! 直到新item有单间为止 Delete就是insert相反, 先把item赶走, 然后把单间拆掉 优点: 简单, 拆两半两半两半再两半就ok了; 对higher dimensions也很容易implementl; 缺点: 占用空间大; 如果数据分布不平均, Tree就会unbalanced, height就会变得很恐怖; Kd-tree 将item以x-coordinate排序, 画一条过median点的纵线(vertical) (同样以2D举例) 对第1步切分出来的两个平面, 分别以y-coordinate排序, 然后过median画一条横线(horizontal) 对第2步切分出来的平面(们)...重复第一步 如果某一步切分出的某个平面内只有一个item, 则停止. 此法解决了Quadtree会unbalanced的问题, 其他一样. 与Quadtree相同, 所有item都只存在于leaf中 Range Tree 以x-coordinate为基准建立balanced BST T (同样以2D举例) 针对T中的每一个node vi, 用vi及其所有children建立以y-coordinate为基准的Tassoc(vi) 将vi链接到Tassoc(vi) 也就是说, Range Tree第一层的每一个subtree背后, 都有一个以y-coordinate排序的另一个BST 如果是higher dimensions的话, 则要多几层associated BST嵌套 Search 用x-coordinate进行BST Search 对所有inside node的顶部(root of the subtree)的Tassoc, 执行y-coordinate的BST Search 对所有不确定的边缘node (卡在指定range的边上), 逐一进行单独判断 Insert 依照x-coordinate进行BST insertion 从最终insert的位置, travel回root. 并将item insert到途经的所有node的Tassoc中 Delete和Insert相反 缺点: balance难度较大. 更新1: 修正了Range Tree的错误解释更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/ http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-liu--dictionary-tricks.html 2011-04-08T03:03:14+08:00 各种Binary Search的变种 (杂种?)插值查找法 Interpolation Search 在已知Array A大小的前提下, 假设A中的数据呈线性排列 用比例推测所查找值 K, 可能存在的Index I I = Ilow + (Iupper - Ilow)(K - Klow) / (Kupper - Klow) 如果A中的数据分布比较平均, 此法效率比BS高 否则相反 更详细的解释, 可参考: 【演算】內插搜尋法 - Interpolation Search Gallop Search 先推测出K所在的范围, 然后执行BS 适用于数据量大的搜索. 通过减小BS的搜索范围, 优化性能. 跳跃列表 Skip Lists (我觉得最有意思的数据结构) 整个表以多层表的形式出现, 每层均包含"极小"和"极大"两个item 每个item拥有一个随机的height值 最顶层只包含两个极值, 层数越低, 包含的item越多, 直到底层. Search方式 从顶层起 如果该层中的下一项item大于K, 则落入下一层 否则继续在该层向后查找 针对访问概率进行的优化自排序搜索 Self-Organizing Search 如果我们知道某一系列数据中, 每一个item可能被访问的概率 依照每一项的概率对数据进行排序, 优化高概率item的访问效率 如果不知道可能的访问概率, 则需要... 动态排序 Dynamic Ordering 方法一: Move-To-Front(MTF) 将每次搜索到的item移到最前 近期内再搜索此item的时候, 效率会提高 方法二: Transpose 将每次搜索到的item与其前一项互换 多次访问同一item以后, 该item的排序会提前很多, 访问效率会提高 更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/