Как ускорить внешнюю сортировку слиянием в Java

Question

Я пишу код для внешней сортировки слиянием. Идея состоит в том, что входные файлы содержат слишком много чисел для хранения в массиве, поэтому вы читаете некоторые из них и помещаете их в файлы для хранения. Вот мой код Хотя он работает быстро, он не достаточно быстр. Мне было интересно, можете ли вы подумать о каких-либо улучшениях, которые я могу сделать в коде. Обратите внимание, что сначала я сортирую все 1m целых чисел, поэтому пропускаю итерации алгоритма слияния.

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.security.DigestInputStream;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;

public class ExternalSort {

    public static void sort(String f1, String f2) throws Exception {
        RandomAccessFile raf1 = new RandomAccessFile(f1, "rw");
        RandomAccessFile raf2 = new RandomAccessFile(f2, "rw");
        int fileByteSize = (int) (raf1.length() / 4);
        int size = Math.min(1000000, fileByteSize);
        externalSort(f1, f2, size);  
        boolean writeToOriginal = true;
        DataOutputStream dos;
        while (size <= fileByteSize) {
            if (writeToOriginal) {
                raf1.seek(0);
                dos = new DataOutputStream(new BufferedOutputStream(
                        new MyFileOutputStream(raf1.getFD())));
            } else {
                raf2.seek(0);
                dos = new DataOutputStream(new BufferedOutputStream(
                        new MyFileOutputStream(raf2.getFD())));
            }
            for (int i = 0; i < fileByteSize; i += 2 * size) {
                if (writeToOriginal) {
                    dos = merge(f2, dos, i, size);
                } else {
                    dos = merge(f1, dos, i, size);
                }
            }
            dos.flush();
            writeToOriginal = !writeToOriginal;
            size *= 2;
        }
        if (writeToOriginal)
        {
            raf1.seek(0);
            raf2.seek(0);
            dos = new DataOutputStream(new BufferedOutputStream(
                    new MyFileOutputStream(raf1.getFD())));
            int i = 0;
            while (i < raf2.length() / 4){
                dos.writeInt(raf2.readInt());
                i++;
            }   
            dos.flush();
        }
    }

    public static void externalSort(String f1, String f2, int size) throws Exception{

        RandomAccessFile raf1 = new RandomAccessFile(f1, "rw");
        RandomAccessFile raf2 = new RandomAccessFile(f2, "rw");

        int fileByteSize = (int) (raf1.length() / 4);

        int[] array = new int[size];
        DataInputStream dis = new DataInputStream(new BufferedInputStream(
                new MyFileInputStream(raf1.getFD())));
        DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(
                new MyFileOutputStream(raf2.getFD())));

        int count = 0;
        while (count < fileByteSize){
            for (int k = 0; k < size; ++k){
                array[k] = dis.readInt();
            }
            count += size;
            Arrays.sort(array);
            for (int k = 0; k < size; ++k){
                dos.writeInt(array[k]);
            }       
        }
        dos.flush();
        raf1.close();
        raf2.close();
        dis.close();
        dos.close();
    }

    public static DataOutputStream merge(String file,
            DataOutputStream dos, int start, int size) throws IOException {
        RandomAccessFile raf = new RandomAccessFile(file, "rw");
        RandomAccessFile raf2 = new RandomAccessFile(file, "rw");

        int fileByteSize = (int) (raf.length() / 4);
        raf.seek(4 * start);
        raf2.seek(4 *start);
        DataInputStream dis = new DataInputStream(new BufferedInputStream(
                new MyFileInputStream(raf.getFD())));
        DataInputStream dis3 = new DataInputStream(new BufferedInputStream(
                new MyFileInputStream(raf2.getFD())));
        int i = 0;
        int j = 0;
        int max = size * 2;

        int a = dis.readInt();

        int b;
        if (start + size < fileByteSize) {
            dis3.skip(4 * size);
            b = dis3.readInt();
        } else {
            b = Integer.MAX_VALUE;
            j = size;
        }
        while (i + j < max) {
            if (j == size || (a <= b && i != size)) {
                dos.writeInt(a);
                i++;
                if (start + i == fileByteSize) {
                    i = size;
                } else if (i != size) {
                    a = dis.readInt();
                }
            } else {
                dos.writeInt(b);
                j++;
                if (start + size + j == fileByteSize) {
                    j = size;
                } else if (j != size) { 

                    b = dis3.readInt();
                }
            }
        }
        raf.close();
        raf2.close();
        return dos;
    }

    public static void main(String[] args) throws Exception {
        String f1 = args[0];
        String f2 = args[1];

        sort(f1, f2);

     }
}

Answer 1

Мы реализовали в Java внешнюю сортировку в открытом доступе:

http://code.google.com/p/externalsortinginjava/

Это может быть быстрее, чем у вас.Мы используем строки, а не целые числа, но вы можете легко изменить наш код, подставив в строки целые числа (код был сделан взломанным по замыслу).По крайней мере, вы можете сравнить с нашим дизайном.

Глядя на ваш код, кажется, что вы читаете данные в единицах целых чисел.Так что IO будет узким местом, я думаю.С помощью алгоритмов внешней памяти вы хотите читать и записывать блоки данных - особенно в Java.

Answer 2

Возможно, вы захотите объединить k> 2 сегмента за раз.Это уменьшает количество операций ввода-вывода с n log k / log 2 до n log n / log k.

Редактировать: В псевдокоде это будет выглядеть примерно так:

void sort(List list) {
    if (list fits in memory) {
        list.sort();
    } else {
        sublists = partition list into k about equally big sublists
        for (sublist : sublists) {
            sort(sublist);
        }
        merge(sublists);
    }
}

void merge(List[] sortedsublists) {
    keep a pointer in each sublist, which initially points to its first element
    do {
        find the pointer pointing at the smallest element
        add the element it points to to the result list
        advance that pointer
    } until all pointers have reached the end of their sublist
    return the result list
}

Чтобы эффективно найти «самый маленький» указатель, вы можете использовать PriorityQueue.

Answer 3

Я бы использовал отображенные в память файлы.Это может быть в 10 раз быстрее, чем при использовании этого типа ввода-вывода.Я подозреваю, что в этом случае это будет намного быстрее.Отображенные буферы используют виртуальную память, а не кучу места для хранения данных и могут быть больше, чем доступная физическая память.

Answer 4

Вы сортируете целые числа, поэтому вам следует проверить сортировку по основанию.Основная идея радикальной сортировки состоит в том, что вы можете сортировать n-байтовые целые числа с n проходами через данные с радикальной 256.

Вы можете объединить это с теорией сортировки слиянием.