Сортировка больших объёмов данных, реализация на 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);
            }
        }
    }



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

    Комментарии 14

      +1
      Почему в конструктор передаёте итератор без дженерика?
        0
        Упс. Наверное потому, что дженерики начал копать позавчера :)
        «Виноват, сейчас исправлюсь»
        0
        Вместо Listitems = new ArrayList(); нужно использовать LinkedList. Мы же с вами знаем что вставка в список намного быстрее ArrayList. А ArrayList мы используем когда нам нужен быстрый доступ к элементу по индексу.

        Вам не кажется что такой предор и вставка не очень красивый код?
        for (FileSortStorage f: partFiles) {
        iterators.add(f.iterator());
        }

        Я бы на вашем месте посмотрел в сторону Collection класса или утилит по работе с коллекциями.

        И почему вы не стали пользоваться коллекциями которые предназначены для сортировки?
          0
          *перебор
            0
            ArrayList я использовал, т.к. к этому списку (хоть он и не слишком большой) идут частые обращения к случайному элементу ( iterators.get(minIdx) и items.set(minIdx, iterators.get(minIdx).next()) ).
            Я не тестировал и опыта у меня пока «кот наплакал», но предположил, что оно сработает лучше :)

            Перебор… Можно было воспользоваться итератором и здесь (да, они мне очень нравятся), но код получился бы длиннее.

            Классы по работе с коллекциями я как раз использовал. Да, совсем чуть-чуть. А есть специализированные классы, которые позволяют сортировать большие объёмы данных (для которых памяти совсем не хватает)?
              0
              Перебор… вообще нехорошо. Мы же просто берем из одного списка и вставляем в другой. Это «узкое место». У коллекций есть метод addAll.

              Первым делом я стал бы смотреть в сторону коллекций которые предназначены для сортировки SortedSet, TreeSet.

              java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html
                0
                А смысл этих сортирующих коллекций тут?
                  0
                  эммм мы же про «Сортировку больших объёмов данных» тут разговариваем. Может строить нашу сортировку на основе этих коллекций?
                    0
                    Set'ы ведь уникализируют содержимое. А у нас произвольный список.

                    И, мне кажется, Вы несколько не поняли алгоритм. AddAll здесь помочь никак не может, т.к. в переменной(списке) items хранятся по одному минимальному на текущий момент значению из файлов подкачки (доступных через переменную(список итераторов :)) iterators). Добавив минимальное значение из одного из них необходимо подтянуть из использованного источника следующее значение. Вдруг оно окажется меньшим остальных имеющихся в пуле?

                    Про коллекции читал, туториал тоже разбирал. В доступном объёме их возможности используются, но как ими сортировать большие массивы (например, терабайты), на ум не приходит.

                    ВотЪ
              0
              > Я бы на вашем месте посмотрел в сторону Collection класса или утилит по работе с коллекциями.
              Не совсем понятно о чём вы. Collection — абстрактный класс и он там, строго говоря, используется. Может вы имели в виду класс Collections?
                0
                Да, вы правы. Редко его использую.
            • НЛО прилетело и опубликовало эту надпись здесь
                0
                В JavaTest есть разнообразные алгоритмы сортировки.
                  0
                  Есть. Но у Вас несколько не то. Насколько я понял, там примеры реализации алгоритмов, сделанные «для себя» и «чтобы понять». Некоторые даже переведены с паскаля, ах, ностальгия :)
                  Такие примеры можно (и мне кажется удобно) смотреть в той же википедии ( Категория: Алгоритмы_сортировки — описания с примерами реализации на различных языках ).
                  А здесь я пытался привести пример универсальной реализации внешней сортировки (т.е. той, оперирует большим объёмом данных, который обычной сортировкой обработать нельзя).

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое