Java 5亿整数大文件怎么排序

问题

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

6196302  3557681  6121580  2039345  2095006  1746773  7934312  2016371  7123302  8790171  2966901  ...  7005375

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

内部排序

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

3路快排:

private final int cutoff = 8;

public <T> void perform(Comparable<T>[] a) {
    perform(a,0,a.length - 1);
  }

  private <T> int median3(Comparable<T>[] a,int x,int y,int z) {
    if(lessThan(a[x],a[y])) {
      if(lessThan(a[y],a[z])) {
        return y;
      }
      else if(lessThan(a[x],a[z])) {
        return z;
      }else {
        return x;
      }
    }else {
      if(lessThan(a[z],a[y])){
        return y;
      }else if(lessThan(a[z],a[x])) {
        return z;
      }else {
        return x;
      }
    }
  }

  private <T> void perform(Comparable<T>[] a,int low,int high) {
    int n = high - low + 1;
    //当序列非常小,用插入排序
    if(n <= cutoff) {
      InsertionSort insertionSort = SortFactory.createInsertionSort();
      insertionSort.perform(a,low,high);
      //当序列中小时,使用median3
    }else if(n <= 100) {
      int m = median3(a,low,low + (n >>> 1),high);
      exchange(a,m,low);
      //当序列比较大时,使用ninther
    }else {
      int gap = n >>> 3;
      int m = low + (n >>> 1);
      int m1 = median3(a,low,low + gap,low + (gap << 1));
      int m2 = median3(a,m - gap,m,m + gap);
      int m3 = median3(a,high - (gap << 1),high - gap,high);
      int ninther = median3(a,m1,m2,m3);
      exchange(a,ninther,low);
    }

    if(high <= low)
      return;
    //lessThan
    int lt = low;
    //greaterThan
    int gt = high;
    //中心点
    Comparable<T> pivot = a[low];
    int i = low + 1;

    /*
    * 不变式:
    *  a[low..lt-1] 小于pivot -> 前部(first)
    *  a[lt..i-1] 等于 pivot -> 中部(middle)
    *  a[gt+1..n-1] 大于 pivot -> 后部(final)
    *
    *  a[i..gt] 待考察区域
    */

    while (i <= gt) {
      if(lessThan(a[i],pivot)) {
        //i-> ,lt ->
        exchange(a,lt++,i++);
      }else if(lessThan(pivot,a[i])) {
        exchange(a,i,gt--);
      }else{
        i++;
      }
    }

    // a[low..lt-1] < v = a[lt..gt] < a[gt+1..high].
    perform(a,low,lt - 1);
    perform(a,gt + 1,high);
  }

归并排序:

/**
   * 小于等于这个值的时候,交给插入排序
   */
  private final int cutoff = 8;

  /**
   * 对给定的元素序列进行排序
   *
   * @param a 给定元素序列
   */
  @Override
  public <T> void perform(Comparable<T>[] a) {
    Comparable<T>[] b = a.clone();
    perform(b, a, 0, a.length - 1);
  }

  private <T> void perform(Comparable<T>[] src,Comparable<T>[] dest,int low,int high) {
    if(low >= high)
      return;

    //小于等于cutoff的时候,交给插入排序
    if(high - low <= cutoff) {
      SortFactory.createInsertionSort().perform(dest,low,high);
      return;
    }

    int mid = low + ((high - low) >>> 1);
    perform(dest,src,low,mid);
    perform(dest,src,mid + 1,high);

    //考虑局部有序 src[mid] <= src[mid+1]
    if(lessThanOrEqual(src[mid],src[mid+1])) {
      System.arraycopy(src,low,dest,low,high - low + 1);
    }

    //src[low .. mid] + src[mid+1 .. high] -> dest[low .. high]
    merge(src,dest,low,mid,high);
  }

  private <T> void merge(Comparable<T>[] src,Comparable<T>[] dest,int low,int mid,int high) {

    for(int i = low,v = low,w = mid + 1; i <= high; i++) {
      if(w > high || v <= mid && lessThanOrEqual(src[v],src[w])) {
        dest[i] = src[v++];
      }else {
        dest[i] = src[w++];
      }
    }
  }

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

数据太多,数组太长 -> OOM?加大Xmx?

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

sort命令来跑

sort -n bigdata -o bigdata.sorted

跑了多久呢?24分钟.

为什么这么慢?

粗略的看下我们的资源:

1. 内存

jvm-heap/stack,native-heap/stack,page-cache,block-buffer

2. 外存

swap + 磁盘

数据量很大,函数调用很多,系统调用很多,内核/用户缓冲区拷贝很多,脏页回写很多,io-wait很高,io很繁忙,堆栈数据不断交换至swap,线程切换很多,每个环节的也很多.

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

位图法

private BitSet bits;

  public void perform(
      String largeFileName,
      int total,
      String destLargeFileName,
      Castor<Integer> castor,
      int readerBufferSize,
      int writerBufferSize,
      boolean asc) throws IOException {

    System.out.println("BitmapSort Started.");
    long start = System.currentTimeMillis();
    bits = new BitSet(total);
    InputPart<Integer> largeIn = PartFactory.createCharBufferedInputPart(largeFileName, readerBufferSize);
    OutputPart<Integer> largeOut = PartFactory.createCharBufferedOutputPart(destLargeFileName, writerBufferSize);
    largeOut.delete();

    Integer data;
    int off = 0;
    try {
      while (true) {
        data = largeIn.read();
        if (data == null)
          break;
        int v = data;
        set(v);
        off++;
      }
      largeIn.close();
      int size = bits.size();
      System.out.println(String.format("lines : %d ,bits : %d", off, size));

      if(asc) {
        for (int i = 0; i < size; i++) {
          if (get(i)) {
            largeOut.write(i);
          }
        }
      }else {
        for (int i = size - 1; i >= 0; i--) {
          if (get(i)) {
            largeOut.write(i);
          }
        }
      }

      largeOut.close();
      long stop = System.currentTimeMillis();
      long elapsed = stop - start;
      System.out.println(String.format("BitmapSort Completed.elapsed : %dms",elapsed));
    }finally {
      largeIn.close();
      largeOut.close();
    }
  }

  private void set(int i) {
    bits.set(i);
  }

  private boolean get(int v) {
    return bits.get(v);
  }

