Ломаем мозг. Часть 0.0

Итак, предположим Вам стало что-то очень скучно. Но это ничего страшного. Для веселья попробуем решить непростую задачку )

Дано: бинарный /или не бинарный - разницы в общем-то нету/ файл с хаотичными /рандомными/ данными.

Что сделать: отсортировать его.

Еще кое-что: файл может быть ооооооочень большим.

Взять сорцы можно тут.

Подготовка

Для начала нам нужно сгенерировать такой файл. В windows делайте что хотите, а я сижу на ubuntu и просто открываю консоль и пишу:

dd if=/dev/urandom of=/home/hanna/tosort.file bs=1M count=4096

Тут скажем спасибо братьям по разуму из irc-канала #ubuntu-ru )))

Как это будет работать

 Во-первых сортировать массив в оперативной памяти будем алгоритмом слияния, он имеет сложность O(n log n) - то есть очень быстрый. Этот же алгоритм будет применяться и к файлам.

Про сортировку слиянием можно почитать на википедии.

В-вторых, для ускорения работы будем использовать Fork/Join Framework. Не знаете, что это такое? Тогда загляните сюда)

Требуется Java 7. Это тоже важно. 

Итак, теперь непосредственно описание логики.

1. Читаем исходный файл, если он очень большой, то разделяем его на 2 временных, которые рекурсивно тоже разбиваются, пока не получим размер такой, что можно отсортировать.

2. После сортировки данных они записываются в свои временные файлы.

3. Два отсортированных файла совмещаем, при этом выходим из рекурсии.

4. В конце получаем, что исходный файл отсортирован.

Замечание! Когда получаем количество доступных байт для чтения вот так:

int availableSize = mainFile.available();

Есть одна особенность - мы получаем тип int, а следовательно, если доступно более 2Гб /это примерно/, то он нам и покажет максимальное значение типа int. Поэтому это значение перечитывается в цикле после получения очередного куска данных из файла.

Наверное, по комментариям проще понять логику) И вообще, чтобы понять, нужно думать параллельно-рекурсивно)

Что же мы получим

Это содержимое файла до и после сортировки
/Тут еще раз скажем спасибо мальчикам из #ubuntu-ru/

Копирайт

Вы можете использовать всю эту информацию как Вам будет угодно /даже продавать, если захотите/. Ваши ссылки на этот источник при перепечатывании останутся только на Вашей совести, карма сама все сделает.

Исходный код

MergeSortingFileTask.java - это работа с файлами

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.RecursiveAction;

/**
 * @author Hanna Eismant
 * 13.11.12
 */
public class MergeSortingFileTask extends RecursiveAction {

    //    имя файла для обработки
    private String mainFileName;
    //    имя одного временного файла
    private String tempFileName0;
    //    имя второго временного файла
    private String tempFileName1;

    /**
     * Задать файл для обработки.
     *
     * @param mainFileName Полный путь к файлу.
     */
    public void setMainFileName(String mainFileName) {
        this.mainFileName = mainFileName;
    }

    private void merge() throws IOException {
        System.out.println("[INFO] Merge files");
//        файлы
        FileOutputStream resultFile = new FileOutputStream(mainFileName);
        FileInputStream tempFile0 = new FileInputStream(tempFileName0);
        FileInputStream tempFile1 = new FileInputStream(tempFileName1);
//        сюда читаем из temp файлов
        Integer from0 = null;
        Integer from1 = null;
//        количество доступных байт для чтения
        int available0 = tempFile0.available();
        int available1 = tempFile1.available();
//        пока есть что читать в обоих файлах одновременно
        while (available0 > 0 && available1 > 0) {
            if (from0 == null) {
                from0 = tempFile0.read();
            }
            if (from1 == null) {
                from1 = tempFile1.read();
            }
            if (from0 < from1) {
                resultFile.write(from0);
                from0 = null;
            } else {
                resultFile.write(from1);
                from1 = null;
            }
            available0 = tempFile0.available();
            available1 = tempFile1.available();
        }
//        после цикла выше в одном из файлов еще что-нить осталось
//        вот это мы и дочитываем
        while (available0 > 0) {
            from0 = tempFile0.read();
            resultFile.write(from0);
            available0 = tempFile0.available();
        }
        while (available1 > 0) {
            from1 = tempFile1.read();
            resultFile.write(from1);
            available1 = tempFile1.available();
        }
//        теперь имеем отсортированные данные в исходном файле
//        временные файлы можно удалить
        resultFile.close();
        tempFile0.close();
        tempFile1.close();
        File f0 = new File(tempFileName0);
        f0.delete();
        File f1 = new File(tempFileName1);
        f1.delete();
    }

