자바 5 억 정수 큰 파일 정렬 방법

문제.
파일 1 개 를 드 리 겠 습 니 다bigdata크기 4663 M,5 억 개,파일 의 데 이 터 는 무 작위 입 니 다.다음 줄 의 정수 입 니 다.
6196302
3557681
6121580
2039345
2095006
1746773
7934312
2016371
7123302
8790171
2966901
...
7005375
지금 이 파일 을 정렬 하려 고 하 는데 어떻게 합 니까?
내부 정렬
먼저 내 열 을 시도 하고 두 가지 정렬 방식 을 선택 하 십시오.
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큰 파일 이 처 리 될 때 까지 n 개의 질서정연 한 디스크 파일 을 반복 적 으로 이용 합 니 다.

2.합
현재 n 개의 질서 있 는 작은 파일 이 있 는데 어떻게 질서 있 는 큰 파일 로 합 칩 니까?
모든 작은 파일 을 메모리 에 읽 고 내 열 합 니까?
(⊙o⊙)…
no!
다음 과 같은 원 리 를 이용 하여 정렬 합 니 다.
 
우 리 는 간단 한 예 를 들 었 다.
파일 1:3,6,9
파일 2:2,4,8
문건 3:1,5,7
1 라운드:
파일 1 의 최소 값:3,파일 1 의 첫 번 째 줄 에 있 습 니 다.
파일 2 의 최소 값:2,파일 2 의 첫 번 째 줄 에 있 습 니 다.
파일 3 의 최소 값:1,파일 3 의 첫 번 째 줄 에 있 습 니 다.
그러면 이 세 파일 중 가장 작은 값 은 min(1,2,3)=1 입 니 다.
즉,최종 큰 파일 의 현재 최소 값 은 파일 1,2,3 의 현재 최소 값 의 최소 값 입 니 다.돌아 갑 니까?
위 에서 최소 값 1 을 꺼 내 큰 파일 에 썼 습 니 다.
2 라운드:
파일 1 의 최소 값:3,파일 1 의 첫 번 째 줄 에 있 습 니 다.
파일 2 의 최소 값:2,파일 2 의 첫 번 째 줄 에 있 습 니 다.
파일 3 의 최소 값:5,파일 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
...
자바 5 억 정수 대 파일 을 어떻게 정렬 하 는 지 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 대 파일 정렬 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!