作者：清雅竹gf_644 | 来源：互联网 | 2023-10-11 14:02
一、需求
有1个大文件包含5亿个数&＃xff08;文件大小好几个G&＃xff09;&＃xff0c;其中每一行都是一个随机整数&＃xff08;不重复&＃xff09;&＃xff0c;现在要对这个文件进行排序。
二、实现
2.1 位图法
核心思想是&＃xff0c;创建一个拥有5亿bits的BitSet&＃xff08;位图&＃xff09;&＃xff0c;BitSet每一位初始时都为false。然后读取包含正整数的文件&＃xff0c;对于每一个数i&＃xff0c;将bitSet[i]设置为true。最后遍历位图&＃xff0c;如果bitSet[j]为true&＃xff0c;那么输出 j。
采用位图法&＃xff0c;也可以判断某个给定的数是否在大文件中&＃xff0c;只需要判断bitSet的指定位是否为true即可。
下面是我写的一个简单的demo&＃xff0c;用于对文件中的数字排序&＃xff1a;
data.txt内容如下&＃xff1a;
代码如下&＃xff1a;
public static void main(String[] args) {BitSet bitSet &＃61; new BitSet(100);try (BufferedReader br &＃61; new BufferedReader(new FileReader("F:\\data.txt"))) {String line &＃61; null;while ((line &＃61; br.readLine()) !&＃61; null) {int value &＃61; Integer.valueOf(line);bitSet.set(value);}} catch (Exception e) {e.printStackTrace();}for (int i &＃61; 0; i 结果如下&＃xff1a;
1
7
9
12
32
43
87
765
32543
2.2 外部排序
在内存极小的情况下&＃xff0c;采用分治策略&＃xff0c;利用外存保存中间结果&＃xff0c;再用多路归并来排序。
map-reduce思想&＃xff1a;
内存中维护一个极小的缓冲区buffer&＃xff0c;将大文件bigdata按行读入&＃xff0c;直到buffer满或者大文件读完时&＃xff0c;对buffer中的数据调用内排进行排序&＃xff0c;排序后将有序结果写入磁盘临时文件bigdata.xxx.part.sorted&＃xff0c;循环利用buffer直到大文件处理完毕&＃xff0c;得到n个有序的临时文件。
接下来&＃xff0c;对n个有序的临时文件进行归并排序&＃xff0c;方法如下&＃xff1a;假如有三个临时文件&＃xff0c;其中文件1&＃xff1a;3,6,9&＃xff0c;文件2&＃xff1a;2,4,8&＃xff0c;文件3&＃xff1a;1,5,7。
第一回合&＃xff1a;文件1的最小值&＃xff1a;3 , 排在文件1的第1行&＃xff0c;文件2的最小值&＃xff1a;2&＃xff0c;排在文件2的第1行&＃xff0c;文件3的最小值&＃xff1a;1&＃xff0c;排在文件3的第1行 那么&＃xff0c;这3个文件中的最小值是&＃xff1a;min(1,2,3) &＃61;1。也就是说&＃xff0c;最终大文件的当前最小值&＃xff0c;是文件1、2、3的当前最小值的最小值。上面拿出了最小值1&＃xff0c;写入大文件。
第二回合&＃xff1a;文件1的最小值&＃xff1a;3&＃xff0c;排在文件1的第1行&＃xff0c;文件2的最小值&＃xff1a;2&＃xff0c;排在文件2的第1行&＃xff0c;文件3的最小值&＃xff1a;5&＃xff0c;排在文件3的第2行。那么&＃xff0c;这3个文件中的最小值是&＃xff1a;min(5,2,3) &＃61; 2&＃xff0c;将2写入大文件。
接下来&＃xff0c;重复上述操作&＃xff0c;直到所有小文件的内容都写到了大文件。
参考&＃xff1a;
https://blog.csdn.net/zxx901221/article/details/83028481
https://mp.weixin.qq.com/s?__biz&＃61;MzUzMTA2NTU2Ng&＃61;&＃61;&mid&＃61;2247488950&idx&＃61;2&sn&＃61;a3f4a09acd07638055c803338c15e29e&chksm&＃61;fa496a07cd3ee3117a27f17818ddc4152a817b50961780ae65ce3ac545303092221b08778e16&mpshare&＃61;1&scene&＃61;1&srcid&＃61;&sharer_sharetime&＃61;1582344585643&sharer_shareid&＃61;cfcd208495d565ef66e7dff9f98764da&key&＃61;56dae8b8a643d0f33cf6fdae6748f10f94d93459951fc0f564b244e54c6e8de6cce77ff794210f989a83231ae733a61f773233f7a4f5cbe90fac0ba3b3f194898dacea95b4b6667befc1c49ea94fd347&ascene&＃61;1&uin&＃61;MjI5NzkwNjI0Mg%3D%3D&devicetype&＃61;Windows&＃43;10&version&＃61;62070158&lang&＃61;zh_CN&exportkey&＃61;A9Ay4nz6HZO2bU0iugefePI%3D&pass_ticket&＃61;FW9GJdVHO2LjxiXcRXeofaBYJdcXuPY6k3di%2BzwOyVBLknE63w20ogQQfIUitcCY
京公网安备 11010802041100号