Java: читать группы строк с одинаковым префиксом из очень большого текстового файла

У меня есть большой (~ 100 ГБ) текстовый файл, структурированный следующим образом:

A,foobar
A,barfoo
A,foobar
B,barfoo
B,barfoo
C,foobar

Каждая строка представляет собой пару значений, разделенных запятыми. Файл сортируется по первому значению в паре. Линии имеют переменную длину. Определите группу как все строки с общим первым значением, т. е. в приведенном выше примере все строки, начинающиеся с «А», будут группой, а все строки, начинающиеся с «В», будут другой группой.

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

У меня есть процедура для обработки одной такой группы строк и записи в текстовый файл. Моя проблема в том, что я не знаю, как лучше всего читать файл по группе за раз. Все группы произвольного неизвестного размера. Я рассматривал два пути:

1) Сканировать файл с помощью BufferedReader, накапливая строки из группы в строку или массив. Всякий раз, когда встречается строка, принадлежащая новой группе, удерживайте эту строку во временной переменной, обрабатывая предыдущую группу. Очистите аккумулятор, добавьте временную, а затем продолжите чтение новой группы, начиная со второй строки.

2) Сканировать файл с помощью BufferedReader, всякий раз, когда встречается строка, принадлежащая новой группе, каким-то образом сбрасывать курсор, чтобы при следующем вызове readLine() он начинался с первой строки группы, а не со второй. Я просмотрел mark() и reset(), но для этого нужно знать позицию байта начала строки.

Я собираюсь пойти с (1) на данный момент, но я был бы очень признателен, если бы кто-нибудь мог предложить метод, который меньше пахнет.


java file text line bufferedreader
person advait    schedule 30.08.2012    source источник
comment
Вы хотите искать конкретную группу или хотите делать настоящие целые значения?   -  person Ruwantha    schedule 30.08.2012
comment
@ RJ45 для всех строк в каждой группе. Мне нужно выполнить вычисление для каждой строки в группе, выполнить вычисление, объединяющее результаты отдельных строк, и записать результат на диск.   -  person advait    schedule 30.08.2012
comment
Похоже, это потенциальный кандидат на github.com/fge/largetext.   -  person aliteralmind    schedule 02.07.2014

Ответы (2)


arrow_upward
2
arrow_downward

Я думаю, что PushbackReader будет работать:

 if (lineBelongsToNewGroup){
     reader.unread(lastLine.toCharArray());
     // probably also unread a newline
 }
person Thilo    schedule 30.08.2012
comment
Жаль, что он не понимает линий. Не знаю, как совместить его с BufferedReader. - person Thilo; 30.08.2012
comment
Спасибо Тило. Вы правильно поняли, что я хотел. Мне нужен был чистый способ чтения групп строк, по сути что-то вроде: while (thereAreGroupsRemaining) { String s = readNextGroup(); process(s); } - person advait; 30.08.2012

arrow_upward
1
arrow_downward

Я думаю, что вариант 1 самый простой. Я бы разобрал текст самостоятельно, а не использовал BufferedReader, так как для анализа 100 ГБ потребуется одно время.

Единственный вариант, который, вероятно, будет быстрее, — это использовать двоичный поиск, обращаясь к файлу с помощью RandomAccessFile. Вы можете отобразить 100 ГБ памяти на 64-битной JVM. Это позволяет избежать необходимости анализировать каждую строку, что довольно дорого. Преимущество этого подхода в том, что вы можете использовать несколько потоков. Его гораздо сложнее реализовать, но он должен быть намного быстрее. Получив каждую границу, вы можете массово копировать необработанные данные, не анализируя все строки.

