20220530数据结构绿皮书读书笔记
9 表格和信息检索
9.1 简介
第七章我们证明过,仅仅使用比较的方式从n个元素中搜索1个元素,不可能小于lgn次的比较次数
事实上我们通常这么做,如果有500个不同的记录,每个的索引分别是0-499,我们可以使用这个索引快速的定位
基于表的不同形状,获取一个记录的动作是不一样的,但是最低可以是O(1),所需的时间不随着表的增大而增加
9.2 矩形表格
行优先表、列优先表。大部分编译器都使用行优先存储,假如行标是1、2,列标是5、6、7,基于行优先的存储就是15\16\17\25\26\27,基于列优先的存储就是15\25\16\26\17\27
这种存储的定位算法(index function)就是简单的线性函数,ni+j即可。如果从0开始或从1开始就+1或者-1
9.3 其他异形表格
9.3.1 三角表
可以使用额外的一个数组(Access table)记录每行或者每列的offset,其余位置都是0,或者没值
9.3.2 参差不齐锯齿状表格
三角形退化一点就是参差不齐的表格
9.3.3 倒排表
考虑到实际情况,比如电话本,需要同时按姓名、地址、电话查找,在这种情况下就需要倒排表。通过排好序的access table可以很快的定位原始数据,注意,access table里不会含有原始数据,只有下标,就像字典或者其他任何书的目录一样
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Index Name Address Phone 1 Hill, Thomas M. High Towers #317 2829478 2 Baker, John S. 17 King Street 2884285 3 Roberts, L. B. 53 Ash Street 4372296 4 King, Barbara High Towers #802 2863386 5 Hill, Thomas M. 39 King Street 2495723 6 Byers, Carolyn 118 Maple Street 4394231 7 Moody, C. L. High Towers #210 2822214 Access Array Name Address Phone 235 677 111 544 422 753 366 |
9.4 表格
新的抽象数据类型
一个table由以下部分组成:
1.索引的集合I
2.基础类型T
3.一个从I到T的函数映射
4.Table读取:评估任意I中index元素的操作
5.Table写入:修改任意I中index元素位置的值
注意区分table和array的概念区别,一个是抽象数据类型,一个是具体实现table或者顺序表的语言特性
9.5 应用,基数排序
radix sort又称桶排
不废话直接上代码
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/BucketSortBug V1.0.c
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/BucketSortBug V1.1.c
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/BucketSortBug V1.2.c
9.6 哈希
当table的key不再是一个index的情况下,如何把key和index一一关联?
hash table允许我们把很多不同分布的key映射到我们想要的分布上
哈希函数可以把一个key映射到数组的某个索引上,另外我们需要一些方法来解决映射结果相同,也就是碰撞
1.寻找好的hash函数
便于快速运算,结果有着良好的均匀分布
如果我们事先精确知道key如何分布,那就有可能构造一个足够高效的哈希函数,但实际上不可能。因此通常的方法是把key的一部分信息混合其他的方式来生成均匀分布的函数。注意:这里没有任何随机成分,如果相同的key多次执行hash函数,结果应当是一致的,否则将无法从表中再取出数据
常用套路1:truncation,忽略部分key,举个例子一个8位整数需要映射到1000个位置,直接使用其中3位数字即可,剩余的丢弃。这种方式生成的分布取决于key原始的分布,并不是非常均匀
常用套路2:folding,折叠,举个例子,21296876->212+968+76->1256,折叠通常会比truncation有效
常用套路3:modular,取模,n % x 的结果服从 0 ~ x – 1的分布
这里需要提下概率论与梳理统计hhhh但愿你们还记得,反正我记得的不多了
2.决定如何处理碰撞
常用套路1:线性探测,如果第一个位置不可用,则依照预定义的函数尝试下一个位置
常用套路2:聚簇,把多个碰撞的元素放到同一个位置直接存下来,例如拉链法
常用套路3:再哈希,把结果再过一次hash函数
常用套路4:二次探测,如果第一个位置h不可用,则尝试h+i^2的位置,h+1\h+4+h+9
常用套路5:key独立的增长,基于发生碰撞的key的自身数据决定下一个探测的位置
常用套路6:猴子探测(随机)
一般都会说因为泊松分布,所以loadfactor设置的0.75,但这么说一般能应付面试。如果深挖泊松分布的原理,其实是还挺不好解释的
下面的文章仅供参考
https://zhuanlan.zhihu.com/p/395174872
https://zhuanlan.zhihu.com/p/396019103
https://blog.csdn.net/weixin_43883685/article/details/109809049
9.9 应用:Life模拟
因为Life开局就是稀疏矩阵,大部分概率下也就是稀疏矩阵了,因此可以考虑使用压缩存储的办法进行处理
明天继续二叉树
mark 目前是429页 ,pdf是446页
0 Comments