Как сортировать очень большие файлы

Ответ 1

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

Взгляните на это: http://en.wikipedia.org/wiki/Merge_sort

и: http://en.wikipedia.org/wiki/External_sorting

В основном идея состоит в том, чтобы разбить файл на более мелкие части, отсортировать их (либо с помощью сортировки слияния, либо с помощью другого метода), а затем использовать Merge из merge-sort для создания нового, отсортированного файла.

Ответ 2

Для этого вам нужна внешняя сортировка слияния. Здесь - это реализация Java, которая сортирует очень большие файлы.

Ответ 3

Поскольку ваши записи уже находятся в текстовом формате с плоским файлом, вы можете подключить их к UNIX sort(1), например. sort -n -t' ' -k1,1 < input > output. Он автоматически разбивает данные и выполняет сортировку слияния с использованием доступной памяти и /tmp. Если вам нужно больше места, чем у вас есть доступная память, добавьте -T /tmpdir в команду.

Очень забавно, что все говорят вам загружать огромные библиотеки С# или Java или реализовывать слияние-сортировку самостоятельно, когда вы можете использовать инструмент, который доступен на каждой платформе и существует уже несколько десятилетий.

Ответ 4

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

class Line {
   int key, length;
   long start;
}

Это будет использовать около 40 байт в строке.

После того как вы отсортировали этот массив, вы можете использовать RandomAccessFile для чтения строк в том порядке, в котором они появляются.

Примечание: поскольку вы будете случайно попадать на диск, вместо использования памяти это может быть очень медленным. Типичный диск занимает 8 мс для случайного доступа к данным, и если у вас 10 миллионов строк, это займет около одного дня. (Это самый худший случай). В памяти это займет около 10 секунд.

Ответ 5

Вы можете использовать файл SQL Lite db, загружать данные в db, а затем разрешать сортировку и возвращать результаты для вас.

Преимущества: Не нужно беспокоиться о написании лучшего алгоритма сортировки.

Недостаток: вам потребуется дисковое пространство, медленная обработка.

https://sites.google.com/site/arjunwebworld/Home/programming/sorting-large-data-files

Ответ 6

Что вам нужно сделать, так это объединить файлы через поток и обработать их отдельно. Затем вы можете объединить файлы вместе, поскольку они уже будут отсортированы, это похоже на то, как работает сортировка слияния.

Ответ на этот вопрос SO будет полезен: Поток больших файлов

Ответ 7

Операционные системы поставляются с мощной утилитой сортировки файлов. Простая функция, вызывающая bash script, должна помочь.

public static void runScript(final Logger log, final String scriptFile) throws IOException, InterruptedException {
    final String command = scriptFile;
    if (!new File (command).exists() || !new File(command).canRead() || !new File(command).canExecute()) {
        log.log(Level.SEVERE, "Cannot find or read " + command);
        log.log(Level.WARNING, "Make sure the file is executable and you have permissions to execute it. Hint: use \"chmod +x filename\" to make it executable");
        throw new IOException("Cannot find or read " + command);
    }
    final int returncode = Runtime.getRuntime().exec(new String[] {"bash", "-c", command}).waitFor();
    if (returncode!=0) {
        log.log(Level.SEVERE, "The script returned an Error with exit code: " + returncode);
        throw new IOException();
    }

}

Ответ 8

Вам нужно выполнить внешний вид. Это своего рода ведущая идея Hadoop/MapReduce, так как она не учитывает распределенный кластер и работает на одном узле.

Для лучшей производительности вы должны использовать Hadoop/Spark.

Измените эти строки в соответствии с вашей системой. fpath - ваш один большой файл ввода (протестирован с 20 ГБ). shared путь - это где хранится журнал выполнения. fdir - это промежуточные файлы, которые будут сохранены и объединены. Измените эти пути в соответствии с вашим устройством.

public static final String fdir = "/tmp/";
    public static final String shared = "/exports/home/schatterjee/cs553-pa2a/";
    public static final String fPath = "/input/data-20GB.in";
    public static final String opLog = shared+"Mysort20GB.log";

