Java
28 July 2009

Сортировка больших объёмов данных, реализация на Java

Недавно на Хабре была статья Сортировка миллиона 32-битных int'ов в 2 мегабайтах памяти на Питоне. Заинтересовался, попробовал реализовать на Java.

Конечно, 32 строчки не получилось. Получилось 235.
Но мне показалось, что результат вполне можно использовать в качестве первого поста — не судите строго ;)


Сначала получилась пробная версия, которая работала с массивами целых чисел, хранила их в бинарном файле. После того как она заработала (кстати, 2.3 секунды на p4-3.2), подумалось, что жесткая привязка к архитектуре и типам не есть правильный путь. Ведь недаром в яве сделали коллекции, которые работают с любыми типами данных.

Потратив 2 часа, я получил вполне рабочий класс, переваривающий любые Comparable-типы.

Из чего «оно» состоит:


Test — класс для проверки работоспособности. С юнит-тестами я не заморачивался.

FileSort — собственно, главный работник, повар и плотник.

FileSortStorageObject — помощник, сохраняющий список объектов во временный файл.

FileSortStorage — интерфейс помощника. На самом деле сериализация (ObjectOutputStream и ObjectInputStream) несколько замедляет работу алгоритма, так что желающие могут реализовать другой метод сохранения.

Как оно работает:


Так как данных много, то представлять их в виде полного массива смысла нет. Мне показалось, что с ними можно работать при помощи итератора.

1. С помощью итератора читается часть данных, которая вмещается в память (количество записей задаётся).
2. Прочитанный блок сортируется тем же quicksort (накладные расходы по памяти у него не велики).
3. Далее отсортированный блок складывается в свой временный файл, где лежит до поры до времени.
4. Пока есть данные, повторяются п1-3
5. Здесь у нас имеется N файлов, каждый из которых содержит отсортированную порцию данных.
6. Создаётся итератор, который элементарно производит слияние имеющихся файлов.

При слиянии тоже используются итераторы (что поделать, нравятся мне они), которые выбирают очередную запись из каждого отдельного файла. Из выбранных записей выбирается минимальная, которая возвращается наружу. На место выданной наружу записи тут же подчитывается очередной объект из соответствующего файла.

Итак, исходники. Вдруг кто-то захочет поиграться


Основной класс:


package ru.dchekmarev.test.FileSort;

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

/**
* Класс для сортировки больших объёмов данных с использованием файловой подкачки
*/

public class FileSort<T extends Comparable<T>> implements Iterable<T> {
    private int bufferSize = 10000;
    private List<FileSortStorage> partFiles = new LinkedList<FileSortStorage>();
    private Iterator<T> source;
    private List<T> part = new LinkedList<T>();
    /**
     * Конструктор по умолчанию, ничего не делает
     */

    public FileSort() {
    }
    /**
     * Конструктор с параметром - источником
     */

    public FileSort(Iterator<T> newSource) {
        setSource(newSource);
    }
    /**
     * Конструктор с двумя параметрами - источником и количеством объектов на файл
     */

    public FileSort(Iterator<T> newSource, Integer newSize) {
        this(newSource);
        setBufferSize(newSize);
    }
    /**
     * Установка количества объектов на один файл
     */

    public void setBufferSize(int newSize) {
        bufferSize = newSize;
    }
    /**
     * Установка источника данных, используется итератор
     */

