0%
大数据问题的一般思路
利用位数组
- 利用基础类型（比如int）制作一个bit数组
- 比如一个int是32位，那么10个int就是320位的位数组
- 利用每个位的1和0计数数字的存在与否
小空间词频统计
- 假如用一个小空间计算40亿个数字中
unsigned int中的哪个不包括在内
- 先申请允许内存大小的数组，检查系统内存能够允许的数组长度，找最近的长度为2的整数幂次的数组长度作为长度
- 然后按照数组的长度均分
unsigned int范围得到小的范围长度
- 遍历整个数组，每个元素除以小范围的长度，结果向下取整得到自己属于哪个小范围
- 将词频数组对应的index位置（上一步计算的结果）
+1
- 循环一遍之后，词频数组中肯定有某个位置的词频达不到理论上的小范围长度
- 将整个统计范围的长度从整个
unsigned int范围调整到上一个词频达不到满的小范围
- 重复上述步骤遍历整个数据，丢弃所有不在范围内的数字，其他数字按照第二次划分的小范围分类，统计结束之后再看哪个位置的词频达不到此时的小范围
- 统计巨量URL的访问次数
- 使用哈希函数将URL转换，然后分流到一定数量（按照服务器的内存资源决定）的小文件中，每个小文件使用一个利用URL被访问次数组织的大根堆
- 将每个大根堆的堆顶组织成大根堆得到总堆
- 结果就是依次将内容从总堆中弹出，弹出之后找到这个元素原来所在的大根堆，同样将这个元素弹出，然后弹出后的大根堆的头部放入总大根堆中。
- 利用位数组统计出现了两次的数字
- 用两位表示一个数字是否出现过
00没出现过，01出现一次，10出现两次，11出现大于2次
- 利用小空间找中位数
- 同样利用小范围词频统计（第一种）操作
- 统计到找出中位数在哪个小分区里
- 然后对这个对应的小分区再等分找到具体的中位数的位置
小空间给大数组
- 方法一
- 小空间使用小根堆
- 小根堆存储的内容是<数字，出现次数>的元组，有小根堆中存在的数字的时候，相应的出现次数+1
- 小根堆不能直接用一条记录的空间计算，需要考虑一些额外的开销，实际可用的空间可能是总空间/16或者其他数值
- 堆的大小用最接近的2的整数次幂次
- 然后按照被排序的内容/堆的大小得到被排序内容按大小分的小段
- 第一次处理落在最小部分段内的数据，第二次处理第二小部分段内的数据…
- 都处理完即可得到所有排序
- 方法二
- 使用一个大根堆存储此时数组中最小的几种数字
- 假如此时一个新的数字小于此时大根堆中最大的数字，那么可以加入
- 假如这个数字比大根堆中最大的数字还大，那么说明这个数字不属于整个数组中最小的k个数字之一，直接忽略（k为堆的大小）
- 假如此时大根堆的数字超出数字限制，那么将最大的数字弹出然后将新的数字压入
- 然后将大根堆内的所有数字逆序排出并清空堆，然后给堆设置最小值，等于上次弹出之前堆中最大的数字，以后只考虑大于这个数字的数