这是一个非常有挑战性的问题,需要综合运用计算机科学、算法和数据结构等知识。以下是一种基于哈希表的解决方案:
1. 将所有整数以64个整数一组进行分组。每组的大小为 64 * 4B = 256B。
2. 每个组中的整数,采用哈希表的方式进行统计。具体来说,可以使用开放地址法解决哈希冲突,将哈希表开到2GB的空间大小。统计整数出现次数时,可以使用32位整数来计数统计,每组最多2^32个整数,不会出现溢出情况。
3. 统计所有整数的出现次数,找到出现次数最多的整数。
这种解决方案可以最大限度地利用内存空间,将所有整数分组、哈希表分组统计。对于大量整数的处理,能够在相对较小的内存空间内高效完成。但要注意选择合适的哈希函数以及解决哈希冲突的方法,以确保哈希表的操作效率和正确性。
一、用4字节表示的整数个数为2^32≈40亿,而用2字节表示的无符号整数个数为2^16≈6万。
二、2G=2^31B≈20亿字节。
三、要找出出现次数最多的数,则应记录每个数出现的次数,最快的方法是在内存中将每个数出现的次数记录下来,记录的方法则是内存地址对应数,相应地址的内存单元记录次数,但2G内存以字节为单位仅能记录20亿个数,且每个数出现的次数大于255将会出现溢出风险。因此,这一方案不可取。
四、这样只能将每个次出现的次数记录在磁盘上。这样在磁盘上建一个16G的文件,每4字节对应一个整数,可对应40亿个整数,并用于记录相应整数的出现的次数。
1、将文件初始化。
2、依次读取数据,并用无符号整数记录在磁盘文件中,如出现溢出,则该数为次数最多的数。
3、从文件中读取各数出现的次数,用一个变量A记录最高次数,再用一个变量B记录最高次数出现的数据个数,要用个文件依次记录最高次数出现的数。当最高次数增加时,A+1,B置1,文件中写入该数,同次数的数出现时,B+1,文件相应位置写入该数,直到全部读完。
这样根本不需2G内存。
需求:
使用2G的内存,找出80亿个数字中出现最多的数字。
假设:
设计:
也就是说,将2G的内存分成单位为4字节的数组,可以一次获得0∼5亿多之间出现最多的数字。
步骤:
问题:
如果整数长度为8字节,则需要扫描约300多亿次(2^64/512M=2^40)。所以此算法并不适用于8字节的整数。
讨论:
当数字足够多,且数字取值范围足够大时,以有限内存获取出现次数最多的数字几乎是不可能的。因为数字的取值范围极大,且数字极多,任何哈希或其它分片的算法都有可能出现极端情况,导致分片数据过多而无法一次性导入内存计算。除非我们预先知道部分数字规律,否则考虑到效率,应该只会要求得到近似结果。
2g内存不是重点,80亿数字和取值范围才是重要的:
1. 80亿的数字至少需要加载一遍,才知道有哪些数据
2. 如果是取mapsize = 2ˇ16 或者 80亿开方,一个map<int,int>大mapsize的空间不到1m
3. 顺序读80亿数据,除以mapsize取余,同一余数放追加同一文件,余数作文件名
4. 顺序读取步骤3产生的所有文件,读取的每个文件时新建mapsize大小的hashmap,统计每个数的次数,再取该hashmap中出现最多次数的整数放到新的map中
5. 依次读完步骤3 产生的文件,就能得到每个文件最多次数的整数map
所有步骤需要80亿数据的两次读盘,一次写盘,mapsize次取最大值,80亿数据取余数
页面更新:2024-03-18
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号