课程咨询: 400-996-5531 / 投诉建议: 400-111-8989
认识达内从这里开始
认真做教育 专心促就业
青岛达内的小编总结，5亿个int找它们的中位数
思路一
将int划分为2^16个区域
读取数据，统计落到各个区域里的数的个数
根据统计结果判断中位数落到哪个区域，同时知道这个区域中的第几大数刚好是中位数
第二次扫描，只统计落在这个区域中的那些数即可
实际上，如果是long,我们可以经过3次这样的划分即可降低到可以接受的程度
即可以先将long分成224个区域，然后确定区域的第几大数，在将该区域分成220个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。
思路二
同样需要做两遍统计，如果数据存在硬盘上，就需要读取2次
方法同基排，开一个大小为65536的Int数组，第一遍读取，统计Int的高16位，也就是
0-65535,都算作0
Int除以 65536的结果不会超过65536种情况，因此开一个长度为65536的数组计数即可
每读取一个数，数组中对应计数+1,考虑有负数的情况，需要将结果加32768（因为只用一半）后，记录在相应的数组内。
第一遍统计之后，遍历数组累加，看中位数处于哪个区间
比如处于区间k,那么0~k-1内数字的数量sum应该<n/2（2.5亿）
而k+1 ~ 65535的计数和也<n/2
第二遍统计同上面方法，但这次只统计处于区间k的情况，也就是说（x / 65536） + 32768 = k.统计只统计低16位的情况。并且利用刚才统计的sum,比如sum = 2.49亿，那么现在就是要在低16位里面找100万个数（2.5亿-2.49亿）。这次计数之后，再统计一下，看中位数所处的区间，最后将高位和低位组合一下就是结果
秘技三：Bloom filter/Bitmap
Bloom filter
适用范围
可以用来实现数据字典，数据判重，集合求交集
基本原理及要点
对于原理来说很简单，位数组+k个独立hash函数。
将Hash函数对应的值的位数组置1,查找时如果发现所有Hash函数对应位都是1说明存在
很明显这个过程并不保证查找的结果100%正确的。
同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。
所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组，就可以支持删除了
以上就是青岛达内给大家做的内容详解，更多关于UI的学习，请继续关注青岛达内
思路一
将int划分为2^16个区域
读取数据，统计落到各个区域里的数的个数
根据统计结果判断中位数落到哪个区域，同时知道这个区域中的第几大数刚好是中位数
第二次扫描，只统计落在这个区域中的那些数即可
实际上，如果是long,我们可以经过3次这样的划分即可降低到可以接受的程度
即可以先将long分成224个区域，然后确定区域的第几大数，在将该区域分成220个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。
思路二
同样需要做两遍统计，如果数据存在硬盘上，就需要读取2次
方法同基排，开一个大小为65536的Int数组，第一遍读取，统计Int的高16位，也就是
0-65535,都算作0
65536 - 131071都算作1
Int除以 65536的结果不会超过65536种情况，因此开一个长度为65536的数组计数即可
每读取一个数，数组中对应计数+1,考虑有负数的情况，需要将结果加32768（因为只用一半）后，记录在相应的数组内。
第一遍统计之后，遍历数组累加，看中位数处于哪个区间
比如处于区间k,那么0~k-1内数字的数量sum应该<n/2（2.5亿）
而k+1 ~ 65535的计数和也<n/2
第二遍统计同上面方法，但这次只统计处于区间k的情况，也就是说（x / 65536） + 32768 = k.统计只统计低16位的情况。并且利用刚才统计的sum,比如sum = 2.49亿，那么现在就是要在低16位里面找100万个数（2.5亿-2.49亿）。这次计数之后，再统计一下，看中位数所处的区间，最后将高位和低位组合一下就是结果
秘技三：Bloom filter/Bitmap
Bloom filter
适用范围
可以用来实现数据字典，数据判重，集合求交集
基本原理及要点
对于原理来说很简单，位数组+k个独立hash函数。
将Hash函数对应的值的位数组置1,查找时如果发现所有Hash函数对应位都是1说明存在
很明显这个过程并不保证查找的结果100%正确的。
同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。
所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组，就可以支持删除了
以上就是青岛达内给大家做的内容详解，更多关于UI的学习，请继续关注青岛达内
< 上一篇：如何高效的处理亿万级数据？（10）
下一篇：如何高效的处理亿万级数据？（12） >
2025-02-12
免费试听课程
- 全部课程
- IT课程
- 设计课程
- 运营课程
4578
最新开班时间
- 北京
- 上海
- 广州
- 深圳
- 南京
- 成都
- 武汉
- 西安
- 青岛
- 天津
- 杭州
- 重庆
- 哈尔滨
- 济南
- 沈阳
- 合肥
- 郑州
- 长春
- 苏州
- 长沙
- 昆明
- 太原
- 无锡
- 石家庄
- 南宁
- 佛山
- 珠海
- 宁波
- 保定
- 呼和浩特
- 洛阳
- 烟台
- 运城
- 潍坊
- 开课名称
- 开班时间
- 抢座
- 咨询
- 开课名称
- 开班时间
- 抢座
- 咨询
-
- Java全链路开发
- 5月29日
- 火热抢座中
- 立即咨询
- 云计算全栈开发
- 5月29日
- 火热抢座中
- 立即咨询
-
- 网络安全工程师
- 5月29日
- 火热抢座中
- 立即咨询
- 人工智能工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- 数据分析与商业智能
- 5月29日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 5月29日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 5月29日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 5月29日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 5月29日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 5月29日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 5月29日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 5月29日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 5月29日
- 火热抢座中
- 立即咨询
-
- Java全链路开发
- 5月29日
- 火热抢座中
- 立即咨询
- 云计算全栈开发
- 5月29日
- 火热抢座中
- 立即咨询
-
- 网络安全工程师
- 5月29日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 5月29日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 5月29日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 5月29日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 5月29日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 5月29日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 5月29日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 5月29日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 5月29日
- 火热抢座中
- 立即咨询
-
- 云计算全栈开发
- 5月29日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- C++物联网工程师
- 5月29日
- 火热抢座中
- 立即咨询
- Web全栈开发
- 5月29日
- 火热抢座中
- 立即咨询
-
- 软件测试工程师
- 5月29日
- 火热抢座中
- 立即咨询
- AI大模型全栈工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- 鸿蒙原生应用开发
- 5月29日
- 火热抢座中
- 立即咨询
- 智能职场办公
- 5月29日
- 火热抢座中
- 立即咨询
-
- VFX商业视效设计
- 5月29日
- 火热抢座中
- 立即咨询
- AGI商业设计变现
- 5月29日
- 火热抢座中
- 立即咨询
-
- UID全链路设计
- 5月29日
- 火热抢座中
- 立即咨询
- 新媒体电商运营
- 5月29日
- 火热抢座中
- 立即咨询
-
- Java全链路开发
- 5月29日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- 数据分析与商业智能
- 5月29日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 5月29日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 5月29日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 5月29日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 5月29日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 5月29日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 5月29日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 5月29日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 5月29日
- 火热抢座中
- 立即咨询
-
- 云计算全栈开发
- 5月29日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- C++物联网工程师
- 5月29日
- 火热抢座中
- 立即咨询
- Web全栈开发
- 5月29日
- 火热抢座中
- 立即咨询
-
- 软件测试工程师
- 5月29日
- 火热抢座中
- 立即咨询
- AI大模型全栈工程师
- 5月29日
- 火热抢座中
- 立即咨询
-
- 鸿蒙原生应用开发
- 5月29日
- 火热抢座中
- 立即咨询
- 智能职场办公
- 5月29日
- 火热抢座中
- 立即咨询
-
- VFX商业视效设计
- 5月29日
- 火热抢座中
- 立即咨询
- AGI商业设计变现
- 5月29日
- 火热抢座中
- 立即咨询
-
- UID全链路设计
- 5月29日
- 火热抢座中
- 立即咨询
- 新媒体电商运营
- 5月29日
- 火热抢座中
- 立即咨询
预约申请试听课
400-111-8989
lihm@tedu.cn
