Внешняя сортировка, дающая OutOfMemory в вызове readInt () - PullRequest
Новая
       13

Внешняя сортировка, дающая OutOfMemory в вызове readInt ()

0 голосов
/ 07 октября 2018

Я использую Внешнюю сортировку со слиянием для сортировки файлов целых чисел.Обычно решением этой проблемы является увеличение размера кучи JVM с использованием -Xmx, но мне было интересно, существует ли способ улучшить мой код без увеличения размера кучи.

Метод, выдавший ошибку, является методом слияния. 

public static void merge(RandomAccessFile a1, RandomAccessFile a2, RandomAccessFile b1,DataOutputStream output, int start, int end) throws FileNotFoundException, IOException {
    //a1: file being read from
    //b1: file being written to

    if((int)a1.length() == 0) {
        return;
    }

    DataInputStream input_a1 = new DataInputStream(
            new BufferedInputStream(new FileInputStream(a1.getFD())));

    DataInputStream input_a2 = new DataInputStream(
            new BufferedInputStream(new FileInputStream(a2.getFD())));


    b1.seek(start); //set output pointer to start


    int mid = (start + end) /2;
    int file_length = (int)a1.length();


    //basically if second block is empty so just copy
    if (end > file_length) {
        end = file_length;
        if (end <= mid) {
            //copy from start to EOF

            int no_of_ints_left = (file_length - start)/4;
            for(int i = 1; i <= no_of_ints_left; i++) {

                output.writeInt(input_a1.readInt());
            }
            output.flush();

            return;
        }
    }


    int first_counter = start;
    int second_counter = mid;

    int x;
    int y;

    while(first_counter < mid && second_counter < end) {
        input_a1.mark(first_counter);
        input_a2.mark(second_counter);
        x = input_a1.readInt();
        y = input_a2.readInt();
        if(x < y) {
            output.writeInt(x);
            input_a2.reset();
            first_counter += 4;
        }
        else {
            output.writeInt(y);
            input_a1.reset();
            second_counter += 4;
        }
    }
    output.flush();
    if(first_counter == mid) {
        int no_of_ints_left = (end - second_counter)/4;

        while(no_of_ints_left > 0){
            x = input_a2.readInt();
            output.writeInt(x);
            no_of_ints_left--;
        }

    }
    else {
        int no_of_ints_left = (mid - first_counter)/4;
        while(no_of_ints_left > 0){
            x  = input_a1.readInt();
            output.writeInt(x);
            no_of_ints_left--;
        }
    }
    output.flush();
    input_a1 = null;
    input_a2 = null;
    return;

}

Строка, которая вызвала ошибку OutOfMemory, - это строка x = input_a1.readInt (), но я сомневаюсь, что этопричина ошибки.Я пытался вызывать System.gc () после каждого вызова merge (), но это не решило проблему.Какими еще способами можно оптимизировать метод, чтобы он занимал меньше памяти?

1 Ответ

0 голосов
/ 07 октября 2018

Код использует mark в буферизованном потоке.Это потребует, чтобы весь помеченный раздел находился в памяти, что, вероятно, является вашей проблемой.

RandomAccessFile, вероятно, самый простой способ получить те же функции, но хранить данные на диске.Отображение памяти с помощью java.nio является более сложной техникой и может по-прежнему сталкиваться с проблемами на 32-разрядных компьютерах.Тем не менее, я думаю, что вы все еще можете столкнуться с серьезными проблемами с производительностью для больших файлов.

(Также трассировка стека полезна для точного определения того, какое распределение не удалось. Возможно, перераспределение буфера. Хотя профилирование кучи скажет вамчто на самом деле занимает память.)

...