大数据处理时的一种BitMap小算法

本文涉及的产品
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: 一种大数据外部排序(内存无法加载所有排序元素)、去除重复元素、快速找到随机被删除元素的BitMap小算法,核心思想即通过将一个数作为下标(index)来索引一个bit表示一个数是否存在,排序时的时间复杂度为O(N),需要的额外空间的复杂度O(N/8)...

一种大数据外部排序(内存无法加载所有排序元素)、去除重复元素、快速找到随机被删除元素的BitMap小算法,核心思想即通过将一个数作为下标(index)来索引一个bit表示一个数是否存在,排序时的时间复杂度为O(N),需要的额外空间的复杂度O(N/8),支持整个int范围(正负数都支持)的算法示例如下:


char BitMask[] = {0x80 , 0x40 , 0x20 , 0x10 , 0x8 , 0x4 , 0x2 , 0x1};


int WriteNumberBitToByte(char *ByteArra , unsigned int ByteArraSize , int Number)
{
	//printf("%d,%d,%d\n",(ByteArraSize * 4) - 1,-(ByteArraSize*4),Number);
	
	if (((int)(ByteArraSize * 4) - 1) < Number || Number<-(int)(ByteArraSize*4) )
	{
		return 0;	//failed,number out of bytearra.
	}

	int BaseArraBitPos = ByteArraSize *4;	//ByteArraSize *8 /2

	BaseArraBitPos+=Number;


	printf("BaseArraBitPos=%d,Number=%d\n",BaseArraBitPos,Number);
	ByteArra[BaseArraBitPos/8] |= Mask[BaseArraBitPos%8];

	return 1;	//success
}

int IsNumberBitInByte(char *ByteArra , unsigned int ByteArraSize , int Number)
{
	if (((int)(ByteArraSize * 4) - 1) < Number || Number<-(int)(ByteArraSize*4) )
	{
		return 0;	//failed,number out of bytearra.
	}


	int BaseArraBitPos = ByteArraSize *4;	//ByteArraSize *8 /2

	BaseArraBitPos+=Number;

	if (ByteArra[BaseArraBitPos/8] & BitMask[BaseArraBitPos%8]) {
		return 1;
	}

	return 0;	//number not found.
}

void PrintOrderedBitMap(char *BitMap,unsigned int BitMapCount)
{
	int MinmumNumber = -(BitMapCount*8/2);
	int MaximumValue = (BitMapCount*8/2)-1;

	for (int i = MinmumNumber; i <= MaximumValue; ++i)
	{
		if (IsNumberBitInByte(BitMap,BitMapCount,i))
		{
			printf("%d,", i);
		}
	}

	printf("\n");
}


int main()
{
	int Arra[] = {3,-4,2,0,-1,-8,7,-12,10};

	int MaximumValue =Arra[0],MinmumValue=Arra[0];
	for (int i = 0; i < sizeof(Arra)/sizeof(Arra[0]); ++i)
	{
		if(MaximumValue<Arra[i]) {
			MaximumValue = Arra[i];
		}
		if (MinmumValue>Arra[i])
		{
			MinmumValue = Arra[i];
		}
	}

	MaximumValue=MaximumValue<0?-MaximumValue:MaximumValue;
	MinmumValue=MinmumValue<0?-MinmumValue:MinmumValue;

	MaximumValue=MaximumValue>MinmumValue?MaximumValue:MinmumValue;
	
	printf("MaximumValue=%d\n",MaximumValue);
	//unsigned int BitMapCount = (MaximumValue*2+7)/8;
	unsigned int BitMapCount = (MaximumValue+3)/4;
	BitMapCount = BitMapCount>0?BitMapCount:1;
	char *BitMap = (char*)malloc(BitMapCount);

	for (int i = 0; i < sizeof(Arra)/sizeof(Arra[0]); ++i)
	{
		WriteNumberBitToByte(BitMap,BitMapCount,Arra[i]);
	}

	PrintOrderedBitMap(BitMap,BitMapCount);
}


仅支持unsigned int范围的算法示例如下:

char BitMask[] = {0x80 , 0x40 , 0x20 , 0x10 , 0x8 , 0x4 , 0x2 , 0x1};


