大数据处理
Laiyong Wang Lv5

源网址:https://blog.csdn.net/Wantbebetter/article/details/121671219

解题技巧

  • 哈希函数可以把数据按照种类均匀分流
  • 布隆过滤器用于集合的建立与查询,并可以节省大量空间
  • 一致性哈希解决数据服务器的负载管理问题
  • 利用并查集结构做岛问题的并行计算
  • 位图解决某一范围上数字的出现情况,并可以节省大量空间
  • 利用分段统计思想、并进一步节省大量空间
  • 利用堆、外排序来做多个处理单元的结果合并

经典问题:

1、设计算法找到每日访问百度出现次数最多的IP地址
  • 思路
    数据量肯定非常大,不能全加载到内存里面进行计算,所以需要拆分
    所以设计一个算法,使所有的ip进行处理后,可能有10W条结果,将对应的ip分别存放至这十万个文件中
    根据文件的大小,在最大的那一批文件里进行计算统计即可
2、两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件的交集
  • 这题其实很傻逼,限定100亿整数和1G内存了
    其实已经限定了用位图进行处理了,两个位图(二进制),进行异或计算即可
  • 但是可以延伸出另外一个问题
    那些树没有出现
    位置为0的数字就是没出现的
3、两个文件,分别有100亿个string,我们只有1G内存,如何找到两文件交集?分别给出精确算法和近似算法
  • 近似算法
    首先要想到布隆过滤器,也可以自己写个算法,但是没必要。
    布隆过滤器,不存在的肯定不存在,存在的可能不存在
    所以做判断
  • 精确算法
    设计个算法,使每个string 都有10W个结果,相同结果的string 保存在同一个文件内,第一个大文件后缀1,第二个大文件后缀2,然后前缀相同的进行比较,假设超内存了,可以345.
    4、一个词典,包含N个英文单词,现在任意给一个字符串,设计算法找出包含这个字符串的所有英文单词
    非常傻逼的题
    算了
    刚看过树的数据机构,用多叉树来处理
    先将词典全部遍历,生成26颗树(原则上来说,二十六个字母开头的单词都会有),跟节点就是字母,各种子节点就是字符串的后缀,然后用字符串在与26颗树进行匹配
 Comments