抖音二面,内存只有 2G,如何对 100 亿数据进行排序?

沙海 2022年6月15日10:05:07Java评论17字数 1844阅读6分8秒阅读模式
摘要

智能摘要

速蛙云 - 极致体验,强烈推荐!!!

智能摘要文章源自JAVA秀-https://www.javaxiu.com/66593.html

亿个int型数字大概占37个G,2G内存显然一次性是装不下的。最常见的思路,拆分成一个一个的小文件来处理呗,最终再合并成一个排好序的大文件。文章源自JAVA秀-https://www.javaxiu.com/66593.html

原文约 2081 | 图片 14 | 建议阅读 5 分钟 | 评价反馈文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?

小黑格子屋 文章源自JAVA秀-https://www.javaxiu.com/66593.html

以下文章来源于飞天小牛肉,作者小牛肉文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

飞天小牛肉.文章源自JAVA秀-https://www.javaxiu.com/66593.html

一个愤青程序员文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

来源:飞天小牛肉文章源自JAVA秀-https://www.javaxiu.com/66593.html

作者:小牛肉文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

大数据小内存排序问题,很经典,很常见,类似的还有比如 “如何对上百万考试的成绩进行排序” 等等文章源自JAVA秀-https://www.javaxiu.com/66593.html

大概有这么三种方法:文章源自JAVA秀-https://www.javaxiu.com/66593.html

  • 数据库排序(对数据库设备要求较高)文章源自JAVA秀-https://www.javaxiu.com/66593.html

  • 分治法(常见思路)文章源自JAVA秀-https://www.javaxiu.com/66593.html

  • 位图法(Bitmap)文章源自JAVA秀-https://www.javaxiu.com/66593.html

1. 数据库排序

将存储着 100 亿数据的文本文件一条一条导入到数据库中,然后根据某个字段建立索引,数据库进行索引排序操作后我们就可以依次提取出数据追加到结果集中。文章源自JAVA秀-https://www.javaxiu.com/66593.html

这种方法的特点就是操作简单, 运算速度较慢,对数据库设备要求较高文章源自JAVA秀-https://www.javaxiu.com/66593.html

2. 分治法

假设 100 亿个数据都是 int 类型的数字文章源自JAVA秀-https://www.javaxiu.com/66593.html

1 个 int 类型占 4 个字节(byte,B)文章源自JAVA秀-https://www.javaxiu.com/66593.html

1 B = 8 位(bit)文章源自JAVA秀-https://www.javaxiu.com/66593.html

1024 B(1024 B = 1KB) = 8 * 1024 bit文章源自JAVA秀-https://www.javaxiu.com/66593.html

1024 * 1024 KB(1024KB = 1MB)= 1024 * 8  * 1024 bit文章源自JAVA秀-https://www.javaxiu.com/66593.html

100 亿 int 型数字就是 100 亿 x 4B = 400 亿 B = 38146.97265625 MB 约等于 37.25GB文章源自JAVA秀-https://www.javaxiu.com/66593.html

100 亿个 int 型数字大概占 37 个 G,2G 内存显然一次性是装不下的。文章源自JAVA秀-https://www.javaxiu.com/66593.html

最常见的思路,拆分成一个一个的小文件来处理呗,最终再合并成一个排好序的大文件。文章源自JAVA秀-https://www.javaxiu.com/66593.html

典型的分治法文章源自JAVA秀-https://www.javaxiu.com/66593.html

1)把这个 37 GB 的大文件,用哈希或者直接平均分成若个小文件(比如 1000 个,每个小文件平均 38 MB 左右)文章源自JAVA秀-https://www.javaxiu.com/66593.html

2)拆分完了之后,得到 1000 个 30 多 MB 的小文件,那么就可以放进内存里排序了,可以用快速排序,归并排序,堆排序等等文章源自JAVA秀-https://www.javaxiu.com/66593.html

