C++算法之海量数据处理方法的总结分析

海量数据处理中常用到的技术
1. Bloom Filtering
基本的Bloom Filtering支持快速的插入和查找操作，是一种hash表技术。基本的数据结构非常简单，容量为m的位数组，k个hash函数，将输入的n个元素存储在位数组里面。
每次插入一个新的元素，先计算该元素的k个hash指，将位数组对应hash值位置为1. 查找某个元素时，同样的先计算k个hash值，然后查询看是否对应位数组中得k位是否都是1，是则断定元素存在。
基本的Bloom Filtering算法可以用于允许误差的快速判重操作。集合的交集、并集的计算。
Bloom Filtering有个改进的版本counting bloom filtering可以支持数据的删除操作，countering bloom filtering和基本的bloom filtering相比，位数组中每一位的取值扩展成多位，基本的bloom filtering用1bit表示一位。插入一个元素时，所有的k位都加1，删除时都减1，查找时如果k个值都大于0则判定为存在。CBF中有个很重要的参数，即每一位的位数为多少。可以通过理论证明，位数一般取4就足够了，可以支持同一个数据插入16次。
bitmap可以看做bloom filtering的特例
2. Hash表技术
d-left hash hash表负载均衡技术。将hash表分成d段，设计d个hash函数，更具负载选择一个合适的段存放数据。查找时要计算d个hash值，分别在d段中找。
常用于统计次数。
3. 堆技术
堆有两个典型的应用：
多路归并排序
求TopK
多路归并排序时，降序排序时用最大堆，升序排序用最小堆。
TopK时，求TopK最大时，用最小堆，求TopK最小时用最大堆。求topK最大时，利用最小堆堆维护K个值，当新扫描的值大于堆顶元素时，堆顶元素删除，插入新的值。这样扫描完一遍数据，既可以求得topK最大。
4. 双层桶（多层桶）设计
hash表技术是一种direct addr 技术，但是当数据范围分布过广、且数据量非常大的时候，采用hash表直接direct addr技术就不行了，这是可以使用多层hash技术。将原始数据范围分成小段，每一段内存可以装载，段内可以使用direct addr table技术。可以用多层分级快速定位到小段。

赞 (0)

