开工面试题热个身:5 亿整数的大文件,来排个序 ?

2019 Java 开发者跳槽指南.pdf (吐血整理)….>>>

点击上方“后端技术精选”,选择“置顶公众号”

技术文章第一时间送达!

作者:xupengzhang

http://www.importnew.com/23450.html

一、问题

给你1个文件bigdata,大小4663M,5亿个数,文件中的数据随机,如下一行一个整数:

开工面试题热个身:5 亿整数的大文件,来排个序 ?

现在要对这个文件进行排序,怎么搞?

二、内部排序

先尝试内排,选2种排序方式:

  1. private final int cutoff = 8;


  2. public void perform(Comparable[] a) {

  3. perform(a,0,a.length - 1);

  4. }


  5. private int median3(Comparable[] a,int x,int y,int z) {

  6. if(lessThan(a[x],a[y])) {

  7. if(lessThan(a[y],a[z])) {

  8. return y;

  9. }

  10. else if(lessThan(a[x],a[z])) {

  11. return z;

  12. }else {

  13. return x;

  14. }

  15. }else {

  16. if(lessThan(a[z],a[y])){

  17. return y;

  18. }else if(lessThan(a[z],a[x])) {

  19. return z;

  20. }else {

  21. return x;

  22. }

  23. }

  24. }


  25. private void perform(Comparable[] a,int low,int high) {

  26. int n = high - low + 1;

  27. //当序列非常小,用插入排序

  28. if(n <= cutoff) {

  29. InsertionSort insertionSort = SortFactory.createInsertionSort();

  30. insertionSort.perform(a,low,high);

  31. //当序列中小时,使用median3

  32. }else if(n <= 100) {

  33. int m = median3(a,low,low + (n >>> 1),high);

  34. exchange(a,m,low);

  35. //当序列比较大时,使用ninther

  36. }else {

  37. int gap = n >>> 3;

  38. int m = low + (n >>> 1);

  39. int m1 = median3(a,low,low + gap,low + (gap << 1));

  40. int m2 = median3(a,m - gap,m,m + gap);

  41. int m3 = median3(a,high - (gap << 1),high - gap,high);

  42. int ninther = median3(a,m1,m2,m3);

  43. exchange(a,ninther,low);

  44. }


  45. if(high <= low)

  46. return;

  47. //lessThan

  48. int lt = low;

  49. //greaterThan

  50. int gt = high;

  51. //中心点

  52. Comparablepivot = a[low];

  53. int i = low + 1;


  54. /*

  55. * 不变式:

  56. * a[low..lt-1] 小于pivot -> 前部(first)

  57. * a[lt..i-1] 等于 pivot -> 中部(middle)

  58. * a[gt+1..n-1] 大于 pivot -> 后部(final)

  59. *

  60. * a[i..gt] 待考察区域

  61. */


  62. while (i <= gt) {

  63. if(lessThan(a[i],pivot)) {

  64. //i-> ,lt ->

  65. exchange(a,lt++,i++);

  66. }else if(lessThan(pivot,a[i])) {

  67. exchange(a,i,gt--);

  68. }else{

  69. i++;

  70. }

  71. }


  72. // a[low..lt-1] < v = a[lt..gt] < a[gt+1..high].

  73. perform(a,low,lt - 1);

  74. perform(a,gt + 1,high);

  75. }

三、归并排序:

  1. /**

  2. * 小于等于这个值的时候,交给插入排序

  3. */

  4. private final int cutoff = 8;


  5. /**

  6. * 对给定的元素序列进行排序

  7. *

  8. * @param a 给定元素序列

  9. */

  10. @Override

  11. public void perform(Comparable[] a) {

  12. Comparable[] b = a.clone();

  13. perform(b, a, 0, a.length - 1);

  14. }


  15. private void perform(Comparable[] src,Comparable[] dest,int low,int high) {

  16. if(low >= high)

  17. return;


  18. //小于等于cutoff的时候,交给插入排序

  19. if(high - low <= cutoff) {

  20. SortFactory.createInsertionSort().perform(dest,low,high);

  21. return;

  22. }


  23. int mid = low + ((high - low) >>> 1);

  24. perform(dest,src,low,mid);

  25. perform(dest,src,mid + 1,high);


  26. //考虑局部有序 src[mid] <= src[mid+1]

  27. if(lessThanOrEqual(src[mid],src[mid+1])) {

  28. System.arraycopy(src,low,dest,low,high - low + 1);

  29. }


  30. //src[low .. mid] + src[mid+1 .. high] -> dest[low .. high]

  31. merge(src,dest,low,mid,high);

  32. }


  33. private void merge(Comparable[] src,Comparable[] dest,int low,int mid,int high) {


  34. for(int i = low,v = low,w = mid + 1; i <= high; i++) {

  35. if(w > high || v <= mid && lessThanOrEqual(src[v],src[w])) {

  36. dest[i] = src[v++];

  37. }else {

  38. dest[i] = src[w++];

  39. }

  40. }

  41. }


数据太多,递归太深 ->栈溢出?加大Xss?数据太多,数组太长 -> OOM?加大Xmx?


耐心不足,没跑出来.而且要将这么大的文件读入内存,在堆中维护这么大个数据量,还有内排中不断的拷贝,对栈和堆都是很大的压力,不具备通用性。

四、sort命令来跑

跑了多久呢?24分钟.

为什么这么慢?

粗略的看下我们的资源:

内存 jvm-heap/stack,native-heap/stack,page-cache,block-buffer 外存 swap + 磁盘 数据量很大,函数调用很多,系统调用很多,内核/用户缓冲区拷贝很多,脏页回写很多,io-wait很高,io很繁忙,堆栈数据不断交换至swap,线程切换很多,每个环节的锁也很多.

