빅 데이터 알고리즘: 5 억 데이터 정렬

선언:
  빅 데이터 연구 의 길에서 우 리 는 항상 큰 데이터 에 대해 여러 가지 조작 을 해 야 한다.예 를 들 어 데이터 정렬, 예 를 들 어 데이터 통계, 예 를 들 어 데이터 계산 등 이다.그러나 대량의 데이터 앞에서 우 리 는 항상 속수무책 이다. 왜냐하면 우 리 는 시간 을 제한 하 는 상황 에서 효율 적 으로 사람 을 만족 시 킬 수 없고 공간 을 제한 하 는 상황 에서 문 제 를 신속하게 해결 할 수 없 기 때문이다.아마도 우 리 는 일상적인 개발 과정 에서 이런 문제 들 을 만난 적 이 없 을 것 이다.하지만 이 제 는 이런 문 제 를 고려 해 볼 때 가 됐다.빅 데이터 시대 이기 때문이다.
  본 논문 에서 저 는 세 가지 방법 으로 5 억 데 이 터 를 어떻게 해결 하 는 지 두 가지 측면 에서 설명 하 겠 습 니 다.
본문 링크:http://blog.csdn.net/lemon_tree12138/article/details/48783535 -- 프로 그래 밍 생황
                                                                 --전재 출처 를 밝 혀 주 십시오
사고 분석:
  이런 질문 을 받 으 면 첫 느낌 이 어때요?거품 정렬?정렬 을 선택 하 시 겠 습 니까?정렬 삽입?쌓다아니면 빨리 줄 을 서 시 겠 습 니까?아마 너의 생각 은 나의 메모리 가 부족 하 다 는 것 일 것 이다.확실히 이렇게 큰 데 이 터 는 우리 의 메모리 가 확실히 부족 하 다.5 억 의 정수 데이터 만 3.7 개의 G 가 있 기 때문이다.메모리 가 부족 한 이상 우 리 는 어떻게 해결 해 야 합 니까?
  우리 가 한 걸음 에 할 수 없 는 일 을 알 아야 한다. 두 걸음 이면 항상 할 수 있다.그럼 첫 번 째 단 계 를 시도 해 보 겠 습 니 다. 나머지 는 잠시 후에 다시 해결 하 겠 습 니 다.이러한 사고방식 을 바탕 으로 다음 과 같은 문제 풀이 방법 이 있다. 바로 분 치!
1. 분할 - 데이터 에 존재 하 는 파일 의 위치 에 따라 파일 을 대량 작은 파일 로 분할 합 니 다.
  소박 한 서열 에 비해 비교적 타당 한 해결 방법 이다.데이터 양 이 너무 많아 서!우 리 는 어 쩔 수 없 이 큰 일 을 작은 일 로 만 들 고 작은 일 로 만 들 었 다.
  정렬 할 파일 의 10000 개의 데 이 터 를 읽 을 때마다 10000 개의 데 이 터 를 빠르게 정렬 하고 작은 파일 bigdata. part. i. sorted 에 쓰 는 것 입 니 다.이렇게 해서 우 리 는 5 만 개의 정렬 된 작은 파일 을 얻 었 다.
  정렬 된 작은 파일 이 있 는 토대 에서 나 는 이 파일 들 의 현재 위치의 최소 값 을 받 을 때마다 OK 입 니 다.이 값 들 을 순서대로 bigdata. sorted 에 기록 합 니 다.
2. 분할 - 데이터 자체 크기 에 따라 파일 을 대량 작은 파일 로 분할 합 니 다.
  데이터 위치 에 따라 큰 파일 을 분열 시 켜 도 됩 니 다.그러나 이 로 인해 작은 파일 을 큰 파일 로 합 칠 때 효율 적 이지 않다 는 문제 가 생 겼 다.그러면 여기 서 우 리 는 또 다른 생각 이 생 겼 다. 우 리 는 먼저 파일 의 데 이 터 를 크기 에 따라 다른 파일 에 넣 었 다.이 서로 다른 파일 들 을 정렬 합 니 다.이렇게 하면 우 리 는 직접 파일 의 사전 순서에 따라 출력 하면 된다.
3. 사전 트 리
  사전 트 리 의 기본 사용 에 대해 서 는 본인 의 다른 블 로 그 를 참조 할 수 있 습 니 다.
  '데이터 구조: 사전 트 리 의 기본 사용' 이라는 블 로그 에서 사전 순서 에 대한 설명 을 바탕 으로 사전 트 리 를 넓 게 검색 하 는 것 이 우리 가 해 야 한 다 는 것 을 알 고 있 습 니 다.
구조 설계도:
  
코드 분석:
0. 분 치
(0) 큰 파일 분할
  이 단 계 는 큰 파일 에 대한 분할 을 순서대로 진행 합 니 다. 그러면 우 리 는 데이터 의 분 산 화 를 확보 할 수 있 고 작은 파일 의 데이터 가 많 지 않 으 며 작은 파일 의 데이터 가 매우 적 습 니 다.