    public void setSource(Iterator<T> newSource) {
        source = newSource;
        try {
            sortParts();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        Collections.sort(part);
    }
    /**
     * Получение результата в виде итератора
     */

    public Iterator<T> iterator() {
        if (partFiles.size() == 0) {
            // маленькая оптимизация, если всё уместилось в память
            return part.iterator();
        }
        return new Iterator<T>() {
            Long t = 0L;
            List<T> items = new ArrayList<T>();
            List<Iterator<T>> iterators = new ArrayList<Iterator<T>>();
            Integer minIdx = null;
            // динамическая инициализация итератора, вместо конструктора
            // делаем список итераторов по одному на файл, из которых будем извлекать элементы при слиянии
            {
                iterators.add(part.iterator());
                for (FileSortStorage f : partFiles) {
                    iterators.add(f.iterator());
                }
                for (Iterator<T> item : iterators) {
                    if (item.hasNext()) {
                        items.add(item.next());
                    } else {
                        throw new RuntimeException("failed to get first for iterator");
                    }
                }
            }
            /**
             * Находит среди объектов минимальный, возвращает доступность очередного объекта
             */

            public boolean hasNext() {
                if (minIdx == null) {
                    for (int i = 0; i < items.size(); i++) {
                        if (items.get(i) != null &&
                                (minIdx == null ||
                                 items.get(i).compareTo(items.get(minIdx)) < 0)) {
                            minIdx = i;
                        }
                    }
                }
                return minIdx != null;
            }
            /**
             * Если есть доступный объект - возвращает,
             * замещая его в доступных на очередной из файла
             */

            public T next() {
                T res = null;
                if (hasNext()) {
                    res = items.get(minIdx);
                    if (iterators.get(minIdx).hasNext()) {
                        items.set(minIdx, iterators.get(minIdx).next());
                    } else {
                        items.set(minIdx, null);
                    }
                }
                minIdx = null;
                return res;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
    /**
     * Производит чтение исходных данных с сохранением блоков во временные файлы
     */

    void sortParts() throws IOException {
        while (source.hasNext()) {
            part.add((T)source.next());
            if (part.size() >= bufferSize && source.hasNext()) {
                Collections.sort(part);
                partFiles.add(new FileSortStorageObject(part));
                part.clear();
            }
        }
    }
}



Интерфейс для сохранения на диске:



package ru.dchekmarev.test.FileSort;

import java.util.List;
import java.io.IOException;

public interface FileSortStorage<T> extends Iterable<T> {
    public void setObjects(List<T> objects) throws IOException;
}



Реализация сохранения на диске сериализованных объектов:



package ru.dchekmarev.test.FileSort;

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

/**
* Класс сохраняет список в хранилище и предоставляет к нему доступ через итератор
*/

public class FileSortStorageObject<T> implements FileSortStorage<T> {
    private final File file;

    /**
     * Конструктор, создаёт временный файл и сохраняет в него объекты
     */


    public FileSortStorageObject(List<T> objects) throws IOException {
        file = File.createTempFile("FileSort", "dat");
        setObjects(objects);
    }
    /**
     * Сохраняем объекты в файл
     */

    public void setObjects(List<T> objects) throws IOException {
        ObjectOutputStream wr = new ObjectOutputStream(new FileOutputStream(file));
        for (T item : objects) {
            wr.writeObject(item);
        }
        wr.close();
    }
    /**
     * Итератор по файлу-хранилищу объектов
     */


    public Iterator<T> iterator() {
        try {
            return new Iterator<T>() {
                private ObjectInputStream fr =
                        new ObjectInputStream(new FileInputStream(file));
                T obj;
                public boolean hasNext() {
                    if (obj == null) {
                        try {
                            obj = (T)fr.readObject();
                        } catch (ClassNotFoundException e) {
                            throw new RuntimeException(e);
                        } catch (IOException e) {
                            obj = null;
                        }
                    }
                    return obj != null;
                }
                public T next() {
                    hasNext();
                    T res = obj;
                    obj = null;
                    return res;
                }
                public void remove() {
                    throw new UnsupportedOperationException();
                }
            };
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
    /**
     * Зачищаем
     */


    protected void finalize() {
        file.delete();
    }
}


И тестовый класс, всегда ведь хочется видеть наглядный результат:



package ru.dchekmarev.test.FileSort;

import java.util.*;

public class Test {
    public static void main(String[] args) {
        System.out.println("Test start");
        // создаём класс-сортировщик

        FileSort<Double> sort = new FileSort<Double>(
                        // в конструктор передаём итератор - источник данных
                        // у нас он просто генерирует случайные числа
                        new Iterator<Double>() {
            private int i = 0;
            private Random rand = new Random();
            public boolean hasNext() {
                if (i >= 1000) {
                    System.out.println("generator finish");
                }
                return i < 1000;
            }
            public Double next() {
                i++;
                return rand.nextDouble();
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        });
        int i = 0;
        // выводим отсортированный результат

        for (Double res : sort) {
            if (++i % 10000 == 0) {
                // когда результатов много имеет смысл их вывод отключить
                // и просто считать количество
                System.out.println(i);
            }
            System.out.println(" == " + res);
        }
    }
}



Код… Да, можно было написать грамотней.
Алгоритм… Да, наверняка он не правильный. Но он работает :)
мой оригинал

+4
12.3k 21
Comments 14