    /**
     * Вычислительная часть по разбиению файла на части и отправки их на сортирвку.
     */
    @Override
    protected void compute() {
//        если не задано имя исходного (главного) файла, то выдаем ошибку и закрываемся
        if (mainFileName == null || mainFileName.isEmpty()) {
            System.err.println("[ERROR] Filename not set");
            return;
        }

        try {
//            главный файл, с которго читаем
            FileInputStream mainFile = new FileInputStream(mainFileName);

//            количество байтов, изначально доступных для чтеия
            int availableSize = mainFile.available();
            System.out.println("[INFO] Total size: " + availableSize);

//            устанавливем первоначальный размер для чтения
            int sizeToRead = availableSize;

//            если читаемый кусок можно поместить в память и обработать,
//            то его отправляем на сортировку
            if (sizeToRead < ApplicationProperties.getSizeArray()) {
//                читаем данные из файла и запихиваем их в массив
                ArrayList data = new ArrayList();
                for (int i = 0; i < sizeToRead; i++) {
                    data.add(mainFile.read());
                }
                mainFile.close();
//                создаем и запускаем задачу на сортировку массива
                MergeSortingTask task = new MergeSortingTask();
                task.setData(data);
                task.fork();
//                получаем отсортированный массив
                List sort = (List) task.join();
//                открываем главный файл для записи
                FileOutputStream mainResult = new FileOutputStream(mainFileName);
                System.out.println("[INFO] Writing result into file: '" + mainFileName + "'");
//                записываем в него отсортированный массив
                for (int i = 0; i < sort.size(); i++) {
                    mainResult.write(sort.get(i));
                }
                mainResult.close();
                System.out.println("[INFO] Task is complete");
//                закрываем текущую задачу
                return;
            }

//            пути для временных файлов
            tempFileName0 = File.createTempFile("bigSort", "tmp").getAbsolutePath();
            tempFileName1 = File.createTempFile("bigSort", "tmp").getAbsolutePath();

            System.out.println("[INFO] Create temp file: '" + tempFileName0 + "'");
            System.out.println("[INFO] Create temp file: '" + tempFileName1 + "'");

//            открываем temp для записи
            FileOutputStream tempFileWrite0 = new FileOutputStream(tempFileName0);
            FileOutputStream tempFileWrite1 = new FileOutputStream(tempFileName1);

            while (availableSize > 0) {
                System.out.println("[INFO] Riding size: " + sizeToRead);
//                находим середину
                int middleToRead = sizeToRead / 2;
//                первую половину куска записываем в 0й temp
                for (int i = 0; i < middleToRead; i++) {
                    tempFileWrite0.write(mainFile.read());
                }
//                а вторую половину куска записываем в 1й temp
                for (int i = middleToRead + 1; i <= sizeToRead; i++) {
                    tempFileWrite1.write(mainFile.read());
                }
//                перечитываем количество осавшихся байтов для чтения
                sizeToRead = availableSize = mainFile.available();
                System.out.println("[INFO] Total size: " + availableSize);
            }
//            закрываем все файлы
            mainFile.close();
//            File f = new File(mainFileName);
//            f.delete();
            tempFileWrite0.close();
            tempFileWrite1.close();

//            создаем подзадачи
            MergeSortingFileTask subTask0 = new MergeSortingFileTask();
            MergeSortingFileTask subTask1 = new MergeSortingFileTask();
            subTask0.setMainFileName(tempFileName0);
            subTask1.setMainFileName(tempFileName1);
//            запускаем подзадачи и ждем их выполнения
            invokeAll(subTask0, subTask1);
//           объединяем temp файлы
            merge();

        } catch (FileNotFoundException e) {
            System.err.println("[ERROR] File not found: '" + ApplicationProperties.getInFileName() + "'");
        } catch (IOException e) {
            System.err.println("[ERROR] I\\O error ");
        }
    }
} 

MergeSortingTask.java - сортировка массива /в оперативной памяти/

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.RecursiveTask;

/**
 * Сортировка массива слиянием.
 * Сложность O(n log n)
 * @author Hanna Eismant
 * 13.11.12
 */
public class MergeSortingTask extends RecursiveTask {

    private List data = new ArrayList();

    /**
     * Массив для сортировки.
     * @param data
     */
    public void setData(List data) {
        this.data = data;
    }

