人文艺术 > 挑战程序员同学,如何只用2GB内存从20/40/80亿个整数中找到出现

挑战程序员同学,如何只用2GB内存从20/40/80亿个整数中找到出现

2020-07-25 12:27阅读(85)

挑战程序员同学,如何只用2GB内存从20/40/80亿个整数中找到出现次数最多的数?:这种大数据处理的面试题,其实准备过就非常的简单,对于没准备过的人,简直就是灾

1

这种大数据处理的面试题,其实准备过就非常的简单,对于没准备过的人,简直就是灾难!1个32位整数需要4个字节,1KB可以存储256个数字,1GB可以存储2.6亿个数字。如果只有2亿个数字,我们可能全部加载到内存。很明显,但是我们不可能开出一个以数字大小位下标的数组,因为数字可能非常大,从1到100亿的数字都可能存在,如果我们是Java程序员,我们可以使用HashMap或者TreeMap等数据结构来维护一个Map<数字,次数>的映射,但是Map占用的内存大小其实比较难以评估,用2GB来操作是2亿的数据是存在内存溢出的风险的。这个算法虽然简单,但却又一定的风险。那么,我们有没有可能找到一个算法,在原来的数组上进行操作就找到最终答案的方法呢?其实并不难,我们对所有数字进行排序,常见的排序算法有冒泡排序、选择排序、堆排序、快速排序等。一般我们都使用快速排序,理论的算法复杂度位O(NLogN),又稳定又快。问题就转化成,在一个有序的数组里面,如何快速找到出现次数最多的数字。同样非常简单,我们维护一个计数器,只要从左往右依次检查,如果一个数等于上一个数,计数器就加一,否则计数器就变成1,重新开始统计。就可以巧妙地扫描一遍,找到出现次数最多地数字。

那么如果文件特别大呢?像题目中说的200亿个数字的文件,我们不可能把所有的数字加载到内存里面,这种问题,其实都有一个常见的套路,那便是分治。什么是分治呢?就是把问题拆成多个子问题进行求解,例如上述问题,我们可以把这200亿个数,按照个位十位数的不同,分成100个不同的文件,然后采用上述算法进行统计。很明显,分成如果大于2亿个 那就继续拆分!

这个题目还有非常多的解法,可以看看我的文章哦 https://www.toutiao.com/i6698339771942437384/

2

一、用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内存。

3

按位比较,比如先遍历一遍数字,判断第一位是0还是1多,然后便利多的那一位的数字,判断第二位是0还是1多,依次判断到第32位,就是出现次数最多的数字了

好吧,这个算法不对

我感觉这个题目是不是考的排序算法啊,这80亿个数字如果是有序的,则根本不需要2G内存

如果是无序的,则2G内存不够用,那么肯定要引入额外硬盘空间,既然都引入额外硬盘空间了,那也不用这么多内存了。

所以我估计题目应该是这样:

硬盘空间固定,存储了80亿个随机数字,硬盘可写,只有2G内存,找到其中出现次数最多的数。

解决方案就是排序,但是改写硬盘数据的时候必须成对的改写

4

需求:

使用2G的内存,找出80亿个数字中出现最多的数字。

假设

  1. 整数为4字节(2^32=4G),即最大40多亿。
  2. 所有的数字有80亿个。
  3. 所有数字在硬盘中,本身不会占用内存。
  4. 所用内存为2G多一些,例如有限的变量。但多出的内存和2G相比可以忽略不计。

设计:

  1. 80亿的计数可以用4字节保存(2^32=4G)。因为如果计数超过一半,则表明该数字一定是出现最多的。
  2. 2G的内存约可以保存5亿多数字的计数(2G/4=512M)。

也就是说,将2G的内存分成单位为4字节的数组,可以一次获得0~5亿多之间出现最多的数字。

步骤:

  1. 顺序扫描80亿个数字,忽略0~512M之外的数字,每个数字N的出现个数累加存放在第N个数组元素中。最后将最出现最多的数字及其次数保存起来,出现并列第一时,只保存第一个数字。如果过程中某数字出现个数超过40亿,则直接结束。
  2. 再次扫描所有数字,此次忽略512M~1G之外的数字。每个数字N的出现个数累加存放在第N-512M个数组元素中。本轮所获得的数字的出现个数和第一轮结果比较,保存较大的那个。
  3. 由于整数取值范围为4G,所以最多扫描8次后即可获得最终结果。

问题:

如果整数长度为8字节,则需要扫描约300多亿次(2^64/512M=2^40)。所以此算法并不适用于8字节的整数。

讨论:

当数字足够多,且数字取值范围足够大时,以有限内存获取出现次数最多的数字几乎是不可能的。因为数字的取值范围极大,且数字极多,任何哈希或其它分片的算法都有可能出现极端情况,导致分片数据过多而无法一次性导入内存计算。除非我们预先知道部分数字规律,否则考虑到效率,应该只会要求得到近似结果。

5

只有不是程序员才会出这样的题,你要知道,3、8、55246546是整数,但12345的阶乘,葛立恒数等也是整数,葛立恒数的葛立恒数次方也是整数,你没有限定整数范围,所以我觉得真正的程序员会先和你谈需求。另,我就是程序员。

6

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亿数据取余数

7

64mb内存就够。假设你的数据都存在文件中。

1,分治法,空间换时间,分片读取hash到n个文件中

2,统计每个文件中出现次数最多的数字

3,堆排序,对比每个文件中出现次数最多的数字。

4,结束

8

假设1-80亿,每个数字都只出现一次,只有一个数字出现2次,你们的算法还行?。。。算法要考虑坏情况的

9

说实话,这个题给定条件不完整,首先没说明每个数字的范围,第二没说明这些数怎么来的或者说这些数字存在哪里?比如是从一个ADC口读80亿次呢,还是从网络抓取回来呢?还是存在硬盘上面呢?或许是磁带机里面?第三,是否可以利用其他存储空间?比如硬盘。不然很难给出合适的解决方案

10

把数字变成字符串处理