person Peter Lawrey    schedule 30.08.2012
comment
Я думаю, он хочет прочитать весь файл (а не только одну группу). - person Thilo; 30.08.2012
comment
@Thilo Верно, но ОП нужно найти только первую и последнюю строку каждой группы. Используя произвольный доступ, вы можете не читать как строки все строки между ними. Когда у вас есть позиция первой строки и позиция первой строки следующей группы, вы можете эффективно копировать из ByteBuffer в FileChannel. И это поиск, который вы можете выполнять в многопоточном режиме. - person Peter Lawrey; 30.08.2012
comment
Но он также захочет, чтобы между ними были все строки (в виде строк). Это кажется мне однопроходной потоковой операцией, в конечном итоге считывающей каждую строку ровно один раз (плюс небольшая перемотка назад в начале каждой группы), нет необходимости в произвольном доступе. Но, возможно, я что-то неправильно понял. - person Thilo; 30.08.2012
comment
@Thilo Вы можете читать каждую строку по отдельности, просто это очень медленно. esp, когда вам не нужно анализировать каждую строку. - person Peter Lawrey; 30.08.2012
comment
Не знаю... Похоже, ему все равно нужно прочитать в память целую группу для следующей операции. Таким образом, даже если пропуск бинарного поиска ускорит обнаружение границ, следующим шагом будет повторное чтение всей группы (что, по-видимому, также включает синтаксический анализ, по крайней мере, для поиска концов строк для разделения данных на строки, что кажется, не сильно отличается от поиска запятой). - person Thilo; 30.08.2012
comment
Провел быстрый тест, где чтение 1 ГБ заняло 27 секунд. Поэтому я предполагаю, что чтение строк с BufferedReader.readLine() размером 100 ГБ займет 45 минут. Как только вы узнаете расположение начала и конца группы, вы можете копировать из прямого ByteBuffer в FileChannel без анализа данных или переноса их в пространство Java вообще. Вам не нужно анализировать отдельные линии или создавать объекты на их концах. - person Peter Lawrey; 30.08.2012
comment
можно ли выполнить следующую операцию без переноса данных в пространство Java. Сколько времени потребуется, чтобы установить все границы для этого 1-гигабайтного файла? В любом случае, +1 за усилия сейчас ;-) - person Thilo; 30.08.2012
comment
Привет, ребята, спасибо за вашу помощь. Просто для уточнения: 1) мне нужно прочитать каждую строку в каждой группе. 2) Это одноразовая операция, я уверен, что дисковый ввод-вывод будет самым большим узким местом, и ее можно выполнять в течение нескольких часов. - person advait; 30.08.2012
comment
Если скорость не слишком важна, я бы сделал это самым простым способом, который работает. У меня все еще складывается впечатление, что вам нужно только копировать каждую строку, а не каждую строку readLine(). С помощью readLine() вы можете читать от 30+ МБ в секунду в зависимости от вашего процессора, что близко к максимальной скорости жесткого диска. - person Peter Lawrey; 30.08.2012
comment
@PeterLawrey Спасибо. Как будет реализован ваш более быстрый метод копирования? Как он может быть более/менее гибким, чем readLine()? - person advait; 30.08.2012
comment
@advait readLine() должен прочитать и скопировать каждый символ, последовательно декодированный из байтов, чтобы найти конец каждой строки. Наконец создайте объект String. Это требует немало работы. Читая байты случайным образом, вы можете найти новую строку и имя группы без декодирования байтов, и вы можете использовать двоичный поиск, чтобы найти начало и конец, не анализируя все строки между ними. Когда у вас есть начало и конец, вы можете выполнить массовое копирование, используя прямую память, не читая в Java большую часть байтов в середине группы. Это было бы быстрее для программы, не для разработчика ;) - person Peter Lawrey; 30.08.2012
comment
@PeterLawrey Подробно и понятно, спасибо! Я думаю, что касается моих навыков разработки программного обеспечения: (время на разработку более быстрой версии + время на запуск более быстрой версии) › (время на разработку более медленной версии + время на запуск более медленной версии), поэтому мне придется использовать более простой метод для сейчас :) - person advait; 30.08.2012
comment
@advait Согласен. Только если у вас есть действительно большие файлы, вы даже сочтете, что это стоит усилий. ;) - person Peter Lawrey; 30.08.2012