如何實現(xiàn)基于多路歸并的外排序

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

成都創(chuàng)新互聯(lián)公司專注于企業(yè)成都全網(wǎng)營銷、網(wǎng)站重做改版、秀洲網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、HTML5、購物商城網(wǎng)站建設(shè)、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為秀洲等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

import com.google.common.collect.Lists;

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

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

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

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

    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); // 分割成小文件并加載到內(nèi)存排序
        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數(shù)據(jù)排序?qū)懭胛募?
            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 {
        //構(gòu)建輸出緩沖流
        BufferedWriter out = new BufferedWriter(new FileWriter(OUT_FILE), BUFFER_SIZE);
        //構(gòu)建輸入緩沖流
        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));
        }
        //構(gòu)建一個數(shù)組，存放從每個輸入流里取出來的數(shù)據(jù)
        int[] ext = new int[size];
        int left = size;  //定義剩余文件數(shù)
        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數(shù)組中最小值寫入文件
        while (left > 0) {
            int ind = getMinIndex(ext);
            out.write(ext[ind]+"\n");
            //然后從相應(yīng)的輸入流中取出下一個數(shù)據(jù)
            try {
                ext[ind] = Integer.parseInt(inList.get(ind).readLine());
            } catch (Exception e) {
                ext[ind] = -1;
                left--;
                inList.get(ind).close();
            }
        }
        out.close();
    }

    //找到數(shù)據(jù)中最小的一個
    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;
    }
}

到此，相信大家對“如何實現(xiàn)基于多路歸并的外排序”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

當前文章：如何實現(xiàn)基于多路歸并的外排序
瀏覽路徑：http://www.muchs.cn/article38/ijsjsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、定制網(wǎng)站、網(wǎng)站收錄、商城網(wǎng)站、網(wǎng)站設(shè)計、網(wǎng)站維護

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都做網(wǎng)站