如何實現基于多路歸并的外排序

本篇內容主要講解“如何實現基于多路歸并的外排序”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“如何實現基于多路歸并的外排序”吧!

import com.google.common.collect.Lists;

import java.io.*;
import java.util.*;

/**
 * 對遠遠大于內存的數據進行外排序，先將文件分割為內存可以單獨處理多個小文件，
 * 在內存中對這些小文件進行排序，然后多路歸并將這些文件合并成最終的有序大文件
 *
 */
public class ExternalSort {

    public static int BUFFER_SIZE = 1024 * 4 * 1000;  // 一次緩沖讀取

    public static int LITTLE_FILE_SIZE = 10;    // 每個文件的記錄數

    public static File IN_FILE = new File("data/f1.txt");//要排序的文件

    public static File OUT_FILE = new File("data/concat");//輸出合并后的有序的文件

    /**
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        //排序
        long start = System.currentTimeMillis();
        new ExternalSort().mSort(IN_FILE);
        long end = System.currentTimeMillis();
        System.out.println((end - start) / 1000 + "s");
    }

    /**
     * 多路歸并
     *
     * @param file
     * @throws IOException
     */
    public void mSort(File file) throws IOException {
        List<File> files = split(file); // 分割成小文件并加載到內存排序
        multMerge(files); //歸并

    }

    /**
     * Splits the original file into a number of sub files.
     */
    public List<File> split(File file) throws IOException {
        List<File> files = Lists.newArrayList();
        BufferedReader din = new BufferedReader(new FileReader(file), BUFFER_SIZE);

        int[] buffer = new int[LITTLE_FILE_SIZE];
        boolean fileCompleted = false;

        while (!fileCompleted) {
            int len = buffer.length;
            for (int i = 0; i < buffer.length && !fileCompleted; i++) {
                try {
                    buffer[i] = Integer.parseInt(din.readLine());
                } catch (NumberFormatException | IOException e) {
                    fileCompleted = true;
                    len = i;
                }
            }

            //將buffer數據排序寫入文件
            if (len > 0) {
                Arrays.sort(buffer, 0, len);
                File f = new File("data/set" + new Random().nextInt());
                BufferedWriter dout = new BufferedWriter(new FileWriter(f));
                for (int i = 0; i < len; i++) {
                    dout.write(buffer[i]+"\n");
                }
                dout.close();
                files.add(f);
            }
        }
        din.close();
        return files;
    }

    /**
     * 多路歸并
     *
     * @param files
     * @throws IOException
     */
    public static void multMerge(List<File> files) throws IOException {
        //構建輸出緩沖流
        BufferedWriter out = new BufferedWriter(new FileWriter(OUT_FILE), BUFFER_SIZE);
        //構建輸入緩沖流
        List<BufferedReader> inList = Lists.newArrayList();
        int size = files.size();
        for (int i = 0; i < size; i++) {
            inList.add(i,new BufferedReader(new FileReader(files.get(i)), BUFFER_SIZE));
        }
        //構建一個數組，存放從每個輸入流里取出來的數據
        int[] ext = new int[size];
        int left = size;  //定義剩余文件數
        for (int i = 0; i < size; i++) {
            try {
                ext[i] = Integer.parseInt(inList.get(i).readLine());
            } catch (Exception e) {
                ext[i] = -1;
                left--;
                inList.get(i).close();
            }
        }

        //將ext數組中最小值寫入文件
        while (left > 0) {
            int ind = getMinIndex(ext);
            out.write(ext[ind]+"\n");
            //然后從相應的輸入流中取出下一個數據
            try {
                ext[ind] = Integer.parseInt(inList.get(ind).readLine());
            } catch (Exception e) {
                ext[ind] = -1;
                left--;
                inList.get(ind).close();
            }
        }
        out.close();
    }

    //找到數據中最小的一個
    public static int getMinIndex(int[] ext) {
        //找到第一個不為-1的元素
        int min;
        int inx = 0;
        while (true) {
            if (ext[inx] != -1) {
                min=ext[inx];
                break;
            } else {
                inx++;
            }
        }
        for (int i = 1; i < ext.length; i++) {
            if (ext[i] < min && ext[i] != -1) {
                min = ext[i];
                inx = i;
            }
        }
        return inx;
    }
}

到此，相信大家對“如何實現基于多路歸并的外排序”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！