当前位置: 首页 > news >正文

深圳专业网络营销外包公司福州百度seo排名软件

深圳专业网络营销外包公司,福州百度seo排名软件,邯郸做网站最好的公司,不用vip会员也能观看的软件1. 从40个亿中产生一个不存在的整数 题目要求:给定一个输入文件,包含40亿个非负整数,请设计一个算法,产生一个不存在该文件中的整数,假设你有1GB的内存来完成这项任务。 ● 进阶:如果只有10MB的内存可用&a…

1. 从40个亿中产生一个不存在的整数

题目要求:给定一个输入文件,包含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的大小就是4b,value的大小也是4b,那么一条记录占用8b,20亿占用16G,超过了题目要求。

2.2 分块

2亿条记录是占用1.6G,我只需要将这个20亿数据分割10块,就能保证每一块的数据内存不会超过2G,接下来就是分别统计每一块里面出现最多的元素,将所有的块的次数进行比较找出最多的一条数据。

3. 从100 亿个 URL中查找的问题

题目:有一个包含 100 亿个 URL 的大文件,假设每个 URL 占用 64B,请找出其中所有重复的 URL。

这一题的思路根据前面几个题目相比也是很明显,依然是采用哈希存储,然后将这个大的哈希分成若干个小的文件,分别统计每一块里面的元素出现的个数。但是这里需要明确一下这个空间占用是多少,才能进行相应的分片。

http://www.ritt.cn/news/22454.html

相关文章:

  • 公司做网站服务费怎样做账总裁班课程培训
  • 成都学网站建设广东seo价格是多少钱
  • 怎么做弹幕小视频网站怎么找到当地的微信推广
  • 西安城乡住房建设厅网站首页百度竞价调价软件
  • 厦门网站建设 金猪外链网站是什么
  • 哪些企业网站做的比较好黄冈网站推广优化找哪家
  • 四川网站建设免费咨询百度app浏览器下载
  • 自己在线房屋设计免费seo工资一般多少
  • 新网站怎么快速收录友情链接检测结果
  • 商城网站开发制作百度关键词价格排行榜
  • wordpress自定义的注册seo顾问是什么
  • 在线建网站谷歌seo是什么职业
  • 网站开发难点珠海seo推广
  • 实验方案设计怎么写网站关键词优化排名推荐
  • 自己建设网站需要审核吗原创软文
  • wordpress免插件cdn加速seo专家是什么意思
  • 佛山品牌网站建设怎样建立自己的网站平台
  • 转运网站建设青岛网站制作推广
  • 重庆网站建设公司有哪些百度问答兼职怎么做
  • wordpress微信公众号登录界面seo公司多少钱
  • 做鞋子的招聘网站有哪些seo优化网页
  • 服装网站建设教程山东疫情最新消息
  • 软件著作权申请流程及费用seo关键词排名优化手机
  • 专业的网站建设企业微信营销软件有哪些
  • 网站制作免费软件搜索推广平台
  • 合肥网站建设电话宣传推广渠道有哪些
  • 成人高考考试科目徐州关键词优化排名
  • 网站建设执行力免费网站统计代码
  • php做网站为什么比java快网站营销与推广
  • 六安网站建设电话竞价排名点击