某储备粮的“学习笔记”

by 咳嗽di小鱼

不同系统, 配置文件的位置不太一样.

Windows在
%USERPROFILE%\Local Settings\Application Data\Google\Chrome\User Data

Mac OS X在
~/Library/Application Support/Google/Chrome/

Linux在
$HOME/?.config/google-chrome

用编辑器打开Local State这个文件, 找到以下两行

"last_known_googleurl": "http://www.google.***/",
"last_prompted_google
url": "http://www.google.***/",

将它们改为:

"last_known_googleurl": "http://www.google.com/",
"last_prompted_google
url": "http://www.google.com/",

打开Chrome以后随便搜索个东西...他会提示你正在使用google.com, 要不要更换到google.***|.
选择继续使用, 大功告成! 嘿嘿


在我总结这个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


  1. 将所有数据放在一个平面空间里 (咱们想象力能及的只有2D和3D空间, 这里以2D举例)
  2. 将整个平面以对边中点的连线为基准, 切两刀分成四份 (3D空间的话, 需要多切一刀...)
  3. 针对每一个切出来的平面重复上一步, 直到这个平面内只有一个item为止

Quadtree.png
也就是说, 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


  1. 将item以x-coordinate排序, 画一条过median点的纵线(vertical) (同样以2D举例)
  2. 对第1步切分出来的两个平面, 分别以y-coordinate排序, 然后过median画一条横线(horizontal)
  3. 对第2步切分出来的平面(们)...重复第一步
  4. 如果某一步切分出的某个平面内只有一个item, 则停止.

kd-tree.png
  • 此法解决了Quadtree会unbalanced的问题, 其他一样.
  • 与Quadtree相同, 所有item都只存在于leaf中

Range Tree


  1. 以x-coordinate为基准建立balanced BST T (同样以2D举例)
  2. 针对T中的每一个node vi, 用vi及其所有children建立以y-coordinate为基准的Tassoc(vi)
  3. 将vi链接到Tassoc(vi)

Range_trees.png
  • 也就是说, 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/


各种Binary Search的变种 (杂种?)


插值查找法 Interpolation Search
  • Interpolation_Search.jpg
  • 在已知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, 则落入下一层
    • 否则继续在该层向后查找
  • Skip_List.png

针对访问概率进行的优化

自排序搜索 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/