Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Работа с файлами большого размера

Автор: CSharpProgrammer 8.9.2010, 22:43

Доброго времени суток!

Задача заключается в том чтобы

1) Работать с большим количеством файлов
2) Работать с файлами большого размера (1Гб и больше)

Фалы содержат текстовую информацию, которую нужно распарсить и почистить. как бы мне это сделать наиболее оптимальным образом?

Автор: aleksandy 9.9.2010, 11:06

Задачу можно уточнить? Что за текстовая информация? В каком виде она хранится, что нужно с ней сделать конкретно?

Покажи как ты начал это все реализовывать, если начал. Тогда может быть тебе кто-нибудь и поможет.

Автор: CSharpProgrammer 10.9.2010, 11:23

Цитата(aleksandy @ 9.9.2010, 11:06)

Задача #1:

Имеется файл большого размера (загрузить весь в память нет возможности) содержащий предложения разделенные точкой. Нужно удалить дубли. Алгоритм:
Есть исходный файл (содержащий предложения с дублями) и результирующий (файл куда будут записываться уникальные предложения). После того как кол-во предложений в результирующем файле привысит размер блока, то каждое предложение следующего блока с исходного файла будет сравниваться с каждым предложением всех блоков результирующего (+оптимизация). Т.е. нужно считывать блоки предложений с обоих файлов и сравнивать тоже блоками.

Задача #2:

Имеется большое кол-во файлов (больше 5.000.000) размером оклол 1 мб, файлы находятся не в одной директории, а в суб-директориях, вложенность директорий тоже довольно большая (К примеру в Директории А содержаться 10 файлов и 5 поддиректорий. Каждая поддиректория в свою очередь тоже содержит файлы и другие суб-директории и.т.д.). Так вот нужно обойти все суб-директории и обработать все файлы. Файлы нужно почистить от всех символов не являющихся буквами при этом сохранить структуру предложений.

Автор: AntonSaburov 10.9.2010, 18:11

По поводу 1
Я не понял по поводу "После того как кол-во предложений в результирующем файле привысит размер блока, то каждое предложение следующего блока с исходного файла будет сравниваться с каждым предложением всех блоков результирующего".
Что за блок такой ?

По поводу 2
Ну тут рекурсивно обегать надо. Что-то вроде такого

Код


public class Main {

    public static void main(String[] args) {
        Main m = new Main();
        String root = <"Начальная директория">;
        m.showFileList(root);
    }

    private void showFileList(String root) {
        File fileRoot = new File(root);
        String[] list = fileRoot.list();
        for (String s : list) {
            File fileLocal = new File(root + File.separator + s);
            System.out.println(fileLocal.getAbsolutePath());
            System.out.println();
            if (fileLocal.isDirectory()) {
                showFileList(fileLocal.getAbsolutePath());
            }
        }

    }
}

Автор: soulcub 10.9.2010, 20:04

По задаче №1. Я бы считывал из 1-го файла по предложению и сверял бы его со всеми предложениями результирующего файла по мере его наполнения.. Так в конце сложность вычислений будет равна n!, где n-количество уникальных строк, что не так и страшно.. Правда всё это будет с файлами.. Можно перекачать весь исходник в бинарный файл, для ускорения чтения с файла. Я так себе думаю, что делать блоками - нет смысла, ибо что на прямую, что блоками, всё равно количество чтений из файла будет большими.

Ну это я так думаю. Может ошибаюсь)

По 2-й. Не знаю, хватит ли памяти) Но можно попробовать рекурсивно обойти все каталоги с очисткой файлов на каждом уровне.. Если памяти не хватает, то можно разделить рекурсию, например отдельно на все подкаталоги главного каталога. Это уменьшит затраты в [количество подкаталогов] раз.

Автор: jk1 11.9.2010, 08:11

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

Для того, чтобы не вычитывать в память файл целиком можно иcпользовать http://www.java2s.com/Tutorial/Java/0180__File/MemoryMappedFiles.htm

Автор: Connie 11.9.2010, 11:06

Цитата

Имеется файл большого размера (загрузить весь в память нет возможности) содержащий предложения разделенные точкой. Нужно удалить дубли. Алгоритм:
Есть исходный файл (содержащий предложения с дублями) и результирующий (файл куда будут записываться уникальные предложения). После того как кол-во предложений в результирующем файле привысит размер блока, то каждое предложение следующего блока с исходного файла будет сравниваться с каждым предложением всех блоков результирующего (+оптимизация). Т.е. нужно считывать блоки предложений с обоих файлов и сравнивать тоже блоками.

А не проще вначале закинуть эти предложения в какую либо БД, а потом просто одим запросом дропнуть дубли и перезаписать этот файл?

Автор: CSharpProgrammer 12.9.2010, 09:42

AntonSaburov

Спасибо. Под блоками имелось ввиду - чтобы не считывать одно предложение с исходного файла и сравнивать с каждым из результирующего, считывать блок предложений (скажем 100) и потом уже в памяти сравнивать эти 100 предложений с предложениями из результирующего. Т.е. Когда в результирующем файле будет больше 100 предложений, то будем делать так:
1) Считаем 100 предложений из исходного
2) Считаем 100 из результирующего
3) Сравним их и найдем уникальные (к примеру 20)
4) Считаем следующий блок из результирующего
5) Сравним оставшиеся (20 уникальных) с предложениями из этого блока
6) ну и т.д.

В общем считывать не по одному предложению а блоками.

soulcub
Спасибо. Про рекурсию мне тоже кажется может не хватить памяти, но раз другого способа нет, то будем разбивать на подходы (по директориям).

jk1

Спасибо за Хэш-коды и Memory Mapped Files

Connie

Возможно и проще, спасибо.

Автор: Connie 12.9.2010, 11:35

Цитата

Возможно и проще

Дело даже не в этом. Если, к примеру, одно предложение находится в начале этого большого файла, а потом оно же существует и в конце, то не храня это предложение в памяти не выйдет его пропустить обрабатывая конец файла. А если предположить, что этот файл не состоит из одних повторов, ну допустим хотя бы на 50%, то из 10-и гигабайтного файла 5 гигов нужно будет держать в памяти.