int WriteNumberBitToByte(char *ByteArra , unsigned int ByteArraSize , unsigned int Number)
{
	if (((ByteArraSize * 8) - 1) < Number )
	{
		return 0;	//failed,number out of bytearra.
	}

	int BytePos = Number / 8;
	int BitPos = Number % 8;


	ByteArra[BytePos] |= BitMask[BitPos];

	return 1;	//success
}

int IsNumberBitInByte(char *ByteArra , unsigned int ByteArraSize , unsigned int Number)
{
	if ((ByteArraSize * 8 - 1) < Number )
	{
		return 0;	//failed,number out of bytearra.
	}

	int BytePos = Number / 8;
	int BitPos = Number % 8;

	if (ByteArra[BytePos] & BitMask[BitPos]) {
		return 1;
	}

	return 0;	//number not found.
}


上面的算法都是用一个bit来表示一个数,即只有2种可能,要么有,要么无,可以扩展到一个字节表示一个数,这样就可以统计出现255次范围内的重复元素,原理以此类推。


另外用bit来表示一个int数,节约了31倍的内存空间,即int(4*8),bit(8/1),所以数据量越来使用这种方式的优势越明显,前提是场景适用这种方式。

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
目录
相关文章
|
1月前
|
存储 分布式计算 算法
【底层服务/编程功底系列】「大数据算法体系」带你深入分析MapReduce算法 — Shuffle的执行过程
【底层服务/编程功底系列】「大数据算法体系」带你深入分析MapReduce算法 — Shuffle的执行过程
41 0
|
3天前
|
分布式计算 算法 Java
阿里云ODPS PySpark任务使用mmlspark/synapseml运行LightGBM进行Boosting算法的高效训练与推理
阿里云ODPS PySpark任务使用mmlspark/synapseml运行LightGBM进行Boosting算法的高效训练与推理
|
18天前
|
分布式计算 算法 搜索推荐
Java中可以用的大数据推荐算法
在Java中实现大数据推荐算法,通常使用Apache Mahout、Weka、DL4J或Spark MLlib。本文简要介绍了三种推荐算法:基于内容的推荐、协同过滤推荐和深度学习推荐,以及它们的使用场景。提供了每种算法的伪代码或关键代码片段。基于内容的推荐适用于有用户历史行为和物品内容信息的场景,而协同过滤适用于大量用户行为数据的场景,深度学习推荐则用于处理复杂特征。在实现时,注意数据预处理、特征提取、用户画像构建和相似度计算。
24 1
|
4天前
|
机器学习/深度学习 人工智能 自然语言处理
AI大模型的核心成功因素通常可以归结为三大要素:大数据、大算力和强算法。
AI大模型的核心成功因素通常可以归结为三大要素:大数据、大算力和强算法。
23 0
|
1月前
|
存储 算法 搜索推荐
【大数据分析与挖掘技术】Mahout推荐算法
【大数据分析与挖掘技术】Mahout推荐算法
28 0
|
1月前
|
分布式计算 算法 搜索推荐
阿里巴巴内部:全技术栈PPT分享(架构篇+算法篇+大数据)
我只截图不说话,PPT大全,氛围研发篇、算法篇、大数据、Java后端架构!除了大家熟悉的交易、支付场景外,支撑起阿里双十一交易1682亿元的“超级工程”其实包括以下但不限于客服、搜索、推荐、广告、库存、物流、云计算等。 Java核心技术栈:覆盖了JVM、锁、并发、Java反射、Spring原理、微服务、Zookeeper、数据库、数据结构等大量知识点。 大数据:Spark、Hadoop
|
1月前
|
SQL 存储 大数据
【拿走不谢】大数据高效查询神器--bitmap
【拿走不谢】大数据高效查询神器--bitmap
|
6月前
|
存储 算法 搜索推荐
大数据管理的重要思想和算法总结----排序(上)
大数据管理的重要思想和算法总结----排序(上)
44 0
|
1月前
|
存储 算法 安全
【云计算与大数据技术】数据分片哈希算法、路由算法、复制算法的讲解(图文解释 超详细)
【云计算与大数据技术】数据分片哈希算法、路由算法、复制算法的讲解(图文解释 超详细)
146 0
|
1月前
|
消息中间件 存储 算法
【云计算与大数据技术】数据编码LZSS算法、Snappy压缩库及分布式通信系统的讲解(图文解释 超详细)
【云计算与大数据技术】数据编码LZSS算法、Snappy压缩库及分布式通信系统的讲解(图文解释 超详细)
168 0