C++算法之海量数据处理方法的总结分析
2023-06-13 09:15:00 时间
海量数据处理中常用到的技术
1.BloomFiltering
基本的BloomFiltering支持快速的插入和查找操作,是一种hash表技术。基本的数据结构非常简单,容量为m的位数组,k个hash函数,将输入的n个元素存储在位数组里面。
每次插入一个新的元素,先计算该元素的k个hash指,将位数组对应hash值位置为1.查找某个元素时,同样的先计算k个hash值,然后查询看是否对应位数组中得k位是否都是1,是则断定元素存在。
基本的BloomFiltering算法可以用于允许误差的快速判重操作。集合的交集、并集的计算。
BloomFiltering有个改进的版本countingbloomfiltering可以支持数据的删除操作,counteringbloomfiltering和基本的bloomfiltering相比,位数组中每一位的取值扩展成多位,基本的bloomfiltering用1bit表示一位。插入一个元素时,所有的k位都加1,删除时都减1,查找时如果k个值都大于0则判定为存在。CBF中有个很重要的参数,即每一位的位数为多少。可以通过理论证明,位数一般取4就足够了,可以支持同一个数据插入16次。
bitmap可以看做bloomfiltering的特例
2.Hash表技术
d-lefthashhash表负载均衡技术。将hash表分成d段,设计d个hash函数,更具负载选择一个合适的段存放数据。查找时要计算d个hash值,分别在d段中找。
常用于统计次数。
3.堆技术
堆有两个典型的应用:
多路归并排序
求TopK
多路归并排序时,降序排序时用最大堆,升序排序用最小堆。
TopK时,求TopK最大时,用最小堆,求TopK最小时用最大堆。求topK最大时,利用最小堆堆维护K个值,当新扫描的值大于堆顶元素时,堆顶元素删除,插入新的值。这样扫描完一遍数据,既可以求得topK最大。
4.双层桶(多层桶)设计
hash表技术是一种directaddr技术,但是当数据范围分布过广、且数据量非常大的时候,采用hash表直接directaddr技术就不行了,这是可以使用多层hash技术。将原始数据范围分成小段,每一段内存可以装载,段内可以使用directaddrtable技术。可以用多层分级快速定位到小段。
每次插入一个新的元素,先计算该元素的k个hash指,将位数组对应hash值位置为1.查找某个元素时,同样的先计算k个hash值,然后查询看是否对应位数组中得k位是否都是1,是则断定元素存在。
基本的BloomFiltering算法可以用于允许误差的快速判重操作。集合的交集、并集的计算。
BloomFiltering有个改进的版本countingbloomfiltering可以支持数据的删除操作,counteringbloomfiltering和基本的bloomfiltering相比,位数组中每一位的取值扩展成多位,基本的bloomfiltering用1bit表示一位。插入一个元素时,所有的k位都加1,删除时都减1,查找时如果k个值都大于0则判定为存在。CBF中有个很重要的参数,即每一位的位数为多少。可以通过理论证明,位数一般取4就足够了,可以支持同一个数据插入16次。
常用于统计次数。
多路归并排序
求TopK
多路归并排序时,降序排序时用最大堆,升序排序用最小堆。
TopK时,求TopK最大时,用最小堆,求TopK最小时用最大堆。求topK最大时,利用最小堆堆维护K个值,当新扫描的值大于堆顶元素时,堆顶元素删除,插入新的值。这样扫描完一遍数据,既可以求得topK最大。
相关文章
- C++学习之路—— STL标准模板库概述
- Dev-c++中将头文件和头文件函数分离,编译主函数跳出undefined reference to 的问题解决
- c语言random函数在vc,C++ 中随机函数random函数的使用方法
- c++获取子类窗口句柄位置_C++中各种获取窗口句柄的方法「建议收藏」
- 算法(c/c++入门)第一章第一节
- Android通过jni调用本地c/c++接口方法总结
- c++ auto类型_auto C++
- 【c++】【基础】【primer_plus】【第四章】指针与内存
- C++动态库和静态库_动态库和静态库调用方法
- C++字符串加密_c++字符串连接函数
- 软件开发入门教程网之C++ 信号处理
- 【C++】"undefined reference to" 问题常见的解决方法
- 【C++ 语言】C++字符串 ( string 类 | 创建方法 | 控制台输出 | 字符串操作 | 栈内存字符串对象 | string* )
- 让 Python 拥有 C/C++ 一样的速度,编译神器 Codon 发布!
- C++ 测试框架 GoogleTest 初学者入门篇 丙
- 关于C/C++中typedef的定义与用法总结
- c++int转string方法
- c++大数阶乘的实现方法
- 深入分析C++中执行多个exe文件方法的批处理代码介绍
- 使用C++实现全排列算法的方法详解
- C++实现基数排序的方法详解
- C++运算符重载成员函数与友元函数详解
- C++中访问字符串的三种方法总结
- C与C++之间相互调用实例方法讲解
- C++实现修改函数代码HOOK的封装方法
- VC++获得当前进程运行目录的方法
- 让Sqlite脱离VC++Runtime独立运行的方法
- C++实现获取IP、子网掩码、网关、DNS等本机网络参数的方法
- VC++实现程序开机启动运行的方法