nice!跑了190秒,3分来钟.

以核心内存 4663M/32 大小的空间跑出这么个结果,而且大量时间在用于I/O,不错.

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

外部排序

该外部排序上场了.

外部排序干嘛的?

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

1.分

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

循环利用 memBuffer 直到大文件处理完毕,得到n个有序的磁盘文件:

2.合

现在有了n个有序的小文件,怎么合并成1个有序的大文件?

把所有小文件读入内存,然后内排?

(⊙o⊙)…

no!

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

我们举个简单的例子:

文件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分钟左右.

less bigdata.sorted.text  ...  9999966  9999967  9999968  9999969  9999970  9999971  9999972  9999973  9999974  9999975  9999976  9999977  9999978  ...

到此这篇关于Java 5亿整数大文件怎么排序的文章就介绍到这了,更多相关Java 大文件排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间:2020-03-24

Java的二叉树排序以及遍历文件展示文本格式的文件树

Java二叉树排序算法 排序二叉树的描述也是一个递归的描述, 所以排序二叉树的构造自然也用递归的: 排序二叉树的3个特征: 1:当前node的所有左孩子的值都小于当前node的值: 2:当前node的所有右孩子的值都大于当前node的值: 3:孩子节点也满足以上两点 package test.sort; public class BinaryNode { private int value;//current value private BinaryNode lChild;//left chil

java实现二叉树的创建及5种遍历方法(总结)

用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方式: package myTest; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; public class myClass { public static void main(

Java遍历输出指定目录、树形结构所有文件包括子目录下的文件

Java 5亿整数大文件怎么排序

下面通过一段代码介绍下Java输出指定目录.树形结构下的所有文件包括子目录中的文件的方法,并附有效果图. import java.io.File; public class ReadDirectory { // 文件所在的层数 private int fileLevel; /** * 生成输出格式 * @param name 输出的文件名或目录名 * @param level 输出的文件名或者目录名所在的层次 * @return 输出的字符串 */ public String createPri

JAVA实现遍历文件夹下的所有文件(递归调用和非递归调用)

JAVA 遍历文件夹下的所有文件(递归调用和非递归调用) 1.不使用递归的方法调用. public void traverseFolder1(String path) { int fileNum = 0, folderNum = 0; File file = new File(path); if (file.exists()) { LinkedList<File> list = new LinkedList<File>(); File[] files = file.listFile

java 实现计数排序和桶排序实例代码

java 实现计数排序和桶排序实例代码 目录 比较和非比较的区别 常见的快速排序.归并排序.堆排序.冒泡排序等属于比较排序.在排序的最终结果里,元素之间的次序依赖于它们之间的比较.每个数都必须和其他数进行比较,才能确定自己的位置. 在 冒泡排序 之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²).在 归并排序.快速排序 之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均 O(nlogn) . 比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布

浅谈java指令重排序的问题

指令重排序是个比较复杂.觉得有些不可思议的问题,同样是先以例子开头(建议大家跑下例子,这是实实在在可以重现的,重排序的概率还是挺高的),有个感性的认识 /** * 一个简单的展示Happen-Before的例子. * 这里有两个共享变量:a和flag,初始值分别为0和false.在ThreadA中先给 a=1,然后flag=true. * 如果按照有序的话,那么在ThreadB中如果if(flag)成功的话,则应该a=1,而a=a*1之后a仍然为1,下方的if(a==0)应该永远不会为 * 真,

JAVA 实现二叉树(链式存储结构)

Java 5亿整数大文件怎么排序

二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

python实现的二叉树定义与遍历算法实例

Java 5亿整数大文件怎么排序

本文实例讲述了python实现的二叉树定义与遍历算法.分享给大家供大家参考,具体如下: 初学python,需要实现一个决策树,首先实践一下利用python实现一个二叉树数据结构.建树的时候做了处理,保证建立的二叉树是平衡二叉树. # -*- coding: utf-8 -*- from collections import deque class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=l

详解Java读取本地文件并显示在JSP文件中

详解Java读取本地文件并显示在JSP文件中 当我们初学IMG标签时,我们知道通过设置img标签的src属性,能够在页面中显示想要展示的图片.其中src的值,可以是磁盘目录上的绝对,也可以是项目下的相对路径,还可以是网络上的图片路径.在存取少量图片的情况下,采用相对路径存储图片的情况下最方便,也最实用.但是当图片数量过多时,这种方式就显的有些掣肘了. 当系统的图片数量过多时,如果仍把这些图片当做项目的一部分去发布,势必会大大延长项目的发布时间及更新时间.对于某些对于时限性要求特别高的系统来说,采

Java将文件分割为多个子文件再将子文件合并成原始文件的示例

Java将文件分割为多个子文件再将子文件合并成原始文件的示例,废话不多说,代码如下: import java.io.File; import java.io.InputStream; import java.io.FileInputStream; import java.io.OutputStream; import java.io.FileOutputStream; import java.util.Properties; import java.util.Iterator; import j

原文 

https://www.zhangshengrong.com/p/Mr1WJxQ0XG/

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Java 5亿整数大文件怎么排序

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址