сортировка строк огромного файла .txt в Java - PullRequest
Новая
       45

сортировка строк огромного файла .txt в Java

7 голосов
/ 12 января 2012

Я работаю с очень большим текстовым файлом (755 МБ). Мне нужно отсортировать строки (около 1890000), а затем записать их обратно в другой файл.

Я уже заметил, что обсуждение, у которого есть начальный файл, действительно похожий на мой: Сортировка строк на основе слов в них в качестве ключей

Проблема в том, что я не могу сохранить строки в коллекции в памяти, потому что я получаю исключение пространства кучи Java (даже если я расширил его по максимуму) .. (уже пробовал!)

Я не могу открыть его с помощью Excel и использовать функцию сортировки, поскольку файл слишком велик и его нельзя полностью загрузить.

Я думал об использовании БД ... но я думаю, что при написании всех строк затем использовать запрос SELECT, это слишком долго с точки зрения времени выполнения .. я не прав?

Любые намеки приветствуются Заранее спасибо

Ответы [ 6 ]

15 голосов
/ 12 января 2012

Я думаю, что решение здесь - выполнить сортировку слиянием, используя временные файлы:

  1. Считайте первые n строк первого файла ( n - количество строк, которое вы можете позволить сохранить и отсортировать в памяти), отсортировать их и запишите их в файл 1.tmp (или как вы его называете). Сделайте то же самое со следующими n строками и сохраните его в 2.tmp. Повторяйте, пока все строки исходного файла не будут обработаны.

  2. Читать первую строку каждого временного файла. Определите наименьший (в соответствии с порядком сортировки), запишите его в целевой файл и прочитайте следующую строку из соответствующего временного файла. Повторяйте, пока все строки не будут обработаны.

  3. Удалить все временные файлы.

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

2 голосов
/ 12 января 2012

Вы можете запустить следующее с помощью 

-mx1g -XX:+UseCompressedStrings  # on Java 6 update 29
-mx1800m -XX:-UseCompressedStrings  # on Java 6 update 29
-mx2g  # on Java 7 update 2.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String... args) throws IOException {
        long start = System.nanoTime();
        generateFile("lines.txt", 755 * 1024 * 1024, 189000);

        List<String> lines = loadLines("lines.txt");

        System.out.println("Sorting file");
        Collections.sort(lines);
        System.out.println("... Sorted file");
        // save lines.
        long time = System.nanoTime() - start;
        System.out.printf("Took %.3f second to read, sort and write to a file%n", time / 1e9);
    }

    private static void generateFile(String fileName, int size, int lines) throws FileNotFoundException {
        System.out.println("Creating file to load");
        int lineSize = size / lines;
        StringBuilder sb = new StringBuilder();
        while (sb.length() < lineSize) sb.append('-');
        String padding = sb.toString();

        PrintWriter pw = new PrintWriter(fileName);
        for (int i = 0; i < lines; i++) {
            String text = (i + padding).substring(0, lineSize);
            pw.println(text);
        }
        pw.close();
        System.out.println("... Created file to load");
    }

    private static List<String> loadLines(String fileName) throws IOException {
        System.out.println("Reading file");
        BufferedReader br = new BufferedReader(new FileReader(fileName));
        List<String> ret = new ArrayList<String>();
        String line;
        while ((line = br.readLine()) != null)
            ret.add(line);
        System.out.println("... Read file.");
        return ret;
    }
}

печать 

Creating file to load
... Created file to load
Reading file
... Read file.
Sorting file
... Sorted file
Took 4.886 second to read, sort and write to a file
1 голос
/ 12 января 2012

Алгоритм:

Сколько памяти у нас доступно? Предположим, у нас есть X MB доступной памяти.

  1. Разделите файл на K кусков, где X * K = 2 GB. Поместите каждый кусок в память и отсортируйте строки, как обычно, используя любой O(n log n) алгоритм. Сохраните строки обратно в файл.

  2. Теперь внесите следующий фрагмент в память и выполните сортировку.

  3. Как только мы закончим, объедините их один за другим.

Вышеприведенный алгоритм также известен как внешняя сортировка. Шаг 3 известен как N-way merge

0 голосов
/ 12 января 2012

Может быть, вы можете использовать perl для форматирования файла. И загрузить в базу данных, как mysql. это так быстро и использовать индекс для запроса данных. и записать в другой файл.

вы можете установить размер кучи jvm, например, '-Xms256m -Xmx1024m'. Я надеюсь помочь вам.

0 голосов
/ 12 января 2012

разделяй и властвуй - лучшее решение:)

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

Ссылки:

Сортировка файла с огромным объемом данных с учетом ограничения памяти

http://hackerne.ws/item?id=1603381

0 голосов
/ 12 января 2012

Почему бы вам не попробовать многопоточность и увеличить размер кучи программы, которую вы запускаете?(для этого также необходимо использовать сортировку слиянием, если у вас в системе больше памяти, чем 755 МБ.)

...