网页制作与网站建设pdf,网站开发前端和后端工作,wordpress删除时间,江门制作公司网站1. 从40个亿中产生一个不存在的整数
题目要求#xff1a;给定一个输入文件#xff0c;包含40亿个非负整数#xff0c;请设计一个算法#xff0c;产生一个不存在该文件中的整数#xff0c;假设你有1GB的内存来完成这项任务。 ● 进阶#xff1a;如果只有10MB的内存可用给定一个输入文件包含40亿个非负整数请设计一个算法产生一个不存在该文件中的整数假设你有1GB的内存来完成这项任务。 ● 进阶如果只有10MB的内存可用该怎么办
1.1 哈希存储
最坏的情况是里面数据都存在那么这个哈希表的记录数就是40亿而一个整数占4个字节也就是说哈希表记录数占据160亿个字节大概是16G很显然是超过了1GB这种方法就不需要考虑了。但是如果转换成比特存储1个字节等于8比特空间就小了很多。
1.2 位图bitmap存储
但是如果使用位存储需要申请一个长度为 4294967295 的 bit 类型的数组 bitArr就是boolean类型8 个bit 为1B所以长度为 4 294 967 295 的 bit 类型的数组占用 500MB 空间bitArr 上的每个位置只可以表示 0 或1 状态。只要存在这个数据那么就将这个数据状态设置为1表示重复了最后只需要找到元素下标为0的数就是不存在的数最好的情况就是只有极个别的数据不存在或者没有数据不存在查找的速度也就提升了。
1.3 10MB存储
上面bitmap里面需要500MB空间而这里只给10MB意味着至少需要50块空间而一般是使用2的倍数进行分块所以这里可以使用64块来存储。
每一块里面的数据大小都是67 108 864个只要遍历一次就能统计每个区间内的元素个数里面肯定有一个小于67 108 864然后再bitmap映射找到不存在的那个数。
2. 用 2GB 内存在 20 亿个整数中找到出现次数最多的数
题目要求有一个包含 20 亿个全是 32 位整数的大文件在其中找到出现次数最多的数。
2.1 哈希存储
一般统计个数使用哈希比较多词频统计每一个key都对应一个整数假设没有重复的数key的大小就是4bvalue的大小也是4b那么一条记录占用8b20亿占用16G超过了题目要求。
2.2 分块
2亿条记录是占用1.6G我只需要将这个20亿数据分割10块就能保证每一块的数据内存不会超过2G接下来就是分别统计每一块里面出现最多的元素将所有的块的次数进行比较找出最多的一条数据。
3. 从100 亿个 URL中查找的问题
题目有一个包含 100 亿个 URL 的大文件假设每个 URL 占用 64B请找出其中所有重复的 URL。
这一题的思路根据前面几个题目相比也是很明显依然是采用哈希存储然后将这个大的哈希分成若干个小的文件分别统计每一块里面的元素出现的个数。但是这里需要明确一下这个空间占用是多少才能进行相应的分片。