相关推荐

  • C++基本算法思想之递推算法思想

    C++基本算法思想之递推算法思想

    递推算法是非常常用的算法思想,在数学计算等场合有着广泛的应用.递推算法适合有明显公式规律的场合. 递推算法基本思想递推算法是一种理性思维莫斯的代表,根据已有的数据和关系,逐步推到而得到结果.递推算法的执行过程如下: (1)根据已知结果和关系,求解中间结果. (2)判断是否达到要求,如果没有达到,则继续根据已知结果和关系求解中间结果.如果满足要求,则表示寻找到一个正确答案. 递推算法需要用户知道答案和问题之间的逻辑关系.在许多数学问题中,都有明确的计算公式可以遵循,因此可以采用递推算法来实现. 递

  • C++实现各种排序算法类汇总

    C++可实现各种排序算法类,比如直接插入排序.折半插入排序.Shell排序.归并排序.简单选择排序.基数排序.对data数组中的元素进行希尔排序.冒泡排序.递归实现.堆排序.用数组实现的基数排序等. 具体代码如下: #ifndef SORT_H #define SORT_H #include <iostream> #include <queue> using namespace std; // 1.直接插入排序 template<class ElemType> void

  • C++实现汉诺塔算法经典实例

    本文所述为汉诺塔算法的C++代码的经典实现方法. 汉诺塔问题描述:3个柱为a.b.c,圆盘最初在a柱,借助b柱移到c柱.需要你指定圆盘数. 具体实现代码如下: #include <iostream> using namespace std; int times = 0; //全局变量,搬动次数 //第n个圆盘从x柱搬到z柱 void move(int n, char x, char z) { cout << "第" << ++times <&l

  • c++实现MD5算法实现代码

    测试结果和百度百科测试例子一致. 实现过程中需要注意事项:最后把四个变量A B C D 链接成结果时 ,注意变量高低位的先后顺序,具体参考 LinkResult()方法. md5.h #ifndef _MD5_H_ #define _MD5_H_ #include <iostream> #include <string> using namespace std; class MD5 { public: typedef unsigned char uchar8; //make sur

  • C++遗传算法类文件实例分析

    本文所述为C++实现的遗传算法的类文件实例.一般来说遗传算法可以解决许多问题,希望本文所述的C++遗传算法类文件,可帮助你解决更多问题,并且代码中为了便于读者更好的理解,而加入了丰富的注释内容,是新手学习遗传算法不可多得的参考代码. 具体代码如下所示: #include "stdafx.h" #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #inc

  • 采用C++实现区间图着色问题（贪心算法）实例详解

    本文所述算法即假设要用很多个教室对一组活动进行调度.我们希望使用尽可能少的教室来调度所有活动.采用C++的贪心算法,来确定哪一个活动使用哪一间教室. 对于这个问题也常被称为区间图着色问题,即相容的活动着同色,不相容的着不同颜色,使得所用颜色数最少. 具体实现代码如下: //贪心算法 #include "stdafx.h" #include<iostream> #define N 100 using namespace std; struct Activity { int n

  • C++泛型算法的一些总结

    泛型算法的一些总结1.每个泛型算法的实现都独立于单独的容器,并且不依赖于容器存储的元素类型. 2.泛型算法从不直接添加或删除元素. 3.与容器的类型无关,只在一点上隐式地依赖元素类型:必须能够对元素做比较运算. A.需要某种遍历集合的方式:能够从一个元素向前移到下一个元素. B.必须能够知道是否到达了集合的末尾. C.必须能够对容器中的每一个元素与被查找的元素进行比较. D.需要一个类型来指示元素在容器中的位置,或者表示找不到该元素. 4.迭代器将算法和容器绑定起来.算法基于迭代器及其操作实现,

  • C++实现迷宫算法实例解析

    本文以实例形式描述了C++实现迷宫算法.本例中的迷宫是一个矩形区域,它有一个入口和一个出口.在迷宫的内部包含不能穿越的墙或障碍.障碍物沿着行和列放置,它们与迷宫的矩形边界平行.迷宫的入口在左上角,出口在右下角 本实例迷宫算法的功能主要有: 1.自动生成10*10迷宫图 2.判断是否有迷宫出口,并且画出路线图 具体实现代码如下: # include <iostream> # include <list> # include <sys/timeb.h> # include

  • k均值算法c++语言实现代码

    复制代码 代码如下: //k-mean.h #ifndef KMEAN_HEAD #define KMEAN_HEAD #include <vector> #include <map> //空间点的定义 class Node {     public:        double pos_x;        double pos_y;        double pos_z;      Node()      {          pos_x = 0.0;          pos

  • VC++实现选择排序算法简单示例

    本文以一个非常简单的实例说明VC++选择排序算法的实现方法,对n个记录进行n-1趟简单选择排序,在无序区中选取最小记录. 具体实现代码如下: #include<iostream> using namespace std; //简单选择排序 void SelectSort(int r[ ], int n) { int i; int j; int index; int temp; for (i=0; i<n-1; i++) //对n个记录进行n-1趟简单选择排序 { index=i; for

  • C++实现顺序排序算法简单示例代码

    本文实例讲述了最直接的顺序排序法VC++示例代码,还记得以前上学时候这是计算机的必考题,而且在排序算法中,顺序排序似乎是最简单的了,也是最容易掌握的.现在列出来让大家重新回顾一下! 具体代码如下: //顺序排序 void InsertSort(int r[], int n){ for (int i=2; i<n; i++){ r[0]=r[i]; //设置哨兵 for (int j=i-1; r[0]<r[j]; j--) //寻找插入位置 r[j+1]=r[j]; //记录后移 r[j+1]

随机推荐