3)1000 个小文件内部排好序之后,就要把这些内部有序的小文件,合并成一个大的文件,可以用堆排序来做 1000 路合并的操作(假设是从小到大排序,用小顶堆):文章源自JAVA秀-https://www.javaxiu.com/66593.html

  • 首先遍历 1000 个文件,每个文件里面取第一个数字,组成 (数字, 文件号) 这样的组合加入到堆里,遍历完后堆里有 1000 个 (数字,文件号) 这样的元素文章源自JAVA秀-https://www.javaxiu.com/66593.html

  • 然后不断从堆顶 pop 元素追加到结果集,每 pop 一个元素,就根据它的文件号去对应的文件里,补虫一个元素进入堆中,直到那个文件中的元素被拿完文章源自JAVA秀-https://www.javaxiu.com/66593.html

  • 按照上面的操作,直到堆被取空了,此时最终结果文件里的全部数字就是有序的了文章源自JAVA秀-https://www.javaxiu.com/66593.html

3. 位图法(Bitmap)

位图法的基本思想就是利用一位(bit)代表一个数字,例如第 3 位上为 1,则说明 3 这个数字出现过,若为0,则说明 3 这个数字没有出现过。很简单~文章源自JAVA秀-https://www.javaxiu.com/66593.html

上面分析过,1M = 8388608 bit(800 多万)文章源自JAVA秀-https://www.javaxiu.com/66593.html

也就是说,通过位图法,只需要 1M 的空间,我们就可以处理 800 多万级别的数据文章源自JAVA秀-https://www.javaxiu.com/66593.html

Java 中没有 bit 这样的基本数据类型,最小数据类型是 byte,我们可以用 byte 数组来实现这个位图法文章源自JAVA秀-https://www.javaxiu.com/66593.html

byte 数组上的每一个元素都是 byte 类型,一个 byte 等于 8 个 bit,我们可以把 10 进制的 byte 用二进制的 bit 来表示,如下图:文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

这样,byte 数组中的一个元素就能表示 8 个数字是否出现过,比如 byte[0] 可以表示 0 ~ 7 是否出现过,byte[1] 可以表示 8 ~ 15 是否出现过.....文章源自JAVA秀-https://www.javaxiu.com/66593.html

全部处理完之后,我们从前往后遍历一遍 byte 数组就能获取到有序数据了,时间复杂度为 O(N)文章源自JAVA秀-https://www.javaxiu.com/66593.html

java.util 封装了 BitSet 这样一个类,是位图法的典型实现文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

底层用的 long 数组,一个 long 型数据占 8 个字节(64 位,也就是说 long 数组中的一个元素就可以表示 64 个数字否出现过),占比与只占 1 个字节的 byte(8 位) 来说,能存储的数据更多了文章源自JAVA秀-https://www.javaxiu.com/66593.html

BitSet bitSet = new BitSet();bitSet.set(0, 2, true);

上面的代码的含义是,第 [0,2) 位会被设置成 1,也就是说这个类会自动地生成一个 long 型的元素,二进制表示是 .....(省略 60 个 0) 0011,十进制表示就是 3文章源自JAVA秀-https://www.javaxiu.com/66593.html

位图法的缺点:文章源自JAVA秀-https://www.javaxiu.com/66593.html

  • 可读性差(不是一般的差 ?)文章源自JAVA秀-https://www.javaxiu.com/66593.html

  • 位图存储的元素个数虽然比一般做法多,但是存储的元素大小受限于存储空间的大小。要想定义存储空间大小就需要实现知道存储的元素到底有多少文章源自JAVA秀-https://www.javaxiu.com/66593.html

  • 对于有符号类型的数据,需要用 2 位来表示,比如 第 0 位和第 1 位表示 0 这个数据,第 2 位和第 3 位表示 1 这个数据......,这会让位图能存储的元素个数,元素值大小上限减半文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

 文章源自JAVA秀-https://www.javaxiu.com/66593.html

-End-

文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序? 可乐记得加冰,爱我就要置顶 抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

抖音二面,内存只有 2G,如何对 100 亿数据进行排序?素质三连biubiubiu~抖音二面,内存只有 2G,如何对 100 亿数据进行排序?文章源自JAVA秀-https://www.javaxiu.com/66593.html

继续阅读
文章末尾固定信息...
weinxin
资源分享QQ群
本站是JAVA秀团队的技术分享社区, 会经常分享资源和教程; 分享的时代, 请别再沉默!
沙海
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定