3.6 符号表的应用

时间:2021-09-30 18:44:23

一.Set

1.一个存储不同值的集合。可以简单的忽略符号表的value,就可以将任何符号表的实现转化为一个Set类的实现。

2.应用:白名单和黑名单(即找出在/不在该集合的元素)

 

二.字典查找

1.例如:ip和address,读取相同的文件中,可以输入ip找到address,也可以输入address找到ip。根据需求,分别使用ip和address作为key建立符号表,即可快速查找。

3.6 符号表的应用

 

三.文件索引

1.目标:指定一系列文件,给定一个查询字符串可以找到所有包含该字符串内容的文件。

3.6 符号表的应用

2.解决方法:将查询的字符串当做key,将包含该字符串的文件集合当做值。

四.稀疏向量

1.问题:稀疏矩阵的乘法。假设矩阵是巨大的,直接相乘需要N2的时间。而稀疏矩阵大部分项都是0,直接相乘显然不合适。

2.使用符号表来表示稀疏向量。用非零元素所在的位置表示键,用具体元素表示值。这样空间消耗取决于非零元素的个数了。

3.6 符号表的应用

3.6 符号表的应用

3.对于稀疏矩阵来说,使用上面的向量表示法。即使用数组表示稀疏矩阵的每一行,然后每一行的元素使用符号表来存储。

这样每一行使用常数时间来计算,整个过程只需要使用线性时间即可完成计算。

3.6 符号表的应用