Затем запустите следующую программу. Ваш окончательный отсортированный файл будет создан с именем op401 в пути fdir. последняя строка Runtime.getRuntime().exec("valsort " + fdir + "op" + (treeHeight*100)+1 + " > " + opLog); проверяет, сортируется ли выход. Удалите эту строку, если у вас нет установленного valsort или входной файл не генерируется с помощью gensort (http://www.ordinal.com/gensort.html).

Также не забудьте изменить int totalLines = 200000000; к общим строкам в вашем файле. и количество потоков (int threadCount = 16) должно всегда быть в силе 2 и достаточно большим, чтобы количество (суммарный размер * 2/нет потока) количество данных могло находиться в памяти. Изменение счетчика потоков приведет к изменению имени конечного выходного файла. Как и для 16, это будет op401, для 32 будет op501, для 8 будет op301 и т.д.

Наслаждаться.

    import java.io.*;
    import java.nio.file.Files;
    import java.nio.file.Paths;
    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.stream.Stream;


    class SplitFile extends Thread {
        String fileName;
        int startLine, endLine;

        SplitFile(String fileName, int startLine, int endLine) {
            this.fileName = fileName;
            this.startLine = startLine;
            this.endLine = endLine;
        }

        public static void writeToFile(BufferedWriter writer, String line) {
            try {
                writer.write(line + "\r\n");
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        public void run() {
            try {
                BufferedWriter writer = Files.newBufferedWriter(Paths.get(fileName));
                int totalLines = endLine + 1 - startLine;
                Stream<String> chunks =
                        Files.lines(Paths.get(Mysort20GB.fPath))
                                .skip(startLine - 1)
                                .limit(totalLines)
                                .sorted(Comparator.naturalOrder());

                chunks.forEach(line -> {
                    writeToFile(writer, line);
                });
                System.out.println(" Done Writing " + Thread.currentThread().getName());
                writer.close();
            } catch (Exception e) {
                System.out.println(e);
            }
        }
    }

    class MergeFiles extends Thread {
        String file1, file2, file3;
        MergeFiles(String file1, String file2, String file3) {
            this.file1 = file1;
            this.file2 = file2;
            this.file3 = file3;
        }

        public void run() {
            try {
                System.out.println(file1 + " Started Merging " + file2 );
                FileReader fileReader1 = new FileReader(file1);
                FileReader fileReader2 = new FileReader(file2);
                FileWriter writer = new FileWriter(file3);
                BufferedReader bufferedReader1 = new BufferedReader(fileReader1);
                BufferedReader bufferedReader2 = new BufferedReader(fileReader2);
                String line1 = bufferedReader1.readLine();
                String line2 = bufferedReader2.readLine();
                //Merge 2 files based on which string is greater.
                while (line1 != null || line2 != null) {
                    if (line1 == null || (line2 != null && line1.compareTo(line2) > 0)) {
                        writer.write(line2 + "\r\n");
                        line2 = bufferedReader2.readLine();
                    } else {
                        writer.write(line1 + "\r\n");
                        line1 = bufferedReader1.readLine();
                    }
                }
                System.out.println(file1 + " Done Merging " + file2 );
                new File(file1).delete();
                new File(file2).delete();
                writer.close();
            } catch (Exception e) {
                System.out.println(e);
            }
        }
    }

    public class Mysort20GB {
        //public static final String fdir = "/Users/diesel/Desktop/";
        public static final String fdir = "/tmp/";
        public static final String shared = "/exports/home/schatterjee/cs553-pa2a/";
        public static final String fPath = "/input/data-20GB.in";
        public static final String opLog = shared+"Mysort20GB.log";

        public static void main(String[] args) throws Exception{
            long startTime = System.nanoTime();
            int threadCount = 16; // Number of threads
            int totalLines = 200000000;
            int linesPerFile = totalLines / threadCount;
            ArrayList<Thread> activeThreads = new ArrayList<Thread>();

            for (int i = 1; i <= threadCount; i++) {
                int startLine = i == 1 ? i : (i - 1) * linesPerFile + 1;
                int endLine = i * linesPerFile;
                SplitFile mapThreads = new SplitFile(fdir + "op" + i, startLine, endLine);
                activeThreads.add(mapThreads);
                mapThreads.start();
            }
            activeThreads.stream().forEach(t -> {
                try {
                    t.join();
                } catch (Exception e) {
                }
            });

            int treeHeight = (int) (Math.log(threadCount) / Math.log(2));

            for (int i = 0; i < treeHeight; i++) {
                ArrayList<Thread> actvThreads = new ArrayList<Thread>();

for (int j = 1, itr = 1; j <= threadCount / (i + 1); j += 2, itr++) {
                    int offset = i * 100;
                    String tempFile1 = fdir + "op" + (j + offset);
                    String tempFile2 = fdir + "op" + ((j + 1) + offset);
                    String opFile = fdir + "op" + (itr + ((i + 1) * 100));

                    MergeFiles reduceThreads =
                            new MergeFiles(tempFile1,tempFile2,opFile);
                    actvThreads.add(reduceThreads);
                    reduceThreads.start();
                }
                actvThreads.stream().forEach(t -> {
                    try {
                        t.join();
                    } catch (Exception e) {
                    }
                });
            }
            long endTime = System.nanoTime();
            double timeTaken = (endTime - startTime)/1e9;
            System.out.println(timeTaken);
            BufferedWriter logFile = new BufferedWriter(new FileWriter(opLog, true));
            logFile.write("Time Taken in seconds:" + timeTaken);
            Runtime.getRuntime().exec("valsort  " + fdir + "op" + (treeHeight*100)+1 + " > " + opLog);
            logFile.close();
        }
    }