public static void splitBigFile2PartBySerial(String filePath, String partPath) throws IOException {
        File file = new File(filePath);
        FileInputStream inputStream = new FileInputStream(file);
        BufferedReader reader = new BufferedReader(new InputStreamReader(inputStream));
        
        StringBuffer buffer = new StringBuffer();
        
        String readerLine = "";
        int line = 0;
        while ((readerLine = reader.readLine()) != null) {
            buffer.append(readerLine + " ");
            if (++line % Config.PART_NUMBER_COUNT == 0) {
                sortStringBuffer(buffer);
                int splitLine = line / Config.PART_NUMBER_COUNT;
                write(partPath.replace("xxx", "" + splitLine), buffer.toString());
                buffer.setLength(0);
                System.out.println("SPLIT: " + splitLine);
            }
        }
        
        reader.close();
    }

(1) 정렬
  작은 것 으로 잘 렸 음 에 도 불구 하고 작은 파일 마다 5 만 개의 데이터 세트 가 있다.50000 개의 데이터 도 작은 데이터 가 아니 기 때문에 정렬 하 는 과정 에서 도 일부 신경 을 쓸 수 있 습 니 다. 여기 서 우리 가 사용 하 는 것 은 빠 른 배열 입 니 다.다음 과 같다.

public static void sortStringBuffer(StringBuffer buffer) {
        String[] numberTexts = buffer.toString().split(" ");
        buffer.setLength(0);
        int[] numbers = new int[numberTexts.length];
        for (int i = 0; i < numberTexts.length; i++) {
            numbers[i] = Integer.parseInt(numberTexts[i]);
        }
        
        int[] sorted = QKSort.quickSort(numbers);
        for (int i = 0; i < sorted.length; i++) {
            buffer.append(sorted[i] + "
");
        }
    }

(2) 합병
  합병 할 때 우 리 는 문 제 를 명확 하 게 해 야 한다.비록 우리 의 작은 파일 하나 가 이미 질서 가 있 지만, 우 리 는 아직 전체적인 순 서 를 모른다.예 를 들 면:
  문건 1: 1, 2, 4, 6, 9, 34, 288
  파일 2: 4 5 6 87 99 104 135
  위의 두 파일 은 모든 파일 내부 가 질서 가 있 지만 전체적으로 무질서 하 다.하나의 파일 이 질서 있 는 기초 위 에서 우 리 는 몇 가지 일 을 할 수 있다.우 리 는 모든 파일 의 데 이 터 를 하나의 대기 열 로 볼 수 있 습 니 다. 우 리 는 항상 대기 열의 첫 부분 부터 대기 열 을 진행 합 니 다. (대기 열의 머리 는 항상 가장 작은 숫자 이기 때 문 입 니 다.)이렇게 하면 우 리 는 문 제 를 N 개의 작은 파일 에서 순서대로 비교 하여 가장 작은 결 과 를 얻 고 파일 에 기록 할 수 있 습 니 다. (물론, 우 리 는 하나의 숫자 를 만 들 고 파일 을 한 번 쓸 수 없습니다. 이렇게 하면 너무 비효 율 적 입 니 다. 우 리 는 변수 캐 시 라 는 '최소 값' 을 사용 할 수 있 습 니 다.파일 이 모두 기 록 될 때 까지 변 수 를 비우 고 반복 합 니 다.

public static void mergeSorted(String dirPath) throws NumberFormatException, IOException {
        long t = System.currentTimeMillis();
        
        File dirFile = new File(dirPath);
        File[] partFiles = dirFile.listFiles();
        
        FileInputStream[] inputStreams = new FileInputStream[partFiles.length];
        BufferedReader[] readers = new BufferedReader[partFiles.length];
        
        int[] minNumbers = new int[partFiles.length];
        for (int i = 0; i < partFiles.length; i++) {
            inputStreams[i] = new FileInputStream(partFiles[i]);
            readers[i] = new BufferedReader(new InputStreamReader(inputStreams[i]));
            minNumbers[i] = Integer.parseInt(readers[i].readLine());
        }
        
        int numberCount = Config.TOTAL_NUMBER_COUNT;
        while (true) {
            int index = Tools.minNumberIndex(minNumbers);
            System.out.println(minNumbers[index]);
            write(Config.BIGDATA_NUMBER_FILEPATH_SORTED, minNumbers[index] + "
");
            minNumbers[index] = Integer.parseInt(readers[index].readLine());
            
            if (numberCount-- <= 0) {
                break;
            }
        }
        
        System.err.println("TIME: " + (System.currentTimeMillis() - t));
        
        for (int i = 0; i < partFiles.length; i++) {
            inputStreams[i].close();
            readers[i].close();
        }
    }

주: 여기 서 분 치 된 알고리즘 에 대해 저 는 실현 과정 만 제공 합 니 다.위의 설명 에서 여러분 도 문 제 를 깨 달 았 을 것 입 니 다. 만약 에 우리 가 큰 파일 의 데 이 터 를 수치 에 따라 크기 를 나 누 면 다른 작은 파일 로 나 눌 수 있 습 니 다.이렇게 하면 매우 치 명 적 인 문제 가 있 을 것 이다. 그것 은 바로 우리 의 작은 파일 이 양극 화 될 수 있다 는 것 이다. 즉, 일부 파일 의 데이터 가 매우 적 고 일부 작은 파일 의 데이터 가 매우 많다 는 것 이다.그래서 여기 서 저 는 더 이상 실현 과정 을 제공 하지 않 겠 습 니 다. 위 에서 설명 한 것 이 있 습 니 다. 다만 우리 가 문 제 를 해결 할 때 여러 가지 생각 이 있 을 수 있 습 니 다. 이런 생각 들 은 모두 좋 습 니 다. 다만 가끔 우 리 는 가장 좋 은 것 이 필요 합 니 다 (^ ^).
1. 사전 트 리
  사전 트 리 는 데 이 터 를 압축 할 수 있 는 데이터 구조 라 는 것 을 알 고 있 기 때 문 입 니 다. 특히 사용 하 는 문자열 의 개수 가 제한 되 어 있 습 니 다 (예 를 들 어 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'). 그리고 전체 수량 이 많은 경우 입 니 다.같은 문 자 를 여러 번 반복 해서 사용 할 수 있 기 때문이다.예 를 들 어 '123456789' 와 '123456780' 은 사실 '0' - '9' 라 는 10 글자 만 사용 했다.사전 나무의 실현 에 관 해 서 는 아주 간단 한 방법 이 라 고 생각 합 니 다.만약 당신 이 여전히 약간 몽롱 하고 모호 하 다 고 느낀다 면, 본인 의 다른 블 로그 인 을 참조 하 십시오. 그 블 로그 에서 저 는 사전 트 리 에 대한 각종 기본 조작 과 설명 을 상세 하 게 소개 합 니 다.
  여기 서 중요 한 코드 일 부 를 붙 여 여러분 과 함께 공부 하 겠 습 니 다.코드 는 다음 과 같 습 니 다:
(0) 데 이 터 를 파일 에 기록 합 니 다.

public static void sortTrie(String filePath) throws IOException {
        File file = new File(filePath);
        FileInputStream inputStream = new FileInputStream(file);
        BufferedReader reader = new BufferedReader(new InputStreamReader(inputStream));
        
        TrieTree tree = new TrieTree("sorting");
        String readerLine = "";
        int line = 0;
        while ((readerLine = reader.readLine()) != null) {
            tree.insert(readerLine);
            if (++line % Config.PART_NUMBER_COUNT == 0) {
                System.out.println("LINE: " + line);
            }
        }
        
        System.out.println("      ");
        
        writeTrieTree2File(Config.BIGDATA_NUMBER_FILEPATH_SORTED, tree);
        
        reader.close();
    }

(1) 사전 트 리 에 대한 범위 우선 검색

public static void sortNumberOrder(String filePath, Node node) throws IOException {
        Queue<Node> queuing = new LinkedList<Node>();
        queuing.offer(node);
        
        while (!queuing.isEmpty()) {
            Node currentNode = queuing.poll();
            if (currentNode.isEnd()) {
                buffer.append(getNodePath(currentNode) + "
");
                if (++index % 50000 == 0) {
                    write(filePath, buffer.toString());
                }
            }
            Node[] children = currentNode.getChildren();
            for (Node sonNode : children) {
                if (sonNode != null) {
                    queuing.offer(sonNode);
                }
            }
        }
    }
    
    /**
     *            ，      
     * @param node
     * @return
     */
    public static String getNodePath(Node node) {
        StringBuffer path = new StringBuffer();
        Node currentNode = node;
        while (currentNode.getParent() != null) {
            path.append(currentNode.getName());
            currentNode = currentNode.getParent();
        }
        
        return path.reverse().toString();
    }

소결:
  빅 데이터 탐색 은 여기에 그 치지 않 는 다.우리 가 이해 하고 발견 하 며 창조 하 기 를 기다 리 는 것 도 많다.
  한편, 대량의 데이터 문제 에 대해 우 리 는 분 치 를 이용 하여 그의 큰 부분 을 해결 하고 전 체 를 더욱 편리 하 게 관찰 할 수 있다.우리 가 이미 배 운 데이터 구조 와 알고리즘 을 사용 하여 문 제 를 풀 수도 있다.그러나 우리 가 끊임없이 공부 하고 끊임없이 탐색 하면 서 우 리 는 자신 이 배 운 고유 한 데이터 구조 와 알고리즘 이 우리 가 직면 한 문 제 를 완전히 해결 하지 못 한 다 는 것 을 느 낄 수 있다. 그러면 우리 의 창조력 이 필요 하 다.