总之,内存吃紧,问磁盘要空间,脏数据持久化过多导致cache频繁失效,引发大量回写,回写线程高,导致cpu大量时间用于上下文切换,一切,都很糟糕,所以24分钟不细看了,无法忍受.

五、位图法

  1. private BitSet bits;


  2. public void perform(

  3. String largeFileName,

  4. int total,

  5. String destLargeFileName,

  6. Castor<Integer> castor,

  7. int readerBufferSize,

  8. int writerBufferSize,

  9. boolean asc) throws IOException {


  10. System.out.println("BitmapSort Started.");

  11. long start = System.currentTimeMillis();

  12. bits = new BitSet(total);

  13. InputPart<Integer> largeIn = PartFactory.createCharBufferedInputPart(largeFileName, readerBufferSize);

  14. OutputPart<Integer> largeOut = PartFactory.createCharBufferedOutputPart(destLargeFileName, writerBufferSize);

  15. largeOut.delete();


  16. Integer data;

  17. int off = 0;

  18. try {

  19. while (true) {

  20. data = largeIn.read();

  21. if (data == null)

  22. break;

  23. int v = data;

  24. set(v);

  25. off++;

  26. }

  27. largeIn.close();

  28. int size = bits.size();

  29. System.out.println(String.format("lines : %d ,bits : %d", off, size));


  30. if(asc) {

  31. for (int i = 0; i < size; i++) {

  32. if (get(i)) {

  33. largeOut.write(i);

  34. }

  35. }

  36. }else {

  37. for (int i = size - 1; i >= 0; i--) {

  38. if (get(i)) {

  39. largeOut.write(i);

  40. }

  41. }

  42. }


  43. largeOut.close();

  44. long stop = System.currentTimeMillis();

  45. long elapsed = stop - start;

  46. System.out.println(String.format("BitmapSort Completed.elapsed : %dms",elapsed));

  47. }finally {

  48. largeIn.close();

  49. largeOut.close();

  50. }

  51. }


  52. private void set(int i) {

  53. bits.set(i);

  54. }


  55. private boolean get(int v) {

  56. return bits.get(v);

  57. }

nice!跑了190秒,3分来钟. 以核心内存4663M/32大小的空间跑出这么个结果,而且大量时间在用于I/O,不错.

问题是,如果这个时候突然内存条坏了1、2根,或者只有极少的内存空间怎么搞?

六、外部排序

该外部排序上场了. 外部排序干嘛的?

内存极少的情况下,利用分治策略,利用外存保存中间结果,再用多路归并来排序;

map-reduce的嫡系.

开工面试题热个身:5 亿整数的大文件,来排个序 ?

开工面试题热个身:5 亿整数的大文件,来排个序 ?

1.分

内存中维护一个极小的核心缓冲区memBuffer,将大文件bigdata按行读入,搜集到memBuffer满或者大文件读完时,对memBuffer中的数据调用内排进行排序,排序后将有序结果写入磁盘文件bigdata.xxx.part.sorted. 循环利用memBuffer直到大文件处理完毕,得到n个有序的磁盘文件:

开工面试题热个身:5 亿整数的大文件,来排个序 ?

2.合

现在有了n个有序的小文件,怎么合并成1个有序的大文件?把所有小文件读入内存,然后内排?(⊙o⊙)… no!

利用如下原理进行归并排序:

开工面试题热个身:5 亿整数的大文件,来排个序 ?

我们举个简单的例子:

文件1:3,6,9 文件2:2,4,8 文件3:1,5,7

第一回合:文件1的最小值:3 , 排在文件1的第1行 文件2的最小值:2,排在文件2的第1行 文件3的最小值:1,排在文件3的第1行 那么,这3个文件中的最小值是:min(1,2,3) = 1 也就是说,最终大文件的当前最小值,是文件1、2、3的当前最小值的最小值,绕么?上面拿出了最小值1,写入大文件.

第二回合:文件1的最小值:3 , 排在文件1的第1行 文件2的最小值:2,排在文件2的第1行 文件3的最小值:5,排在文件3的第2行 那么,这3个文件中的最小值是:min(5,2,3) = 2 将2写入大文件.

也就是说,最小值属于哪个文件,那么就从哪个文件当中取下一行数据.(因为小文件内部有序,下一行数据代表了它当前的最小值)

最终的时间,跑了771秒,13分钟左右.

开工面试题热个身:5 亿整数的大文件,来排个序 ?


END

Java面试题专栏

【40期】说一下线程池内部工作原理
【39期】Mybatis面试18问,你想知道的都在这里了!
【38期】一份tcp、http面试指南,常考点都给你了
【37期】请你详细说说类加载流程,类加载机制及自定义类加载器
【36期】说说 如何停止一个正在运行的线程?
【35期】谈谈你对Java线程之间通信方式的理解
【34期】谈谈为什么要拆分数据库?有哪些方法?
【33期】分别谈谈联合索引生效和失效的条件
【32期】你知道Redis的字符串是怎么实现的吗?
【31期】了解什么是 redis 的雪崩、穿透和击穿?redis 崩溃之后会怎么样?应对措施是什么



开工面试题热个身:5 亿整数的大文件,来排个序 ?


欢迎长按下图关注公众号后端技术精选

开工面试题热个身:5 亿整数的大文件,来排个序 ?

原文始发于微信公众号(后端技术精选):开工面试题热个身:5 亿整数的大文件,来排个序 ?