    /**
     * Сортировка массива. Используется рекурсия.
     * Выполняется сортировака по возрастанию.
     *
     * @param dataToSort Массив для сортировки
     * @return Отсортированный массив
     */
    public List sort(List dataToSort) {
        int dataSize = dataToSort.size();
//        если в массиве один элемент, то нам ничего не надо делать
//        просто возвращаем как есть
        if (dataSize <= 1) {
            return dataToSort;
        } else {
//             если в массиве несколько элемнтов, то делим массив
//             поплам и уходим в рекурсию и
//             возвращаем объединение результатов
            int middleIndex = dataSize / 2;
//            все впихиваем в одну мегаконструкцию, чтобы не создавать
//            дополнительных объектов и уменьшить расход памяти
            return merge(
                    sort(dataToSort.subList(0, middleIndex)),
                    sort(dataToSort.subList(middleIndex, dataSize))
            );
        }
    }

    /**
     * Объединение двух сортированных массивов.
     *
     * @param dataToMerge0 Первый массив для объединения.
     *                     Должен быть отсортирован по возрастанию.
     * @param dataToMerge1 Второй массив для объединения.
     *                     Должен быть отсортирован по возрастанию.
     * @return Отсортированный масссив, полученный при объединении входных
     */
    private List merge(List dataToMerge0, List dataToMerge1) {
//        индекс просматривемого элемента первого массива
        int a = 0;
//        индекс просматриваемого элемента второго массива
        int b = 0;
//        размер объединенного массива
        int mergedLen = dataToMerge0.size() + dataToMerge1.size();
//        объединенный массив
        List merged = new ArrayList(mergedLen);
//        количество посмотров\сравнений столько же, сколько
//        элементов в результирующем массиве
        for (int i = 0; i < mergedLen; i++) {
//            если мы не просмотрели элементы обоих массивов до конца (одновременно)
            if (a < dataToMerge0.size() && b < dataToMerge1.size()) {
//                сравниваем элементы обоих массивов и меньший добавляем в результирующий
//                при этом увеличиваем соответствующий счетчик (a или b)
                if (dataToMerge0.get(a) < dataToMerge1.get(b)) {
                    merged.add(dataToMerge0.get(a++));
                } else {
                    merged.add(dataToMerge1.get(b++));
                }
//                проверяем, какой массив недосмотрели и берем из него элемент(ы)
            } else if (a < dataToMerge0.size()) {
                merged.add(dataToMerge0.get(a++));
            } else if (b < dataToMerge1.size()) {
                merged.add(dataToMerge1.get(b++));
            }
        }
//        возвращаем результат
        return merged;
    }

    /**
     * Вычислительная часть задачи. по сортировке массива.
     * @return Отсортированный массив
     */
    @Override
    protected Object compute() {
        System.out.println("[INFO] Starting sort");
        int dataSize = data.size();
//        если мы достигли порогового значения
        if (dataSize < ApplicationProperties.getThresholdMemory())  {
//            то выполняем сортировку своей части
            return sort(data);
        } else {
//            в противном случае продолжаем разбивать
            MergeSortingTask subTask0 = new MergeSortingTask();
            MergeSortingTask subTask1 = new MergeSortingTask();

            int middleIndex = dataSize / 2;

            subTask0.setData(data.subList(0, middleIndex));
            subTask1.setData(data.subList(middleIndex, dataSize));

//            запускаем подзадачи
            subTask0.fork();
            subTask1.fork();

//            получаем результат подзадач
            List result0 = (List) subTask0.join();
            List result1 = (List) subTask1.join();

//            объединяем с сортировкой результат подзадач
//            и возвращаем его головной задаче
            return merge(result0, result1);
        }
    }
}

ApplicationProperties.java - некоторые настройки

/**
 * @author Hanna Eismant
 * 13.11.12
 */
public final class ApplicationProperties {

    private static int thresholdMemory;
    private static int sizeArray;
    private static String inFileName;

    static {
        thresholdMemory = 32000;
        sizeArray = 128000;
        inFileName = "/home/hanna/tosort.file";
    }

    public static int getThresholdMemory() {
        return thresholdMemory;
    }

    public static int getSizeArray() {
        return sizeArray;
    }

    public static String getInFileName() {
        return inFileName;
    }
}

И напоследок "запускатор" Runner.java

import java.util.concurrent.ForkJoinPool;

/**
 * @author Hanna Eismant
 * 13.11.12
 */
public class Runner {

    public static void main(String[] args) {

        long start = System.currentTimeMillis();

        MergeSortingFileTask mainTask = new MergeSortingFileTask();
        ForkJoinPool pool = new ForkJoinPool();
        mainTask.setMainFileName(ApplicationProperties.getInFileName());
        pool.invoke(mainTask);

        System.out.println("[INFO] Sorting is complete. Gratis!");
        long end = System.currentTimeMillis();
        long delay = end - start;
        System.out.println("[INFO] Time: " + delay + "ms");
    }
}